Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 56
Текст из файла (страница 56)
Сколько существует функций из 6-элементного множества в 3-элементное? 16. Сколько существует инъективных функций из 3-элементного множества в 6-элементное? 17. Сколько положительных целых чисел, меньших 700, не делятся на 8? 18. Сколько положительных целых чисел, меньших 1000, не делятся на 5? Которые не делятся на 5? 19.
Сколько существует двубуквенных или трехбуквенных инициалов для людей? 20. Сколько существует различных двубуквенных или трехбуквенных инициалов для людей, если никакие буквы не могут повторяться? 21. Сколько существует битовых строк длины 7? 22. Сколько существует битовых строк длины 7, если первый и последний биты совпадают? 23. Сколько существует битовых строк длины 7-элементных строк битов, содержащих две или более единиц? 24.
Если телефонный номер не может начинаться с О, 1 или 8, то сколько существует различных 7-значных телефонных номеров? 25. Сколько существует четырехзначных чисел, содержащих хотя бы одну цифру 7? 26. Сколько существует четырехзначных чисел, которые не содержат цифру 7? 27. Если компьютерный пароль содержит семь символов, которые могут быть цифрой или буквой, то сколько существует паролей, начинающихся с буквы? 324 ГЛАВА 8. Комбинаторика и вероятность 8.2. КОМБИНАТОРНЫЙ ПРИНЦИП СЛОЖЕНИЯ До настояшего момента непересекающиеся множества рассматривались только в связи с комбинаторным принципом сложения.
Предположим, что множества 5 и Т не являются непересекающимися и требуется найти (5 ш Т~. Когда количество элементов множества о суммируется с количеством элементов множества Т, элементы, принадлежащие ЗпТ, учитываются дважды. Поэтому количество элементов, принадлежащих множеству о' гт Т, нужно из суммы вычесть. Отсюда получаем следующую теорему. ТЕОРЕМА 8.12. Пусть о и Т вЂ” множества. Количество элементов, которое можно выбрать из о или Т, равно )5! + (Т~ — )Я и Т~. Иными словами, )Я ш Т~ = ~В! + (Т! — )5 и Т~.
ДОКАЗАТЕЛЬСТВО. Множество НоТ = (о — Т) и (Т вЂ” 3) и(о гзТ), где о — Т, Т вЂ” о и о П Т вЂ” попарно непересекаюшиеся множества. Поэтому )5 и Т~ = ф— Т~+~Т вЂ” Я~+~РпТ1 Имеем также, что 5 = ф — Т)и(~г~Т) и Т = (Т вЂ” Н)ифпТ), откуда /5/ = !5 — Т~ + !5 и Т~ и !Т/ = ~Т вЂ” Я/+ /В П Т~, Следовательно, /5!+ !Т/ — /ЯГНЯТ~ = !Я вЂ” Т~ + ~Т вЂ” Я/+ 2/ЯПТ~ — /ЯпТ~ = = )~ — Т~+ ~Т вЂ” ~!+ !~ п Т~ = = ~Н оТ~. ПРИМЕР 8.13. Предположим, что в группе из 100 студентов 60 человек изучают математику, 75 — историю, а 45 человек — и то, и другое.
а) Сколько студентов изучают математику или историю? б) Сколько студентов не изучают ни математику, ни историю? а) Пусть универсум Н вЂ” группа из 100 студентов, М вЂ” множество студентов, изучаюших математику, Н вЂ” множество студентов, изучающих историю. Тогда количество студентов, изучающих математику или историю, равно )М ш Н~ = )М) + (Н) — )М п Н! = = 60+ 75 — 45 = = 90. б) Количество студентов, не изучающих ни математику, ни историю, равно ~М' П Н'(. Но М'й Н' = (М 0 Н)', поэтому )М' г~ Н'~ = )(М и Н)'( = = 100 — 90 = = 10. П ПРИМЕР 8.14. Найдем количество положительных целых чисел, меньших 1001, которые делятся на 3 или на 5.
Количество элементов множества о положительных целых чисел, меньших 1001, которые делятся на 3, равно 1'"з"') или 333. Количество элементов множества Т положительных целых чисел, меньших 1001, которые делятся на 5, равно ~'~~') или 200. Элементами множества В ПТ являются целые числа, меньшие 1001, которые делятся на 5 и на 3, и поэтому делятся на 15.
Следовательно, (5 П Т~ = '1 — '",з') или 66. Значит )5 ш Т~ = 333+ 200 — 66 = 467. П РАЗДЕЛ 8.2. Комбинеторный принцип сложения 325 ПРИМЕР 8А5. Сколько существует способов разместить цифры О, 1, 2, 3, 4, 5, 6, 7, 8, 9 так, чтобы первая цифра была больше единицы, а последняя — меньше семи? Пусть ЕУ вЂ” множество всех возможных способов размещений цифр, а  — множество всех размещений цифр таких, что первая цифра больше единицы, а последняя — меньше 7.
Для нахождения )ТУ( заметим, что существуют десять способов выбора первой цифры, девять способов выбора второй, восемь способов выбора третьей цифры, ..., два способа выбора девятой и один способ выбора десятой цифры. Поэтому в соответствии с комбинаторным принципом умножения имеются 10! = 3628800 возможных способов размещения цифр, значит Щ = 3628800. Как и в первом примере, воспользуемся "остаточным" принципом и найдем количество размещений цифр, которые не входят в В, после чего вычтем это количество из ~Ц.
Пусть А — множество всех таких размещений цифр, где первая цифра меньше или равна 1. Подсчитывая количество элементов из А, обнаруживаем, что имеются два варианта выбора первой цифры, а именно, 0 и 1. Существуют девять вариантов выбора второй цифры, восемь вариантов выбора третьей цифры, ..., два варианта выбора девятой цифры и один вариант выбора десятой цифры.
Таким образом, множество А содержит 2 х 9! = 725760 элементов. Пусть  — множество всех таких размещений цифр, что последняя цифра больше или равна 7. Подсчитывая количество элементов В, заметим, что имеются три варианта выбора последней цифры, и, следуя схеме, использованной для множества А, получаем, что существуют 9! вариантов выбора остальных цифр. Таким образом, )В! = 3 х 9! = 1088640. Множество АП В состоит из таких размещений цифр, в которых первая цифра больше или равна 1, а последняя цифра больше или равна 7.
Подсчитывая количество элементов множества А и В, находим, что существуют два способа выбора первой цифры и три способа выбора последней цифры. Используя процедуру, аналогичную предыдущей, получаем 8! способов размещения оставшихся цифр. Таким образом, (А П В) = 3 х 2 х 8! = 241920 и (А ш В) = 725760 + 1088640 — 241920 = 1572480.
Все размещения целых чисел такие, что первая цифра больше единицы, а последняя цифра меньше семи, описывают множество А'гзВ' = (АоВ)'. Поэтому число таких размещений равно )ЕУ! — )(АОВ)') = 3628800 — 1572480 = 2056320. П Рассмотрев случай двух множеств, переходим к изучению случая трех множеств. Пусть заданы множества А, В и С, требуется определить ~А 0 В О С~, количество элементов множества Аш Вг~С, в случае, когда эти множества могут пересекаться.
Если составить сумму количества элементов в каждом множестве А, В и С, то согласно диаграмме Венна, изображенной на рис. 8.4, некоторые подмножества при подсчете будут учтены дважды. Если теперь вычесть )А и В), )Ай С) и )ВйС), т.е. количество элементов множества А П В, множества АСС и множества В Гт С соответственно, то, как следует из диаграммы Венна, изображенной на рис. 8.5, элементы множества А п В й С совсем не будут учтены. 326 ГЛАНД 8.
Комбинаторика и вероятность Рис. 8.8 Рис. 8.4 Поэтому добавляем (АйВйС), после чего каждый элемент множества А0ВиС учтен в сумме ровно один раз. Это дает следующую формулу: )А 0 В ш С) = )А) + (В) + )С( — (А Г) В) — (А й С! — ~В и С) + (А Г1 В й С). ПРИМЕР 6А6. Предположим, что, согласно исследованию, из 200 людей, смотрящих телевизор, 110 человек смотрят спортивную передачу, 120 — комедии, 85 предпочитают драмы, 50 смотрят драмы и спорт, 70 — комедии и спорт, 55 смотрят комедии и драмы и 30 человек смотрят все три вида передач. Сколько человек смотрят спорт, комедии или драмы? Сколько человек не смотрят ничего из вышеперечисленного? Пусть ГУ вЂ” множество 200 людей, среди которых проводился опрос. Пусть Я вЂ” множество людей, которые смотрят спорт, Р— множество людей, которые смотрят драмы, и С вЂ” множество людей, предпочитающих комедии. Тогда первое задание — найти (В 0 Р ш С(.
Это можно сделать, используя непосредственно формулу, приведенную выше: (ВО.О ОС) = (В)+ )и)+ (С) — (ВПП( — )ПГ\С) — )ВГЗС)+ )ЯППГ)С! = = 110 + 85 + 120 — 50 — 55 — 70 + 30 = 170, так что 170 человек смотрят спорт, комедии или драмы. Второе задание требует найти ((В о В ш С)') = )С/) — )(Я о В о С)( = 200 — 170 = 30. Итак, 30 человек не смотрят по телевидению ни спорт, ни драмы, ни комедии. П Существует альтернативный метод решения приведенной выше задачи, который является более информативным. Известно, что 30 человек смотрят по телевидению спорт, комедии и драмы.
Поскольку 50 человек смотрят спорт и драмы, то 20 человек должны смотреть спорт и драмы, но не смотреть комедии. Аналогично, 55 смотрят комедии и драмы, поэтому 25 человек должны смотреть комедии и драмы, но не смотреть спорт. К тому же 70 человек смотрят спорт и комедии, поэтому 40 из них смотрят спорт и комедии, но не смотрят драмы. Таким образом, получаем следующие диаграммы Венна, изображенные на рис. 8.6. Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
