Введение в прикладную комбинаторику, Кофман А. (984071), страница 17
Текст из файла (страница 17)
(1+ г„!). Полагая в (!8.!2) г, =г,= ... =г„=г, имеем Р'(г, г, ..., г; !) =(1+ г!)"= = !+ С„г!+ С;Гг~! + ... + С„'г'!'+ ... (18.12) (18.13) Если ф (г) — соответствующий денумератор, то 12 «Г «Г*(г, г, ° г' !)=е * =1+ф,!+ф,— 2+ +ф,—,, + ф" — ' ф*, г= 1, 2, ..., ф'Π— ' 1.
(18 14) Сравнение (18.13) и (18.14) дает ф',(г) = г! С'„г'= А'„г'! (18.16) таким образом, искомое число равно А„'. (18.16) Вычислим теперь число размещений г различимых и неупорядоченных объектов по и различимым и неупорядоченным ячейкам при условии, что каждая ячейка занята. В этом случае (18.6) запишется так; « Г Полагая г,=г, ... =г„=г, получаем ю Р" (г, г, ..., г; !) =(е" — 1)"= ~С!( — 1)«е'" л"= 1=О Ю Г О «=Πà Π— и!з(г, и) (в силу (10.61)). (18.19) г О !!8 г"*(г !) = г !+ гг — + + г' — + (18 17) откуда Р'(го г„..., г„; !) =(е" — 1)(е" — 1)... (е' — !).
(18.18) Сравнивая (18.19) с еч', имеем (18.201 ~р", (г) = л! й (г, л) г'. Таким образом, искомое число равно п)з(г, и). (18.21) Если теперь эти г объектов размещаются по л различимым ячейкам с тем условием, что т ячеек заняты, а п — т ячеек пусты, то ;(*,: !-('", ' (!8.22) (=т+ 1, ..., и. Припишем т занятым ячейкам номера от 1 до т (не уточняя, какие именно ячейки заняты). Имеем Р'(г, г, ..., г; !) =С„(е — !) и! 'кч гЧ' — т! 8(г, ги) = т! (и — ги)! 2а г! —, М (г, т) = )~~ — „А„з (г, т). (18.
23) г=О Таким образом, искомое число равно А„э(г, т), (18.24) Отсюда следует рекуррентное соотношение для соответствую- щих чисел а,(и, а): д,(п, а) =д,(п — 1, а)+ гд,,(л — 1, а)+ ... ... +С,'д,,(п — 1, а) (18.26) и д,,,(и, а)=па„(п, а) — пС„'д, „(л — 1, а). (18.27) 119 что обобщает (!8.21). Рассмотрим еще некоторые случаи. Пусть г различимых и неупорядоченных объектов размещаются по п различимым и неупорядоченным ячейкам так, что в каждую ячейку попадает не более а объектов. Запишем Р'(г, г, ..., г; !)=(1+г!+г' — !+ ... + — ) .
(18.25) Пусть г различимых и неупорядоченных объектов размещаются по и различимым и неупорядоченным ячейкам так, что в каждую ячейку попадает не менее Ь объектов; тогда 1 вьгь аь+!(ь+~ «" (г1 г> . ° ., г! ()=( — + + (, ь( (ь+!)! тгз ь-!!ь-!1л =!еы — 1 — — — — — ...
— ( . (18.28) 1! 21 ''' (Ь вЂ” 1)1 Отсюда следует рекуррентное соотношение для йг(п, Ь): Ь,(п, Ь) =пй, !(и, Ь)+ пС~:!Ь -ь(п — 1, Ь). (18.29) Число размещений' ) и неразличимых объектов по и различимым н неупорядоченным ячейкам. Случай (3.1). Это число равно й((г, и) = Са+г-!. (18.30) В самом деле, расположим на одной строке г объектов и между ними поставим и — 1 черточек, соответствующих и ячей- кам (рис. 33). Мы можем теперь рассматривать черточки как объекты.
Число размещений г неразличимых объектов по и ячейкам равно поэтому числу переста- новок п + г — 1 объектов, т. е. Рис. 33. числу (и+ г — 1)! упорядоченных (п + г — 1) -выборок без повторения. Так как п — 1 мест (черточек) фиксированы, а остальные г объектов неразличимы, то (л+ г — 1)1 г й! (г п) = (л !)1г! =Са+ — ° Найдем денумератор, соответствующий размещению г объектов в ячейке 1. Воспользуемся (18.6), учитывая, что коэффициенты при 1" нужно умножить на г! (объекты одинаковы); имеем 01о(гь) 1) = 1+ гь(+ г!1 + ° .. + гУ +...
= (1 — гь() . (18 31) Если рассматривать п ячеек, то б'(г„г„..., г„; () =(1 — г!1) '(1 — гз() ' ... (1 — г„() (, ( ( . ( .32) (18.3 ') Быть может, правильнее употреблять слово «распределение» («роз1- НоппешепЬ) вместо слова «размещение» («р!асешепЬ) в тех случаях, когда объекты или ячейки неразличимы, но с келью сохранения единства мы всегда будем пользоваться термином «размещение». 120 Полагаем 1 — а!! + а',Р + ... + ( — 1)" а„!" = (1 — г,!) (1 — г,!) ...
(1 — г„!1, (18.33) где (18.34) а,'=а,(гн г,, ..., г„), а также 1 1 — а*1+ а 1~ — + 1-! !" а Р ' и где (18.35) р, = р, (г„г„..., г„). (!8.36) Можно дать общую формулу для а"„и 5'„с помощью формулы Бруно. Как показано ранее (см. (!0.5!) и (17.15)), из р !з + У !+ У я + Уз з + ' ' е"н+«н'!з+ж!'!з+ " (18 37) следует у~(па!'''п~)~~Й1Й11Й1(ф)ф)(!') (18.38) Сравнивая (18.37) с (18.39), получаем а„(г„г„..., г„) = ')" Х Й,! ь,! ...
Й.! ( !" ) ' ( я" ) ' ' " ( '" ) " (18 40) где суммирование производится по всем решениям (Й„Й„..., Й„) уравнения Й, + 2Й, + ... + пй„=п. Точно так же 1+ р!!+ р,,! + рз! + ... =е*""РЙ'"'"и ~"+"' (18.41) и, сравнивая это с (!8.37), получаем Рл(г!~ гм '''ю га)=,~~а !Й! 1Й 1!! ! ) '( я ) '''( "') "° (1842) Как пример выпишем формулы (!8.40) и (18.42) при п=1, 2, 3, При о=1, Й,=! а", (г,) = ( — 1) ° ( — г,) = г„Р; (г,) = г,. (18.43) 12! где суммирование производится по всем решениям (Й„Й„..., Й„) уравнения Й, + 2Йз+ ... + пй„= п. Запишем также 1 — а',!+а,'!' —...
+( — 1)" а'„!"=е '" '~' ' "' "' " "', (18.39) При и =2, (йо !22) = (2, 0) и (йо й2) =(О, 1) 2( 1~ 2) ( ) [2( 1) + 3 ] 3( 2+ 1)' (18.44) При и = 3, (й1, йм йз) = (3, О, 0), (1, 1, 0), (О, О, 1) 2 22 2122 = — — — +— 3 2 6 ~ з з ~ 21 2122 22 1 22 2122 21 52(1' 2' з) !31+ 2 + 3! 3 + 2 + 6 (18.45) (18. 45) Наконец, обозначая через 11„'(г„г„..., г„) денумератор, соответствующий размещениям г неразличимых объектов по п различимым (указанным) ячейкам, имеем ~~2( 1~ 2 ~ 2) = ~1,~~ ~ ~,, '(+) ' (+) ' .
° . [ — „" ) ". (18.47) Ввиду (18.43) — (18.45) получаем 1(1 (21) = 2„11;(2„22) = г, + 211 2(з(21 22 гз) = 2гз + Зг1г2 + г21 (18.48) Денумератор, соответствующий всем возможным случаям, получается из (18.32) при г, =г2= ... =г„=г: 6'(г, г, ..., г; !) =(1 — г!) "= ~ С;+„12У, (18.49) Р=О откуда 6,(г)=С,',+, 1г', 2=1, 2, 3, ..., (18.50) =21!(1 — 21!), 1=1, 2, ..., п. (18,51) Для всех ячеек Н (21~22~ 2 гз',!)=2122 гз! (! — 21!) ° (1 — 22!) ° (1852) !23 т.
е. опять приходим к (18.30), Найдем теперь денумератор, соответствующий размещениям г неразличимых объектов по и различимым и неупорядоченным ячейкам при условии, что все ячейки заняты. Для фиксированной ячейки находим аналогично (18.31) Н!11(21, т)=21!+гУ+ ... +21!" + ... = Когда ячейки конкретно не указываются, имеем Н" (г, г, ..., г; 1) =г"1" (! — г1) ". (18.53) Разлагая (! — гг) ", запишем Н (г, г, ..., г; 1)= ~ С„":1гУ, (18.54) откуда Н, (г) = С,":1г', г = и, и + 1, (18.55) таким образом, искомое число равно М(г, и) =С,":~1. (!8.56) Наконец, выпишем денумератор, соответствующий размещениям г неразличимых объектов по и различимым ячейкам при том условии, что в каждую ячейку попадает не более одного объекта.
Для фиксированной ячейки 1,"„(г,; 1)=1+ г,.1, 1=1, 2, ..., и; (18.57) Для всех возможных случаев 1" (г, г, ..., г; 1) =(1+г1)"=~С'„г'!', (!8,59) откуда 1, (г) = С'„г', (18.60) следовательно, У(г, и) =С'„. (18.61) Число размещений г различимых и упорядоченных объектов по и различимым и упорядоченным ячейкам. Случай (2.2).
Это число равно !и+ г — !)! У (г, и) = И С„„, и (18.62) Докажем это. Размещаем г неразличимых объектов по и различимым и неупорядоченным ячейкам. Затем, рассматривая объекты в каждой ячейке как различимые, переставим их г! способами. Тем самым все возможные случаи рассмотрены и искомое число равно числу из (18.30), умноженному на г!.
Если при этом потребовать, чтобы все ячейки были заняты, то точно так же из (18.56) получаем Н(г, и) =г! С„":~~. (18.63) !23 для и ячеек 1'(г„г,„..., г„; 1)=(1+г,г)(1+гД ... (1+г„1). (18,38) Число размещений г различимых н неупорядоченных объектов по и неразличимым ячейкам. Случай (1.3). Это число равно )т' (г, а) = о (г, а), (18.64) где о (г, п) = ~ з (г, й) (18.66) н через з(г, а) обозначены числа Стнрлннга второго рода, определяемые формулой (!0.6). Числа 8(г, и) называют иногда кумулятивными числами Сгирлинга второго рода.
Докажем (18.64). Рассмотрим сначала случай, когда каждая ячейка занята. Число таких размещений равно числу, полученному в (!8.21), деленному на и), т. е, з(г, л). Так как каждую пустую ячейку можно выбирать только одним способом, то, суммируя з(г, й) от 1 до а, получаем искомое число. Как мы уже указали, в случае, когда нн одна ячейка не пуста, это число есть з(г, л). (! 8.66) За недостатком места н чтобы сохранить элементарность изложения, мы ограничимся рассмотренными выше случаями. Более полные сведения можно получить нз [36). УПРАЖНЕНИЯ 18А.
Найти число размещений 7 различимых н неупорчдоченных обьектов по 5 различимым н неупорядоченным ячейкам. Каков соответствующий денумераторр 185. Тот же вопрос, что н в упражнении !8А, но для случая, когда 3 объекта попадают в ячейку 1, 2 объекта — в ячейку 2, 2 объекта — в ячей. ку 3, 3 объекта — в ячейку 4, О объектов — в ячейку 5. 18В. Найти число размещений 7 различимых и неупорядоченных объектов по 5 различимым и неупорядоченным ячейкам при условии, что в каждую ячейку попадает не менее одного обьекта. 18Г. Тот же вопрос, что и в упражнении !8В, но с одним нз условий; а) каждая ячейка занята, б) 2 ячейки пусты, 3 ячейки заняты, в) 3 ячейки пусты, 2 ячейки заняты, г) не более 3 объектов в каждой ячейке, д) не менее 2 объектов в каждой ячейке, кроме двух пустых.
Указать соответствующие денумераторы. 18Д. Посчитать число размещений 9 неразличимых объектов по 4 различимым и неупорядоченным ячейкам и указать соответствующий денумератор. 18Е. Тот же вопрос, что и в упражнении 18Д, но с одним из условий: а) не менее одного объекта в каждой ячейке, б) не более 4 объектов в каждой ячейке. 18Ж. Найти число размещений 8 различимых и упорядоченных объектов по 3 различимым и упорядоченным ячейкам. 183. Найти число размещений 8 различимых и неупорядоченных объектов по 3 неразличимым ячейкам. !24 18И.
42 пассажира садятся в автобус, который делает 7 остановок. Подсчитать все возможные ситуации прн условии, что на каждой остановке сходят в точности 6 пассажиров. 18К. Сколькими способамн можно разместить 30 шаров в !00 ящиков прн следующих условиях: а) шары одинаковы; б) шары различимы, порядок шаров в каждом ящике существен; в) шары различимы, порядок шаров в наждом ящике несуществен. В каждом случае в ящике, содержащем шары, нх точно 6.
18Л. Сколько возможностей существует для того, чтобы среди 30 человек оказался по крайней мере один, родившийся ! января) 18М. Сколько существует возможностей для того, что среди 6 человек в точности трое родились во вторник? 18Н. Игрок в бридж объявляет, что среди 13 его карт есть туз. Подсчн. тать число возможных случаев, когда у него в точности 2 туза. 180. Пусть каждая нз 5 семей состоит нз 4 человек. Предположим, что 6 нэ этих 20 человек больны скарлатиной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
