Введение в прикладную комбинаторику, Кофман А. (984071), страница 8
Текст из файла (страница 8)
Рассмотрим следующие тождества: о г'=г, г ( ц ! ге= г(г — 1)(г — 2) + Зг(г — 1)+г, г4 = г (г — 1) (г — 2) (г — 3) + бг (г — 1) (г — 2) + 7г (г — 1) + г, (10.4) Обозначим через з(п, г) коэффициент при ф,"(г) в разложении г" такого вида и запишем г"= Хз(п, г) 4!,'(г), У(0, 0)=1. (10,6) Таблица 10.! Таблица чисел Стирлиига первого рода до и = 8 г=! г 2 г 3 г 7 г!л, г! г в(1, г) а (2, г) -3 1 в (3, г) л (4, г) — 1Π— 50 5(5, г) -15 -225 85 274 в (6, г) — 21 !75 — 735 -1 764 1 624 720 5(7, г) -28 322 — 1960 6769 — 13 182 а (8, г) -5 040 Целые числа з(п,г) называются числами Стирлинга второго рода.
В таблицах 10.! и 10.2 приведены числа з(п, г) и з(п, г) до п=8. Для простоты полагают также з (и, 0) = О, п = О, 1, 2, ..., н й (п, 0) = О, и = О, 1, 2, ... (10,6) Таблица 10.2 Таблица чисел Стирлиига второго рода и = 8 г 2 г 5 г=! гы. г! г 3 г г г 8 (1, г) 8 (2, г) 8 (3, г) 8 (4, г) 10 15 3(5, г) 65 90 31 !5 8 (6, г) 350 140 2! 63 301 8 (7, г) 1701 1ОгО 266 127 966 8 (8, г) Рекуррентные формулы для чисел Стирлинга.
Имеем !р"„ ,(г) = ~р„' (а) (г — п). Таким образом, че! о ~ з(и+1, г) и" = ~ (г — и) з(и, г) г.'. (10,8) г=! г=! Приравнивая коэффициенты при одинаковых степенях гг в пра- вой н левой частях (10.8), получаем рекуррентную формулу: з (п+ 1, г) = з(п, г — !) — пз (п, г), п ен Хо г ен Хо, г ( п, (10.9) позволяющую легко вычислять числа Стирлинга первого рода. Например, з (4, 3) = з (3, 2) — Зз (3, 3) = — 3 — 3 = — 8.
(10.10) Чтобы получить рекуррентную формулу для чисел Стирлинга второго рода, воспользуемся (!0.5): ч+! г" + ! = ~ Л (п + 1, г) !р' (г). (10. 11) г=! Представляя г"+' = г" г, можно записать г"+' = ~~~ з(п, г) г <р,'(г). г В силу (10.7) г!р', (г) = <р",, (г) + пр, '(г). (10.12) (10.13) Подставляем (10.13) в (10.12): г"+'= Д й(п, г))ф', !(г)+гф,'(гЦ. (10.14) г=! Сравнивая (10.11) и (10.14), имеем !!+ ! л ~'! з(а+ 1, г) <р,"(г)= ~ з(п, г)~ф,'+! (г)+и~„'(г)) (10.15) Приравниваем козффициенты при ф,'(г) в правой и левой частях (10.15): й(а+1, г)=й(п, т — 1)+ай(п, г), аен Х,, ген 1Ч, г(п. (10.16) Например, Л(5, 3)=й(4, 2)+33(4, 3)=7+3 ° 6=25. (10.17) записываем ~~~ з (и, к) й (г, й) = б„».
г-! (10.20) Между числами з(п, г) и з(п, т) существует важное соотно- шение. Подставим (10.5) в (10.3): л 1 л с ф'„(г) ~ з(п, х) ~~'., У(г, й) ф' (г)= ~~'., ', з(п, г)з(г, й)ф'„(г) т ! «-! г ! ь=! = з (а, 1) з (1, 1) <р",(г) + з (и, 2) з (2, 1) ф*, (г) + + з (и, 2) з (2, 2) ф", (г) + з (а, 3) з (3, 1) <р', (г) + + з (и, 3) Л (3, 2) !р,' (г) + з (п, 3) Л (3, 3) !рз (г) + ... ... + з (п, а) Л (и, 1) <р', (г) + ... + з (а, а) ю (и, и) <р"„ (г). (10.
18) Сравнивая выражения при ф,"(г) в правой и левой частях (10.18), получаем 10, 1(й <а, Х з (и, «) У (г, й) = ~ (10.19) Пользуясь символом Кронекера О, ючь1, б!! = 1, !=1, (10.2!) (1П О О г(2, 1) г(2, 2) О з (3, 1) г (3, 2) г (3, 3) ..
ПзП= (10.22) 3(1, 1) О О з (2, 1) 3 (2, 2) О 3 (3, 1) 3 (3, 2) й (3, 3) ... ПзП= (10.23) С их помощью (10.20) и (10.21) можно записать так: П П ЦзП=ПзП ПзП=П1П где Ц 1 Ц вЂ” единичная матрица бесконечного порядка, Итак, П Н П=П з Г'ФФП з П=П У Г', т. е. П зП и Пз П вЂ” взаимно обратные матрицы. Числа Белла. Полагаем ПзеП=ПзП', (!0.26) ПзяП=ПзП ° (10.27) Элементы матриц ПзьЦ и ЦзП~ назовем соответственно числами Белла первого и второго рода порядка )г.
Числа Белла порядка 1 — это числа Стирлинга. Из (10.25), (10.26), (!0.27) видно, что П згП=П зь Г ФН зь П=П зя Г! (10. 28) Ц Пз ППзП, (10.29) ПзтЦ=ПУ ьП'Цвыл (10.30) Если обозначить элементы Цз, П и П з, Ц соответственно через з(п, !'1 г) и з(п, 1; г), то л з(п, 1; г) = ~ з(п, !'; г — !г) з(1, 1; й), 1=! з(п, 1; г)= ~~~ в(п, /; г — !Н)з(1, 1; й). (!0.32) ! ! Полиномы Белла и формула Бруно. Рассмотрим сложную функцию (10.24) (10.31) у=~(и) и и=у(х), (10.33) 31 Если подставим, наоборот, (10.3) в (10.5), то получим симметричное соотношение: л ~! П(п, г) з(г, Й) =б„м т=! Рассмотрим две бесконечные матрицы: т.
е. У = 1 (а (г)1 = й (е). Последовательные производные Ь(г) запишутся так: (Я.з4) у~ — у„иы АР уР иРР 1 уРР (цР)з у,"'=у'„и,'"+ Зу'„' и," и,'+ у„"'. (ц,')з, (10.35) Можно ли дать общий вид этих формул? Ответ утвердительный. Мы докажем следующую формулу, называемую формулой Бруно, правая часть которой называется голиномоч Белла. Оба эти понятия часто используются в комбинаторике Обозначая последовательные производные через у('(, у('!..., , у(о, ..., докажем сначала формулу Бруно: у("(=~)~,„, ",, ( (() ( —,() ( — (), (ЯЗ6) у("' = ~ а("(у('(, г ~ и ' г=! (10.37) где а("'=аип(и(" икч ... и("!).
к г ( я' л''''' г)' (10.38) Так как а("! не зависят от у(„'(, то для определения а(,"((й=1, 2, ..., и) функцию у=)(и) можно выбрать произвольно. Возьмем у(и) = е'", (10.39) где а †действительн число, отличное от нуля. Тогда у("! = аде ". и (!0,40) Подставим (10.40) в (10.37): у("! = лл а("! (и(п, и((! ... и("(! а'е " гг(г'я''''~д) Э г ! (10.41) где й( (! = 1,2... л) — такие целые неотрицательные числа, что й! + йз+ ... +й„= К а суммирование производится по всем решениям (й(, Ам ..., и„) уравнения й! + 2й, + ...
+ пй„=. н. Правые части для и = 1, 2, 3, ... называются нолиномами Белла. Докажем (1036), следуя Р и ар дану [36]. Любая производная у(,"' — линейная функция н производных у'„", уа(, ..., у(„(, коэффициенты которой являются функциями производных ц(п ц(2! и(л! 2 Л 1 1 М или Перепишем (10.42), учитывая (10.43): а(л1(ц(11 ц(21 ц(л\ (тт — Е-аимл> (10.44) Согласно (!0.44) л+! — аи (а+11 -аиг л+1„-аиг л+1 аи а =е у, =е Р, У=е Р, е л = е "'аР,"[е'"ц("1=е '"а ~ СиР,'л "(е") Рги(п=') ь-з л =а ~ С,(е Р, ~(е )) Ргц(11= и=о г=з Таким образом, символически можно записать ал+'=аи (а+ и )", аи — ' а(а> иа — 'и'Я>.
(10.46) При ц=0, 1, 2, ... из этой формулы вытекает а(о =аип> г 1 аи' = аи('>ао'+ аи('> = аи('>(аи('>)+ ац('1 = г г г ( г ) г = ц'(и((г>з 1- аи(" г г аз = аи'оа(" + 2аи" >а" > + аи(в = г г г = ам' " (аз (и(1>1з + аин 0 + 2а ипч (ам" '1 + аи(з' ! г ( г) г аз(и(!11з+ Зази(з>и(о + аи(з> ) г г г (10.47) К обеим частям (10.46) применим экспоненциальное а-преобразование.
По формулам (7.74) — (7.77) получаем ае' = аи,е('+"г) (10.48) или и и,( зз а=аи е ' =а и'+ из(+ — '+ ...). ( (10.49) ') Используется известная формула Лейбница (6.99). 63 е '"у(л>= ~ а',л>(и('>, иц>, ..., и(л>)аг. (10.42) г=! Полагаем л а(л>(и(1>, и(З>, ..., и(л', а) = ~ а(л>(и(!>, и('>, ..., и(л>)а'. (10.43) г=! Интегрируем (10.49) от 0 до 1) и2(2 из(З 1= (,1+ — '+ —;, + ...). 2< Потенцируем (10.50): "'-.*4[.[.4.> — "' 4- — "', 4....)]. Переходя к несимволическим обозначениям, получаем ( (2)(2 (3 (2 1+а(Ч+ — + — + ...
) 2) З) Х [~ 4. '~ ' +,', ['";,' ) 4- „['",*, ) 4- " ] Х Приравнивая коэффициенты при одинаковых степенях в (10.52), приходим к (10.47). Бруно дал следующую общую формулу, получаемую этим способом: ,,[";) [ — ",*,) ...[ — ";), ДО.ЗЗ) где <2(+ АЗ+ ... + <2„<з, <2( — целые неотрицательные числа и суммирование производится по всем решениям (й„>з„..., <з„) уравнения 72( + 2)(22 + ... + пй„ =и. Переходя от коэффициентов а<"> к производным у<,"', имеем окончательно У =2' ~" [ — *) [ — ') ...[ — *,) . (14.44) (10.50) (10.51) В заключение приведем полиномы Белла для и = 1, 2, 3, 4, 5: у',и = у'„')ип), у(2) — у())ц(2) 1 у(2) гц((ЦЗ Л З З уо) = у() )ц(з> + у(м (За<2)и(п) + у(з> (и('))з, у<4) = уп)ц(4) + укч(4ц(з)ц(() + 3 (ц(2))21 + З З * и [ л Я (10.55) + у(з) [бц(2) (ц(())2] + у(4) (цн))4 у(з) уп)ц(з) + у(2) [бц(4)цп) + 10ц(з>ц(2)] + + у(з> [10и">(и<п)'+ 15 (и 2>)2 и<,')] + „1 у(4> []Оц(2> (ц(())з] + укч (и(())з Числа Стирлинга и числа А"0".
Покажем, что числа Стирлинга второго рода и числа Л"0" связаны простым и интересным соотношением, которое будет использоваться в дальнейшем. Напомним рекуррентное соотношение (10.16), определяющее числа Стирлинга второго рода: з(и+ 1, г)=з(п, г — 1)+ гз(п, г), г(и, (10.56) и рекуррентное соотношение (6.40) для А'0": Л'0"+ гб'0" + гЛ' 0", г и" п. Обозначим !'(и, г) = г! й (и, г). (10.67) (10.68) Умножаем обе части (10.56) на г1: г!з(и+1, г)=Ну(п, г — 1)+г1ге(п, г). (10.69) 7' (п + 1, г) = г~ (п, г — 1) + г~ (п, г).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
