Введение в прикладную комбинаторику, Кофман А. (984071), страница 16
Текст из файла (страница 16)
Например, если это отношение эквивалентности обозначить через =, то (1427) ~(1472) ~(1274) (!247) ~ (1724) (1742). (17.86) Так как, очевидно, для г-цикла можно образовать г — 1 ему эквивалентных, то для получения искомого денумератора доста- 110 точно в денумераторе Р*„(см. (17.4)) заменить каждое г„на и,/(г — 1)1: Р„(ио и.„..., и„) = )~~ ь ! ( —,) ' (ф '...
~ — „! ) ", (17.87) й,+2й,+ ... +ий„=и. (17.88) Следовательно, подставляя в (17.8), имеем 11',(и,) = ио й;(и„и„и,) = и', + Зи,и, + и,, И,(и„и,) = и', + и„ы,(ион„и, и,) = и',+би;и,+3и;+4и,и,+и4, ы, (и„и,„и,, ич, и,.) = и', + ! Ои',и, + 15и, и,' + 10и',из + +!Ои,из+ 5и,из+ им (17.89) й; (и„и„и,, и„из, и,.) = и', + 15и',и, + 45и';и! + 20и',и, + + 15и,,'+ 60ии и, + 15ии, + 1Ои,-'+ 15ии, + бииз+ и . Сравнивая (17.87) и (10.54), замечаем, что коэффициенты полиномов от иь ! = 1, 2, ..., п, с помощью которых образуется этот денумератор, совпадают с коэффициентами полнномов Белла, если в (10.54) заменить у~~~, й = 1, 2,..., и, на 1, а ин! на и„1=1, 2,...,п, Из (! 7,87) можно вывести ряд соотношений, Аналогично (17.17) имеем еаи емн~-и,ни!-;интмч- ., ! Я*г, Я* с1 0 г = 1, 2, ...
(17.90) Обозначим Л"„(и) =К(и, и,..., и) (!7.91) денумератор, не учитывающий длины циклов, а только их число. Тогда в силу (17.90) имеем ели еи и-~я2ыичз~.ь,.ч еи (е !) иь (ес !р (17.92) ь! ь=О Положим Уь(1) =,~, Й О, 1, 2,, (17.93) Легко убедиться, что Уь удовлетворяют дифференциальному уравнению ((й — й) Уь(1) = Уь-~ (1), /г 1, 2, 3,..., (!7.94) для которого 2ь(1)= )~~ й(п, й) — '„, = — е"< ы, (3(, й))" — з(и, й), и=О 1=0, 1, 2, 3,..., (17.95) (з(и, й) — числа Стнрлинга второго рода) — также решения.
1!! Так как У'ь(0) =21(0), то Ух(!)=Е](!), й=О, 1, 2, ..., (!7.96) как решения одного н того же дифференциального уравнения с одинаковым начальным условием. Таким образом, о ч ех"'= )~~ — „, ~) з (л, й) и, (Л')' — Л;, г=1, 2, . (Л )о . 1. (!7 97) Л"„(и) = ~~ й(п, й) а~. (17.98) Тем самым Л'„(и) легко выписываются с помощью чисел Стирлинга второго рода (таблица ! 0.2). Для первых значений кс Л[(и) = и, Лз (и) = и + Зи'+ и' Л] (и) = и + и~, Л] (и) = и+ Уи'+ Ои'+ и', Лз (и) = и + 15и'+ 25и' + 10и' + и' (17.99) Л! (и) = и + 31и'+ 90из+ 65и4+ 15и'+ ие В силу (17.96) и (17.98) имеем Л„'ч.~ (и) = и[Л*(и) + 1]", (Л')' — ' Л;, г=1, 2, ...; (Л')' — 1.
(!7.!00) Разлагая по формуле бинома, получаем Л](и) = и, Л] (и) = и [Л](и) +! ] = и"-+ и, Лз (и) = и [Л] (и) + 2Л] (и) + 1] = и [и'+ 2и + и + 1] = = и'+ Зиз + и, (17. 101) При этом, как указал Айткен, можно использовать несколько видоизмененный треугольник Паскаля ([36]). Приведем теперь денумератор для цикловых классов подстановок, обладающих й циклами, длина которых не фиксируется, порядок элементов в циклах не учитывается, и не содержащих 1-циклов: Г„'(и) =!1;(О, и, ..., и). (17.
102) Применяем экспоненциальное г-преобразование: егп — е» (е'-~-~! — е~ !л'-м (Г')' — ' Г,*, г= 1, 2, „(Г')' — 1; (17.103) (Л")' — Л;, г=1, 2, ..., (Л')' — ' 1 ° !!я Разлагая обе части (17.103) по степеням 1, имеем Г (и) = )~~ С Л„е(и)( — и) (17.104) и аналогично Л„(и) = ~~', фÄе (и) и .
(17.105) Полагая Г;(и) = ~ у(п, й) и', (17. 106) получаем соотношение, подобное (17.60); у(п, й) называются присоединенными числами Стирлинга второго рода. Принимают у(0, 0) = 1, у(п, 0) = О, и ) О. В таблице 17.2 приведены числа у(п, )е) до и = 8. Таблица 17.2 Таблица присоединенных чисел Стирлинга второго рода до и = 8 т(л, е) е ! 15 105 490 105 Из (17.103) или (17.104) получается рекуррентная формула Г„"+1(и) = и ((Г*(и) + 1)" — Г; (и)], (Г*)' — ' Г,", г = 1, 2,..., 1 — ' (Г*)'. (17.107) Аналогичные результаты можно получить и при других ограничениях на классы подстановок, Различные ограничения иа г-циклы могут привести к денумератору вида ~'(а~ """ае)=ХЬ1.1"' ° 1( — ")'( — )' "(,"и')' (17.108) Например, если фиксировать два первых элемента каждого цикла, то в (17.108) сс„= г — 1.
113 у(). ь) у(2, /г) у(8 е) у(4, л) у(5, л) у(6, л) у (7, л) у (8, Гг) 3 1О 25 56 119 УПРАЖНЕНИЯ 17А. Найти решение уравнения йг+ 2йз+... + пй = и прн и = 7, 9, 1О, 17Б. Найти денумератор цнкловых классов Р„'(з) прн л =? по формуле (17.4). 17В. Решить упражнение 17Б с помощью рекуррентной формулы (!7.23). 17Г. То же, что н в упражнении !7В, но с использованием (!7.38).
17Д. Указать денумератор П„*(з) для подстановок с четырьмя циклами без учета нх длины. Выписать его в явном виде для л = 5, 6, 7. 17Е. Выписать денумератор Ь'„(а) классов подстановок с тремя циклами произвольной длины н не содержащих 1-цнклов (беспорядки в точности с тремя цнкламн) прн и = 5, 6. 17Ж. Вычислить присоединенные числа Стнрлннга первого рода прн л=9. 173. Используя (17.72) н (17.73), найти денумераторы четных н нечетных подстановок прн а = 7. 17И. По формуле (17.87) найти Ит(ип из, ..., ит).
17К. С помощью (17.98) выписать П~(и, и, ..., и). 17Л. Вычислить присоединенные числа Стнрлннга второго рода для а=9. $18. Классифицирование. Схема размещения элементов по ячейкам Под классифицированием понимают распределение объектов из некоторой совокупности по классам, причем каждый объект принадлежит точно одному классу (некоторые классы могут быть пустыми). Объекты из одного и того же класса не обязательно считаются эквивалентными, т.е.
рассматриваемое здесь понятие класса шире понятия класса эквивалентности в теории множеств. Физическая интерпретапия классифипнрования — это «схема размещения» нли «размещение» объектов по ячейкам; каждая ячейка соответствует классу. Во избежание недоразумений, мы вместо классов будем говорить о ячейках '). В этом параграфе мы будем интересоваться различными возможными размещениями г объектов по а ячейкам в основном одного из следующих видов: (1.!); объекты различимые и неупорядоченные, ячейки различимые и неупорядоченные; (1.2): объекты различимые и неупорядоченные, ячейки различимые и упорядоченные; (1.3): объекты различимые и неупорядоченные, ячейки неразличимые; (2.1): объекты различимые и упорядоченные, ячейки различимые и неупорядоченные; (2.2): объекты различимые и упорядоченные, ячейки различимые и упорядоченные; ') Под множеством понимают совокупность различимых объектов, здесь же будут рассматриваться совокупности не обязательно различимых объектов, (2.3): объекты различимые и упорядоченные, ячейки неразличимые; (3.1): объекты неразличимые, ячейки различимые и неупорядоченные; (3.2): объекты неразличимые, ячейки различимые и упорядоченные; (3.3): объекты неразличимые, ячейки неразличимые.
Приведем примеры этих размещений для случая восьми объектов и пяти ячеек. Случай (1.1) (Ас( )ю)еео)в! )Ас) )т)еог(в) )сА)в)еео) )т) 1 2 3 4 5 1 2 3 4 5 1 5 4 2 3 (а) (Р) (у) (а) (р) (у) Случай (1.2) )Ас) !10)Рео)В! !Ас) )и)еоР!В! )сА)в)еРо! 110! 1 2 3 4 5 1 2 3 4 5 1 5 4 2 3 (а) (Р) (у) (а) = (()) ~ (у) Случай (1.3) ! АВ! 1/в( Рео(в) )сА! Рео) 1В)!О! !)в ! В(Ас ! Рео( (а) (Р) (а) (р) (у) (у) Случай (2.1) ~~с~ ~юа~геа~в~ ~яс~ а~ ~в~рта~ ~ся~ЗЗ4!крв~ 1 2 3 4 5 (а) 1 3 2 5 4 1 2 3 4 5 (й) (у) (а) ~ (р) Ф (у) Случай (1.3) не следует смешивать со случаем (1.1). Подмножество ячеек в (1.1) может быть образовано, например, ячейками 1, 2, 4, 5. В случае (1.3) понятие подмножества не имеет смысла. В случае (!.1) размещение (а) описывается так: ячейка 1 содержит А и С, ячейка 2 пуста, ячейка 3 содержит 0 и 1, ячейка 4 содержит Е, Р, б, ячейка 5 содержит В.
В случае (!.3) размещение (а) описывается так; одна ячейка содержит А и С, одна ячейка пустая, одна ячейка содержит Е, Р, 6, одна ячейка содержит 1) и 1, одна ячейка содержит В. Случай (2.2) )АС! )!О) РЕО)В( (АС ~ !О! )В(РЕО ! )СЛ! )!О(РОЕ)В! 1 2 3 4 5 (а) ! 3 2 5 4 1 2 3 4 5 (Р) (а) ~ ф) Ф (у) (у) Случай (2.3) ~~~~~~е 3В3 /АС/ / /В/ ЕЯ/ /СА/ / /~ЙЕ/ / (а) (й) (а) 9) ~ (у) (у) О случаях (2.3) и (2.1) следует сделать те же замечания, что и о случае (1.3). Случай (3.1) )АА! )АЛ)ААА!А! )ААААА! (А)ААА~ )А) )ААА)ААА)А! 1 2 3 4 5 1 3 2 5 4 1 2 3 4 5 (а) Ф) (у) (а) ф) ~ (у) Случай (3.2) )АА! (ЛА)ААА)А! )ЛА)АА/ )А)ААА! )А! ~ААА~ААА)А! 1 2 3 4 5 1 3 2 5 4 ! 2 3 4 5 (а) (Р) (у) (а) ~ (Д) М (у) Случай (3.3) !АА! )АА)ААА)А! )А! (ААА)АА)АА! )А! )АААА)АА!А! (!)) (а) ф) Ф (у) (у) (а) й!(г, и) =л'.
(18.1) В самом деле, пусть г объектов перенумерованы от ! до г. Объект с номером 1 можно поместить в н ячеек в точности п способами, объекты с номерами 1 и 2 — в точности и' способами, ..., г объектов — в точности и" способами, 116 Установим теперь формулы, дающие числа М(г,н) различных размещений г объектов по и ячейкам для некоторых случаев, указанных выше.
Число размещений г различимых и неупорядоченных объектов по н различимым и неупорядоченным ячейкам. Случай (1.1). Это число равно Найдем теперь денумератор таких размещений, что некоторое число объектов попадает в заданную ячейку, а затем — то же для фиксированного множества ячеек. Пусть !р, (г„г,, ..., гл) — денумератор, дающий число объектов, которые могут быть помещены в ячейки с номерами 1, 2, ..., и, причем г1 соответствует ячейке 1, ! = 1, 2, ..., и. Очевидно, !Р1(г!' г2' ' ' '' гл) г! + г2+ ' ' ' + гл' (18.2) ибо один объект можно поместить в каждую из и ячеек. Для двух объектов !р,*(г„ гм ..., гл) = (г, + г, + ...
+ гл)', (18.3) для г объектов !Рг(г!' г2' ''' гл)=(г!+г,+ ° +г„)'. (18.4) Применим экспоненциальное преобразование: л ! Р (г!ю гхэ '' гл ~) ~~(г!+г2+ ''' +гл) 1=2 =Е ! 2 "' ° =Е' Е2 ... Е 1л .!.л .! ... 1-2 ! 1 л ! л 1 л = РН! (гп ~) ~22! (г2 ~) ' ' ' ~(л! (гл' ~) (18.5) ДЛЯ ЯЧЕЙКИ 1 ИМЕЕМ Р21! (г1! 1) = е" 1 = 1 + г!! + г2 — ! + ... + г", — „+ ... (18.8) С другой стороны, можем записать (см. (7.102)) (18.8) Это число получено в (3.34). Из 2Г Р'(г, г, ..., г; 1) ='5'и'г" — ', =е ' г! (18.9) г=о 141 где суммирование производится по всем целым неотрицательным числам гь гм ..., г„таким, что г! + г, +...
+ г = г. Отсюда следует, что число таких размещений г различимых и неупорядоченных объектов по и различимым и неупорядоченным ячейкам, что г! объектов попадает в ячейку 1, г2 объектов— в ячейку 2, г„объектов — в ячейку и, равно г! !2! 22! '''! гл! следует ф (г, г, ..., г) = и г, т. е. (18.1). Применим (18.6) к более сложным случаям. Подсчитаем число размещений г различимых объектов по л различимым и неупорядоченным ячейкам при условии, что в каждую ячейку может попасть не более одного объекта. В этом случае в силу (!8.6) (18.10) Р;(г,; !) = !+ а! (18.!1) и г" (го г „..., г„; !) = (1 + г!) (1 + гГ!) ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
