Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 63
Текст из файла (страница 63)
Осталось рассмотреть две буквы "п". Как и предыдущих случаях, каждое размещение букв "п", которое оставляло все прочие буквы на своих местах и рассматривалось как уникальное, теперь рассматривается как одно и то же размещение. Поскольку существуют 2! способов размещения двух "п", то для подсчета количества размещений, когда две буквы "п" не различаются, нужно разделить еще на 2!. Таким образом, получаем 11! 4!4!2! различных размещений. Заметим, что делая буквы неразличимыми, мы игнорируем их порядок, как это было в сочетаниях.
ТЕОРЕМА 8.58. Пусть множество о содержит и объектов к таких различных типов, что имеется пг неразличимых объектов типа 1, пз неразличимых объектов типа 2, пз неразличимых объектов типа 3 и, вообще, п, неразличимых объекта типа г. Пусть Р(п;п,,пз,пз,...,пь) — количество различных размещений элементов множества 5. Тогда Р(п; пы пз,..., пь) = С(п, п1)С(п — пы пз) С(п — п1 — пз, пз) С(п — п1 — пз — — пь ы пь) п! п1)п2)пз! . пь! ДОКАЗАТЕЛЬСТВО. Рассмотрим первое уравнение. Имеется и мест, которые можно заполнить элементами из 5. Существует С!п,п,) способов выбрать места для п1 неразличимых объектов типа 1. Если эти места выбраны, то для заполнения останется п — п1 мест, поэтому имеются С(п — пы пз) способов выбрать места для пз неразличимых объектов типа 2. Если объекты типа 1 и типа 2 выбраны, то для заполнения остается и — п1 — па мест, поэтому объекты типа 3 РЯЗДЕЛ б.б. Обобщенные пересо1вноеко и сочетания 355 можно разместить С(п — и, — из, пз) способами.
Аналогично, объекты типа 1 для 2 < 1 < й можно выбрать С(п — и1 — пз — пз — — п, 1, и,) способами. Используя комбинаторный принцип умножения, имеем С(п,п1)С(и — и1,пз)С(п — п1 — из,пз) ..С(п — п1 — п2 — .. — пь 1,пь) способов выбора различных размещений элементов из 5. Чтобы показать, что п! Р1™ 1 2 ° ° ПЬ) п1!п2!пз! .. пь! воспользуемся рассуждением, которое использовалось неоднократно. Сначала пред положим, что все и объектов из Я различны. Если это так, то имеется и! способов разместить данные объекты. Для 1 < 1 < Ь, и, объектов являются неразличимыми.
Поэтому способы расположения таких объектов, при которых остальные объекты остаются на своих местах, неразличимы. Поскольку имеется и,! таких расположений, то для нахождения количества различных размещений, когда все и, объектов типа 1' являются неразличимыми, необходимо и! разделить на п;! для каждого 0 Это дает и'.
и1(и2!пз! .. пь! ' что и требовалось доказать. ПРИМЕР 8.59. Предположим, что 12 книг, включающих 4 одинаковых учебника по математике, 6 одинаковых учебников по информатике, 2 одинаковых учебника по химии, следует расставить на полке. Сколькими способами это можно сделать? Используя предыдущую теорему, имеем 12! Р(12;4,6,2) = — = 13660.
4!6!2! ПРИМЕР 8.60. Сколькими различными способами можно расставить буквы в слове зиссеедеН? Девять букв образуют пять типов неразличимых объектов, включающих: (!) букву в, (2) букву и, (3) два вхождения буквы с, (4) три вхождения буквы е и (5) два вхождения буквы Н. Следовательно, количество неразличимых объектов равно 91 Р(9;1,1,2,3,2) = ..., = 15120.
Заметим, что типы, состоящие только из одного объекта, не влияют на конечный результат. Поэтому следует рассматривать типы, содержащие более одного объекта. П Теперь обобщим биномиальную теорему на случай нахождения коэффициентов разложения (х1+ ха+ хз + . + х )". Рассмотрим (а+ Ь+ с)" = (а+ Ь+ с)(а+ 6+ с)(а+ Ь+ с)(а+ Ь+ с). Для нахождения коэффициента при а62с необходимо найти все способы выбора а, двух 6 и с, где буквы выбираются из каждого из сомножителей.
Возможные 366 ГЛАВА 8. Комбинаторика и ввроятнооть варианты: аЬЬс, сЬЬа, аЬсЬ, сйаЬ, ЬаЬс, ЬсЬа, ЬЬас, ЬЬса, саЬЬ, асЬЬ, 6асЬ, ЬсаЬ. Но это только размещения а, двух 6 и одного с. Таким образом, количество размещений, которое является коэффициентом при абгс, равно 4! Р(4;1,2,1) = — = 12. 1!2!1! Аналогично, коэффициент при Ьгсг равен 4! Р(4;0,2,2) = —... = 6. ТЕОРЕМА 8.61. Для заданного положительного числа п и! (х1 + хг + хз + + х,„)" = ~~' х1'хг'хз' х„,, П1 П2)ПЗ! ' ' ' Поа ° где сумма взята по всем неотрицательным целым числам П1,пг,,и„„таким, ЧТО П1+Пг+ИЗ+ +П = П. ДОКАЗАТЕЛЬСТВО. Поскольку (х1+хг+ . +х )" = (х1+хг+ +х )(х1+ хг+ +х ) (х1+хг+ +х ), то каждое слагаемое в разложении получено путем выбора х1 из каждого сомножителя в произведении и их перемножения.
Для нахождения коэффициента при х",'х"'х"' х"- необходимо найти все возможные способы выбора х1 в количестве п1, хг в количестве пг, ... и хкк в количестве и , Но это есть не что иное, как число размещений х1 в количестве п1,хг в количестве пг, ... и х в количестве и , которое равно П1 Р(п; п1, пг, пз,, п,„) = И1 И2 ПЗ '''Пт! ПРИМЕР 8.62. Найдем коэффициент при аЬгсз в разложении (а+ 6+ с)о. Этот коэффициент равен 6! Р(6; 1, 2, 3) = = 60.
1!2!3! ПРИМЕР 8.63. Найдем коэффициент при а Ь с в разложении (2а+ 36+ с) . Слагаемое имеет вид Р(8;3,2,3)(2а)з(36)гс = 560 2 3 а Ь с = 4320азбгс поэтому коэффициент равен 4320. Предположим, что имеются семь различимых шаров, и требуется положить три шара в первую коробку, два шара — во вторую и два шара — в третью коробку. Сколькими способами можно это сделать? Существует С(7,3) способов выбрать три шара для первой коробки. После того, как шары выбраны, остается четыре шара, два из них выбираются для второй коробки. Для этого существуют С(4,2) способов. Наконец, остается два шара, которые мы кладем в последнюю коробку. РЛЗДЕЛ б.б.
Обобщенные перестаноени и сочетания 357 Это может быть сделано С(2,2) или одним способом. Таким образом, количество способов размещений шаров равно С(7,3) С(4,2) . С(2,2). Но по теореме 8.58 это равно Р(7;3,2,2) = 7 Как видим, существует связь между размещениями неразличимых объектов и разбиением множества, что, по сути, мы и делали с шарами и коробками. Для того, чтобы выявить эту связь, рассмотрим следующий пример.
Предположим, что имеются два красных, три зеленых и четыре синих шара, которые отличаются только цветом. Требуется найти все возможные различные размещения данных шаров. Пусть в!, вг, вз, за, ею за, вт, зв~ вд — позиции, в которые шары могут быть помещены. Допустим, красные шары располагаются в позициях вг и вт. Отождествим такое размещение с помещением вг и вт в коробку В. Предположим, что зеленые шары находятся в позициях з!, зз и вд. Отождествим это с помещением в,, вз и вд в коробку С.
Предположим, наконец, что синие шары располагаются в позициях з4, вз, ва и зв. Отождествим это с помещением за, вв, зс и вв в коробку В. Обратно, если в! и вд помещены в коробку В, вг зт и вв — в коробку С, а вз, вв, зз и вв — в коробку В, мы отождествим это с помещением красных шаров в позиции з! и зд, зеленых шаров — в позиции вг, вт и вв, а синих шаров — в позиции вз, вз, вз и вв.
Таким образом, задача о размещении неразличимых шаров свелась к задаче о помещении шаров в коробки. В общем случае справедлива следующая теорема. ТЕОРЕМА 864. Пусть С(и;пыпг,из,...,и ) — количество разбиений множества Я, содержащего и элементов на т множеств В!, Яг, Яз, ... и Я„„содержащих и!, иг, пз, ... и и элементов соответственно. Тогда и! С(п;из,пг,пю.,.,и, ) = Р(п;п1,иъггз,...,и, ) = п!!пг!пз! .п„,! ДОКАЗАТЕЛЬСТВО. Существуют С(п,п!) способов выбора элементов для Я!. Как только эти элементы выбраны, остается п — и! элементов, из которых необходимо выбрать пг элементов для Вг. Последнее можно осуществить С(п — и,, пг) способами. Если эти элементы выбраны, остаются п — и! — иг элементов, из которых необходимо выбрать из элементов для Яз.
Предположим, что множества Я!, Вг, Яз, ... и Я, ! уже выбраны, тогда для выбора п, элементов для множества Я, остается и — и! — иг — — и, ! элементов, Этот выбор можно осуществить С(п — и! — иг — — п, !,г!,) способами. Используя принцип умножения, получаем С(п; п!,..., п,„) = С(п, и!)С(и — п!, иг)С(и — и! — иг, пз) ...С(и — п! — . — пь !,пь) = и! п!.пг.пз.. ' ' п~п ! ! !...
! = Р(п; и!, иг, пз,..., п ). Заметим, что сочетание С(п, й) = С(п; и, п — й) является частным случаем разбиения п-элементного множества на множество, содержащее й элементов (которые 358 ГПАВА 8. комбинаторика и ввроятность мы выбираем), и множество, содержащее и — й элементов (которые остаются). Важно отметить, что множество разбивается в последовательность подмножеств с заданным количеством элементов. При этом мы подсчитывем количество разбиений множества в последовательность подмножеств заданных размеров. Один из способов убедиться в этом — заметить, что С(п, к) = С(п; й, и — й) — количество способов выбрать й объектов из и объектов.
Мы не включаем сюда количество способов выбрать п — й объектов и, следовательно, оставляем к объектов, что также дает разбиение множества В, содержащего п объектов, на подмножества, содержащие к и и — к объектов. Для этого также существуют С(п; и, п — к) способов, поэтому существуют 2С(п;)с,п — й) способов разбиения множества В на множества, содержащие й объектов и и — к объектов. Другой способ представить себе содержание теоремы — это рассматривать ее как описание раскладывания различимых шаров в разные коробки.
ПРИМЕР 8.65. Сколькими способами можно выбрать четыре набора по пять карт из колоды, содержащей 52 карты? По сути, колода разбивается на пять множеств; четыре набора по пять карт и 32 оставшихся карты. Поэтому количество таких наборов равно 52! С(52;5,5,5,5,32) = 5!5!5!5!32! ° УПРАЖНЕНИЯ 1. Сколько различных размещений можно образовать, используя буквы в слове зесеедед? 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
