Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 58
Текст из файла (страница 58)
Сколько пятизначных целых чисел имеют одной из цифр 3, 5 или 7? 19. Сколько пятизначных целых чисел начинаются с 3 и заканчиваются на 5 или содержат цифру 7 ? 20. В группе из 100 студентов 35 изучают французский язык, 42 — испанский 43 — немецкий, 17 изучают французский и испанский, 15 — испанский и немецкий, 13 — французский и немецкий, и 20 студентов не изучают ни один из трех языков.
а) Сколько студентов изучают французский или немецкий язык, но не изучают испанский? б) Сколько студентов изучают только один из трех языков? в) Сколько студентов изучают два из трех языков? г) Сколько студентов не изучают ни испанский язык, ни французский? д) Сколько студентов изучают только испанский? 16. В группе из 200 студентов 75 изучают математику, 70 — историю, 75— Ряздел 8.3.
Перестановки и сочетания 331 8.3. ПЕРЕСТАНОВКИ И СОЧЕТАНИЯ Переставляя объекты некоторого набора, мы обычно располагаем их в различном порядке. В этом смысле перестановка — это переупорядочение набора объектов, или функция, которая задает такое переупорядочение (см. главу 4, раздел 4.2.). Теперь будем исследовать, сколько существует способов переупорядочения набора объектов. Все необходимое для этого уже имеется. Для подсчета перестановок достаточно воспользоваться правилом умножения. Рассмотрим количество возможных способов формирования числа, переставляя цифры 1, 2, 3, 4 и 5. Варианты возможных перестановок — это, например, числа 12345, 15342, 32415 и 32415.
Для нахождения количества возможных размещений или перестановок заметим, что первую цифру можно выбрать пятью способами, вторую — четырьмя способами, третью — тремя способами, четвертую — двумя, и только один вариант остается для выбора пятой цифры. Поэтому существует 5! возможных перестановок. Точно так же, если необходимо переупорядочить и объектов, то для этого существует и! способов. В перестановках важен порядок.
Числа 51342 и 32415, образованные перестановкой цифр 1, 2, 3, 4 и 5, не совпадают. Кроме того, поскольку перестановки рассматриваются как переупорядочения, то каждый объект можно использовать только один раз. Если бы повтор цифр допускался, то при формировании числа для каждой цифры существовало бы пять вариантов выбора, поэтому существовало бы 5з возможных чисел. Мы будем также рассматривать перестановки, когда объектов больше, чем мест для их размещения.
Это обобщает сформулированное выше понятие перестановки, так как в этом случае нельзя рассматривать перестановку как переупорядочение. Предположим, например, что в организации — 20 человек и из них требуется выбрать президента, вице-президента, секретаря и казначея. Имеются 20 вариантов выбора президента, 19 вариантов выбора вице-президента, 18 способов выбора секретаря и 17 — казначея. Таким образом, получаем 20х19х18х17 способов выбора должностных лиц.
Заметьте, что порядок все еще остается существенным. Есть разница, является ли Мэри Браун президентом, вице-президентом, секретарем или казначеем. Каждое из размещений на должностях четырех выбранных лиц представляет собой различную организацию руководства. По-прежнему, любого человека можно избрать только один раз. Если Мэри Браун выбрана президентом, то ее нельзя избрать ни на одну из остальных трех должностей.
Заметим также, что 20! 20! 20 х 19 х 18 х 17 = — ' = 16! (20 — 4)! ' поскольку все множители в числителе, не превышающие 16, сокращаются с множителями знаменателя, входящими в 16!. Предположим, имеется и человек. Требуется выбрать г из них и расположить в определенном порядке. Существует и способов выбрать первого человека, п — 1 способов выбора второго, и — 2 способов выбора третьего, и — 1' + 1 способов выбора 7ъго и и — г+1 способов выбора г-го человека. Следовательно, существует (п)(п — 1)(п — 2)(п — 3) (и — г'+1) (п — г+1) 332 ГЛАНА 8.
Комбинаторика и вероятность способов выбрать г человек из и. Но п!' (п)(п — 1) (и — 2) (и — 3) . (и — 1 + 1) (и — т + 1) = (п — г)! Сформулируем вышесказанное в виде следующей теоремы. ТЕОРЕМА 8.20. Количество способов выбрать г объектов с учетом порядка из п объектов равно и! (и)(п — 1)(п — 2)(п — 3) ..(и — ! + 1) .(и — т + 1) = (и — т)! и.' ОПРЕДЕЛЕНИЕ 8.21. Пусть Р(ткт) =,.
Р(п,т) называется числом (п — г)! перестановок из и объектов по г. Заметим, что если выбирать все и объектов и размешать их в определенном порядке, то т = п и, поскольку О! = 1, имеем п. 'и! Р(п,п) = ' = — ' =пй (и — п)! О! Таким образом, приходим к уже известному результату для случая перестановок п элементов. ПРИМЕР 8.22. Сколько различных четырехзначных чисел можно образовать из цифр 1, 2, 3, ..., 9, если все цифры в каждом четырехзначном числе различны? Для формирования каждого четырехзначного числа выбираем четыре цифры из девяти, поэтому существует 9! 9! Р(9, 4) = = — = 3024 (9 — 4)! 5! таких различных чисел. П ПРИМЕР 8.23. Сколькими способами можно расставить в ряд для фотографирования пять мальчиков и шесть девочек, если ни две девочки, ни два мальчика не должны стоять рядом? Мальчиков меньше, чем девочек, поэтому первой должна стоять девочка, а дальше мальчики и девочки должны чередоваться.
Итак, ряд должен иметь вид ДМДМДМДМДМД. Существуют 6! способов расположить девочек на позициях Д и 5! способов расположить мальчиков на позициях М. Следовательно, имеется 6! х 5! способов расставить детей. П ПРИМЕР 8.24. Сколькими способами можно расположить для фотографирования пять мальчиков и пять девочек, если ни две девочки, ни два мальчика не должны стоять рядом? В данной ситуации первым в ряду может быть либо мальчик, либо девочка. Если первой стоит девочка, то ряд имеет вид ДМДМДМДМДМ.
Имеются 5! способов расставить девочек на позициях Д и 5! способов расставить мальчиков на позициях М. Поэтому, существуют 5! х 5! способов расположить детей в ряд, если первой стоит девочка. Аналогично, сушествуют 5! х 5! способов расположить детей в ряд, если первым стоит мальчик. Таким образом, имеются 2 х 5! х 5! способов расположить детей в ряд для фотографирования.
П РязДеЛ 8.3. Перестановки и сочетания 333 ПРИМЕР 8.25. Сколькими способами можно рассадить 10 человек за круглым столом, если имеет значение только порядок соседей. Существует несколько вариантов решения данной задачи. Первым делом, отметим, что вращение людей вокруг стола не меняет их взаимного расположения, поскольку соседи справа и слева остаются прежними. Предположим, что место за столом уникально. Тогда существует 10! способов рассадить людей за столом. Считаем, что при вращении места остаются теми же, так как соседи не меняются. Существует десять таких вращений, поэтому делим 10! на 10, что дает 9! способов расположить людей за столом, если имеет значение только порядок соседей. Иной подход к решению задачи состоит в том, чтобы сначала усадить одного человека. Этим исключается вращение, а оставшихся 9 человек можно рассадить 9! способами. П ПРИМЕР 8.26.
На книжной полке требуется расположить 15 различных книг по математике, 12 различных книг по физике и 16 различных книг по информатике. Сколькими способами это можно сделать, если а) не существует никаких ограничений? б) все книги по одному и тому же предмету должны стоять вместе? в) все книги по одному и тому же предмету должны стоять рядом, но математические книги и книги по информатике не должны стоять рядом? а) Всего имеется 43 книги, поэтому существуют 43! различных способа расположить их на полке.
б) Предположим, что первыми на полке помещаем книги по математике, книги по физике помещаем вторыми и последними располагаем книги по информатике. Обозначим это расположение МФИ. Существуют 15! различных способов расставить книги по математике, 12! — по физике и 16! — по информатике. Следовательно, имеются 15! х 12! х 16! способов разместить книги. Если первыми поставить на полку книги по физике, затем книги по информатике и, наконец, книги по математике, что можно обозначить как ФИМ, то опять получили бы 15! х 12! х 16! способов разместить книги.
Любая перестановка И, М и Ф даст 15! х 12! х 16! способов размещения книг. Поскольку существуют 3! способа переставить И, М и Ф, то существуют 3! х 15! х 12! х 16! различных способов расставить книги на полке. в) Поскольку книги по физике следует расположить посередине, книги по информатике должны стоять либо первыми, либо последними.
Поэтому единственными возможными конфигурациями являются ИФМ и МФИ. Поскольку для каждой из них существуют 15! х 12! х 16! различных способов разместить книги, то в итоге получаем 2 х 15! х 12! х 16! различных способов разместить книги. П ПРИМЕР 8.27. Сколько существует перестановок букв ш, е,й, г,д, т, а,1, Ь, в которых последовательности букв не образуют слова "тее", кй!и", и "гпа!и"? Например, перестановка с!,д, г,ю,е,1,6,а,т не подходит, поскольку включает сочетание букв "«е". Пусть универсум Б будет множеством всех перестановок букв ш,е, Н,~,д,т,а,т,й. Тогда (У! = 9! = 362880. Пусть Я1 — множество всех перестановок, в которых встречается слово "«е". Пусть Яз — множество всех переста- 334 ГЛЯВЯ В.
Комбинаторика и вероятность новак, в которых встречается слово "Йц", и оз — множество всех перестановок, которые включают слово "гпай". В задаче требуется найти )Я', Г! ог Г! оз! или !Ц вЂ” !эг Оэг 05з1 Но )Яг О Яг ~ 3 оз! = (51! + )ог! + )дз! — !о1 П Яг! — )51 П Яз! — !яг П Яз! + + (дг Г!Ыг Пза!.
Поскольку буквы "ш,е" должны стоять вместе, множество о1 состоит из всех перестановок восьми символов ше, д, г,д, т, а, г, Ь. Поэтому ф1! = 8!. Множество ог состоит из всех перестановок семи символов ш,е, Ыгд, т, а,г, Ь. Следовательно, !ог~ = 7!. Множество оз состоит из всех перестановок шести символов ш,е,г1,г,д,та~Ь. Поэтому фз! = 6!. Множество о, и ог составляют все перестановки шести символов гие,йд,т,а,с, Ь. Поэтому !о1 й ог! = 6! Множество Яг Г1 оз составляют все перестановки четырех символов ш, е, о1д, тасЬ. Поэтому )ог Г! оз! = 4! Множество 5, й оз составляют все перестановки пяти символов ше,г1,г,д,тасЬ. Поэтому )дг Поз! = 5! Наконец, множество дг Поз йаз составляют все перестановки трех символов и~с,дауд,тагЬ.
Поэтому (о1 лог Г1 оз! = 3! и !о1 ~~ ог О оз! = 8! + 7! + 6! — 6! — 5! — 4! + 3! = = 45222, так что )д, Г! ог Г1оз! = )ЕУ! — !ог Ног 0 оз! = = 362 880 — 45 222 = = 317658. Вернемся к задаче выбора президента, вице-президента, секретаря и казначея в группе из 20 человек. Известно, что существуют 20! 16! различных способов сделать выбор. В этом случае избрание Мэри Браун президентом, Джорджа Смита вице-президентом, Джейн Джонс — секретарем и Джо Джексона — казначеем отличается от избрания Джейн Джонс президентом, Джо Джексона — вице-президентом, Джорджа Смита — секретарем и Мэри Браун — казначеем.
Допустим, что вместо выборов президента, вице-президента, секретаря и казначея избирается просто комитет из четырех членов. В этом случае избрание в комитет Мэри Браун, Джорджа Смита, Джейн Джонс и Джо Джексона ничем не отличается от избрания в комитет Джейн Джонс, Джо Джексона, Джорджа Смита и Мэри Браун. Теперь порядок больше не дает различий в способах выбора. При выборе четырех должностных лиц любая перестановка Мэри Браун, Джорджа Смита, Джейн Джонс и Джо Джексона была бы различной, но при избрании комитета они различаются. Поскольку существует 4! перестановки четырех должностных лиц, которые не меняют состав комитета, для нахождения числа комитетов необходимо г1ое! разделить на 4!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
