Введение в прикладную комбинаторику, Кофман А. (984071), страница 15
Текст из файла (страница 15)
гг (17.29) !02 Эта формула позволяет вычислить Р„'+!, зная Р;, г= 1, 2,..., и, и полагая РО=1. Продифференцируем (!7.17) по г,: Дадим примеры применения формул (17.23) и (!7.29), НайДем Р4 (г ' гз гз, г4) считан иавестными Рз(гр гз~ гз) Рз (г1 гз) Р",(г,) и Р„': Р4 (гр гр гр г4) АР)Рз згр гр гз) + Азг«Р~ (гр гз) + + Азг Р; (г1) + Азг Ро = г1 (г1 + Зг гз+ 2гз) + Згз (г'-, + гз) + +бг,гз+бг =г4+бг',г +Зг +8г,г +бг4.
(17.30) Пример на формулу (!7.29): О Р, "(го г„г,, г„г,) = 20г'-, + 20г„(17.31) Аз 3! — 'Р',(гр г,)= —,(г',+г,)=20(г';+г,). (17.32) Обозначим через Р"„(гр гз,, г„~ г,) сумму членов в р*„(гр гр ..., г„), содержащих г,. Интегрируя (17.29), имеем "(г '" "~")= «г А' = —" ~ Р'„,(гр г„..., г„)4зг, (а=0, 1, 2, ..., п). (17.33) 0 Эта формула дает способ рекуррентного вычисления Р'(г, гз,..., г), исхоДЯ нэ Р*(гр г„..., г), г(п, ПолУчим этим способом Р4 (гр гз, гз г4).
Р«(гр г«, гз, г4~ г4) 4 ) Рз "(г4 = — г4 = бг4, о Аз ! 4 ° 3 ° 2 Р1(г1 гз г» г4!гз)= 3 ! Р1(г1) "гз = 3 г1гз=8г,г„(17.35) о 4 ( Р 2' 3' 4 ! 2) «2 «ю = — ) Р"(г, г)4(г = — (г'+г)4!гз=бг'г +Зг,', (17.36) 2 з о о и Р4 (го гм гз, г4 ~ г,) = А,' ) Р, (гр гм г,) 4зг, = 0 «~ 4 ~ (гз + Зг,гз + 2гз) 4(г, = г4+ бг',гз + 8г4гз (17 37) 0 Тогда Р4(гз гз гз г4) О Р4(гр гм гм г41г«) (17 38) 103 г 1 8 га.', ) 0а1сп~анаапа ннаааа (гдйаб или й,+й,+ ... +й,=з, й +2й + + й (1~(з(~а). (17.42) Денумератор классов, содержащих в точности з циклов (длина которых не фиксируется), можно получить с помощью (17.16) и (17.17). Для этого полагаем П;,(г)=Р1,(г, г, ..., г) (17,43) и согласно (17.17) еп з езп+Р/з+зтз+" ) (17.44) где в 5 суммирование производится по правилу: сумма подоб- Г ных членов равна одному из них.
Например, Р4(г! гз гз~ г4) = (г", + бг',г, + 8г,гз) + (бгзгг + Зггз) (- Згрз+-бг„= = г4+ (бгзгз+ бг',гз) + Зггг ~ (Зг,гз ч- 8г,гз) + 6г, = г4+ бгзгг + Зг- '+ Зг,гз + бг . (17.39) Можно сказать, что 5 есть объединение членов в выражениях Г Р'(г, г, гз, г4~ г ), В общем случае (17.38) имеет вид Р (г гм г ) З~ п(г~' гз~ ' ° ~ гс~гг). 4зс~ реЮ (17.40) зуааапганаана Найдем теперь де- (4даР,О) нумератор подстановок разлагающихся в проРис 29. изведение з циклов (без учета числа элементов в цикле).
Рассмотрим, например, подстановки пяти элементов. Сколько существует цикловых классов (йь йз, ..., Йз) с числом циклов, равным 37 Нетрудно увидеть, что таких классов два (рис. 29): (1, 2, О, О, 0) и (2, О, 1, О, 0). Общая задача сводится к решению системы линейных уравнений: й,+йз+ ...
+А„=з, й +2й + й (1< ~п) (1741) Так как з !и — =1+ — + — + ° ° ° — з гв4 0 (1 < 1, (17Аб) то епм ее !п Пгп ~н и!п1!)и о 1 — (1 !) = 1 + г! + г (г + 1) 2 ! + г (г + 1) (г + 2) з, + ... = ') О =1+ ~~ г(г+ 1) .. ° (г+л — 1) — ), и 1 или гп 1+ П!!+ П2г'/2+ ... + Пп ! + =1+ г!+г(г+!) —,+ ... + г(г+ 1) ... ... (г+ и — !) —, + ... (17.47) Окончательно для П'(г) имеем П;(г)=г(а+ 1) ... (г+ л — 1)> и=1, 2, ... (17.48) Пример. Пз(г) =г(г+ 1)(г+2)(г+3)(г+ 4)= гз ! 1Огз,+ 35гз+ 50г'+ 24г. (17.49) Итак, для а = 5 имеем соответственно 1 подстановку с 5 циклами, 10 — с 4 циклами, 35 в с 3 циклами, 50 в с 2 циклами, г ~ г л СР ~ЬС~ л р Ь(~ ~ С~ ю Я Рис.
30. ') Разлагаем (1 — !) ~ ио формуле бинома. )Об 24 — с 1 циклом. На рис. 30 изображены !О подстановок с 4 ци- клами (рис. 30). Из (17.48) получается рекуррентная формула П„' (г) = (г + л — 1) П; ~(г). (17.50) Сравним, с другой стороны, (17.48) и (10.1) (числа Стирлинга): П", (г) = г (г + 1) ... (г + л — 1), ~р'„(г) =г(г — 1) ... (г — а+ 1), Полагаем П*.(г)= 2', и(л, й)гь. а=о (17.53) Сравнивая (!7.53) и (10.3) видим, что и(п, й) =( — !)"+'з (и, й). (! 7.54) Рис. 3! Л*„(г) = Р'„(О, г,, г); (!7.55) тогда в силу (!7.!7) еа ' = е*ип2+юч-" > (! 7,56) вам а~ньеР+гРь ч.
е- ~ — (1 !)-', е- ~ р 2~Р = ~ 1+ ~~~ г(г+ 1) ... (г+ и — !) . — ~! — г!+ й~! =~~ +~ п~*~" (( т. '-„'>'" (= („'а),а! К ь(г)( — г)' !", где Л"-: Л,', 1!о(г)=1, ю-а ! ь=о (17.57) !Об Таким образом, таблица 10.! дает числа п(а, й), если в ней везде опустить знак « — ». Подобными рассуждениями можно найти денумератор цикловых классов, состоящих из й циклов, длина которых не фиксируется, и не содержащих 1-циклов, т. е, беспорядков с й-циклами. Рис.
31 изобра,ж жает беспорядок, состоящий из двух циклов. Положим или «=о «=о! ь а (17.58) Наконец, Л„(г) = ~ С,П„з(г)( — г)~, я=1, 2, 3, ... (17.59) »=о Положим также Ьл (з) = 2~ Ь (л, й) 3 , «=о (17.60) Сравнивая коэффициенты в (17.59) и (17.60), имеем Ь(п, Й) = ~"„С'„( — 1)'п(п — г, й — г).
(17.61) Ь(а, Й) ~~~~ С),( — 1) з(л — г, й — г). (17.62) г 0 При и 7 и А=2 имеем 1 Ь (7, 2) = ~ Ст( — 1)~ "з (7 — г, 2 — г) ~ о =Сто( — 1) з(7, 2)+С«( — 1) з(6, 1) = — з(7,2)+7з(6, 1). (17.63) По таблице 10.1 (стр. 48) находим з(7,2) = — 1762 и з(6, 1) = = — 120: Ь (7, 2) = 1764 — 7 ° 120 = 924. (17.64) В таблице 17.1 приведены значения Ь(п, й) до и=8. Полагаем Ь(0, 0)=1 н Ь(п, 0) =О, п > О.
Для Ь(п, Й) можно указать непосредственно интересную рекуррентную формулу. Используя (17.62) и (10.9) имеем Ь(п+ 1, й) = ЬЬ (и, й) + пЬ(п — 1, й — 1). (17,65) Можно также выразить П"„(г) через А'„(г). Для этого рассмотрим (17.57): ьп и г <М'Р+г~з+ .. З (1 1)-г о г, Ь (17 66) 107 Числа Ь(п, й) называются «присоединенными числами Стирлинга первого рода».
Подсчитаем Ь(и, й) для некоторых значений и и и. Для этого запишем (17.61) с помощью (!7.54): Таблица 17.! Та5лнца присоединенных чисел Стирлинга первого рода до и 8 сов Ц !5 2!0 2380 105 ИЛИ + ! + О2! + ''')( + + 21+ ''') 12 гз =1+г~+г(г+1) 21 +г(г+1)(г+2) з + = 1 + П! (г) г + Пт (г) 21 + Пз (г) 3! + ... (17.67) Отсюда П, (г) = Х С'„Л„, (г) г'.
г=о (17.68) Подставляя (17.63) и (17.60) в (17.68), получаем Ф-1 и (и, й) = ~ С',6 (и — г, )г — г), Г=о (17.69) или, возвращаясь к числам Стирлинга первого рода, 3 (п, й) = ( — 1)"+е ~~ С'„6 (и — г, п — )г). (17.70) г=е С помощью 6(и, )с) можно вычислить число беспорядков и элементов: и/2, если и четно, (17.71) в-1 ' ! (и — 1)/2, если п нечетно. Предел суммирования в (!7.71) взят, исходя из того, что бес. порядок не содержит 1-циклов. 108 6(1, )г) 6(2, л) 6(3, А) 6(4, л) Ь(5, А) 6(5, л) 6(7, А) Ь (8, А) 0 1 2 6 24 120 720 5040 3 20 130 924 7308 Выпишем денумераторы четных и нечетных подстановок: Ри (г1> гз» гз) = ~ (~ (г1> гз гз> го ° ° ° > гр)+ Р (г1> гь гз> — гь> ...)! (17.72) с РР'= 1' Р (гн г ... г)— = фР (г1 гн гз гь °, г~) — Р" (го гм гз гь ° ° ° )) (17 73) с Рь =О. Например, в силу (!7.8) имеем Рр" (г1) = г1, Р4 = г1 + Згз+ 8гзгз, р р» 2 р 5 2 Рзр (г1, гз) =го Рь =г1+ 15гьг2+ + 20гьгз + 24гь, (17.74) з р* ь 2 2 Рз Р(г1, гм гз)=г1+2гз, Рь*=г, +45г,г,+ + 40г',гз+ 40гз+ 90г,г4+ 144г,г, Р11»(г1)=0, 4 ( 1> г2> гь> г4) 1г2+ Я> Рз (гн гз) = аз» Р, (г1> гм гм г4, гь) = = 10г',г, + 20гзг„+ ЗОг,г4, (17.75) Рз ь(г1' гз' гз) = Згьгз, Рь ь(г1, гз, гз' гь' гь' гь) = 15г41гз+ + 15г,'+ 120г,гзгз -1- 90гзгь+ 120г, Имеем соответственно 15 нечетных подстановок класса (4, 1,0, О, О, 0), 15 — класса (О, 3, О, О, О, 0), 120 — класса (1, 1, 1, О, О, 0), 90 — класса (2, О, О, 1, О, 0), 120 — класса (О, О, О, О, О, 1).
Точно так же можно найти денумераторы ПР' и П, числа подстановок, обладающих заданным числом циклов. Полагаем (как в (17.43)) Пз (г)=РРЗ'(г> г> * г)> Пь*(г) = Рз (г> г» г) (17.?6) (17.77) !09 Имеем соответственно одну четную подстановку класса (6, О, О, О, О, 0), 45 — класса (2, 2, О, О, О, 0), 40 — класса (3, О, 1, О, О, 0), 40 — класса (О, О, 2, О, О, 0), 90 — класса (О, 1, О, 1, О, 0), 144 — класса (1, О, О, О, 1, 0).
Для нечетных подстановок в силу (17.8) получаем анало- гично Тогда еп~"ю ! !(1 !)-' ! (! ! !)'1 (17.78) "" =-,'й! — !) ' — (!+!)'1. Отсюда ввиду (17.46) 11Г(г)= 21 (г+1) ... (г+ — 1)+г( — !)... ( — и+ !)), ! (17.80) 11;(г) = — (г(г+ 1) ... ( + л — 1) — ( — 1)... (г — + !)) (17.81) (17.79) Например, для л=6 Пл* (г) = — (г (г + 1) (г + 2) (г + 3) (г + 4) (г + 5) + + г (г — 1)(г — 2)(г — 3)(г — 4) (г — 5)) = = — 12гл + 170г'+ 548г) = гл + 85г" + 274г-".
(17.82) Таким образом, существуют одна четная подстановка 6 элементов, содержащая 6 циклов, 85 — содержащих 4 цикла и 274 — содержащих два цикла. Денумераторы циклов с предписанным порядком элементов. Предварительно рассмотрим пример. Пусть задана подстановка класса (О, О, 1, 1, О, О, 0) (рис. 32).
По соглашению (см. стр. 89) ее можно записать так: (1427) (365). (17.83) б с Это соглашение позволяет не различать циклы (1427), (4271), (2714) и (7142), (17.84) й а также Рис 32. (365), (653), (536). Однако циклы (1427) и (1724) различны. Пересчитаем подстановки и элементов, в циклах которых элементы расположены в предписанном порядке. Таким образом, приходим к задаче пересчета классов циклов, составленных из одних и тех же элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
