Stirlingova čísla
Rozeznáváme Stirlingova čísla 1. druhu a Stirlingova čísla 2. druhu. Stirlingova čísla 1. druhu jsou definována následovně. Buď x proměnná. Pak pro libovolné nezáporné celé číslo n je klesající faktoriál
[x]„ = x(x-l)(x-2)---(x-n+l)
(klademe [x]o = 1) polynomem v proměnné x stupně n, který lze vyjádřit ve tvaru
n
[*]n = ^Sn^X1
k=0
pro jisté celočíselné koeficienty sn^- Tyto koeficienty sn^ pro všechna nezáporná celá čísla a?, k se nazývají Stirlingova čísla 1. druhu.
Tvrzení.
Stirlingova čísla 1. druhu jsou dána počátečními hodnotami
s0,o = 1, 5,7,0 = 0 pro n > 0, s0,/c = 0 pro k > 0
a rekurentní formulí
Sn+l,k = Sa7,/c-1 — nSn^k
platnou pro všechna nezáporná celá čísla n a všechna kladná celá čísla k,
Důkaz.
Uvedené počáteční hodnoty ihned plynou z definice Stirlingových čísel 1. druhu. Pokud jde o uvedenou rekurentní formuli, uvědomme si, že = [x]n(x — n).
Podle definice je hodnota sn+i,k koeficientem u xk v polynomu [x]n+i. S ohledem na právě uvedené vyjádření polynomu je tento koeficient roven koeficientu
u xk~ľ v polynomu [x]n zmenšenému o n-násobek koeficientu u xk v polynomu [x]n. To však znamená, že hodnota sn+i,k je rovna hodnotě sn,k-i — nsn^k- To je ale právě dokazovaná rekurentní formule. □
Zaměňme nyní ve výše uvedené formuli definující Stirlingova čísla 1. druhu proměnnou x za —x. Dostaneme tak formuli
n
k=0
čili formuli n
k=0
Ještě jinak zapsáno, máme formuli
n
[x]n = ^2(-iy+ksn,kxk
k=0
oro všechna nezáporná celá čísla n.
Poněvadž rostoucí faktoriál
[x]n = x(x + l)(x + 2) • • • (x + n - 1)
(klademe [x]° = 1) má evidentně všechny koeficienty u kladných mocnin proměnné x kladné, znamená to, že pro všechna nezáporná celá čísla a?, k je číslo (—l)n+ksn^ absolutní hodnotou čísla sn^- Odtud je patrno, že všechna čísla sn?i, sn?2, ■ ■ ■ , sn^n jsou nenulová a jejich znaménka se pravidelně střídají. Pro zmíněné absolutní hodnoty \sn^\ Stirlingových čísel 1. druhu pak platí obdoba předchozího tvrzení.
Tvrzení.
Absolutní hodnoty Stirlingových čísel 1. druhu jsou dány počátečními hodnotami
|s0,o| = 1, |s„,o| = 0 pro a? > 0, |s0,/c| = 0 pro k > 0
a rekurentní formulí
$n+l,k\ — \Sn,k-l\ + n\sn,k
platnou pro všechna nezáporná celá čísla n a všechna kladná celá čísla k,
Důkaz.
Co se týče počátečních hodnot, ty plynou okamžitě z předchozího tvrzení. Pokud jde o danou rekurentní formuli, s využitím rekurentní formule z předchozího tvrzení dostáváme
n+k+1
= (-ly+'-hn^ + (-l)n+kns„,k = |s„)k_i| + n\s„tk což dává dokazovanou rekurentní formuli.
□
Pro libovolná nezáporná celá čísla a?, k označme symbolem cn^ počet všech permutací a množiny {1,2,..., n} takových, že v rozkladu permutace a na součin nezávislých cyklů se objevuje právě k cyklů (včetně cyklů délky 1, to jest včetně pevných bodů).
Tvrzení.
Čísla cn^ jsou dána počátečními hodnotami
c0,o = 1, cn,o = 0 pro n > 0, c0,/c = 0 pro k > 0
a rekurentní formulí
Cn+l,k — Qi,/c-l + nCn,k
platnou pro všechna nezáporná celá čísla n a všechna kladná celá čísla k,
Uvedené počáteční hodnoty plynou ihned z definice čísel cn^. Pokud jde o uvedenou rekurentní formuli, uvažujme libovolnou permutaci a množiny {1, 2,..., a?, n + 1}, v jejímž rozkladu na součin nezávislých cyklů se objevuje právě k cyklů. Počet takových permutací je dán číslem cn+i^- Uvažujme číslo n + 1. Permutace a může mít číslo n + 1 jako pevný bod. V takovém případě zúžení permutace a na množinu {1,2,..., n} bude permutací této množiny {1,2,..., n}, v jejímž rozkladu na součin nezávislých cyklů se objeví k — 1 cyklů. Počet takových permutací je dán číslem cn^-i- Anebo číslo n + 1 nebude pevným bodem permutace a. Pak toto číslo n + 1 bude figurovat v některém cyklu délky větší než 1. Uvažme permutaci a' množiny {1,2,..., n}, která se bude lišit od permutace a jenom tím, že zkrátíme cyklus permutace a obsahující číslo n + 1 vypuštěním tohoto čísla n + 1; ostatní cykly zůstanou beze změny. Tak ale může vzniknout zcela libovolná permutace množiny {1,2,..., n}, v jejímž rozkladu na součin nezávislých cyklů se objeví právě k cyklů. Počet takových permutací je dán číslem cn,k- Opačným postupem je možno ke každé permutaci r množiny {1,2,..., n}, v jejímž rozkladu na součin nezávislých cyklů se objevuje k cyklů, vytvořit celkem n permutací množiny {1, 2,..., a?, n + 1}, v jejichž rozkladu na součin nezávislých cyklů se objevuje právě k cyklů a které nemají číslo n + 1 jako pevný bod, vložením tohoto čísla n + 1 do kteréhokoliv cyklu permutace r na kterékoliv místo v tomto cyklu.
_j
5/18
Je vidět, že takto jsme ověřili, že číslo cn+i^ je rovno hodnotě cn^-i + ncn^, což dokazuje uvedenou rekurentní formuli. □
Nyní jsme připraveni odvodit následující výsledek poskytující informaci o kombinatorickém významu Stirlingových čísel 1. druhu.
Důsledek.
Pro všechna nezáporná celá čísla a?, k platí rovnost
J
Důkaz
Podle předchozích dvou tvrzení čísla \sn^\ a cn^ jsou dána týmiž počátečními hodnotami a vyhovují týmž rekurentním formulím, odkud plyne, že tato čísla si musí být rovna. □
Stirlingova čísla 1. druhu vyhovují rekurentní formuli
n
7=0
platné pro všechna nezáporná celá čísla n a všechna kladná celá čísla k,
Důkaz
Už jsme viděli, že platí [x]n+i = [x]n(x — n) = x[x]n formuli opakovaně, postupně získáme rozvoj
n[x]n. Aplikujeme-li tuto
Mn+l = X[*]n ~ n[x]n = x[x]n - A7x[x]„_i + A?(a7 - l)[x]„_i
= X[x]n - A7x[x]„_i + n(n - l)x[x]„_2 - A7(A7 - 1)(A7 - 2)[x]„_2
= x[x]n - A7x[x]„_i + n(n - l)x[x]A?_2
+ (-l)>]„x[x]0
n
= ^(-iyHx[x]n_j.
Číslo Sn+i^ je koeficient u mocniny x v polynomu [xj^+i. Vzhledem k právě odvozené rovnosti to znamená, že číslo sn+i^ je součtem koeficientů u mocniny xk v polynomech (—l)7 [n^-x [x]„_/ pro j = 0,1, 2,..., n. Koeficient u mocniny xk v takovém polynomu (—l)7 [a7]7-x [x]„_/ je číslem (—l)7 [n]j vynásobený koeficient
u mocniny x v polynomu [x]n_/. Ale tento poslední koeficient je roven číslu Sn-j^k-i- Odtud pak plyne, že
n
Sn+l,k = [n]jSn-j,k-l
j=0
což bylo potřeba dokázat.
□
Odtud ještě podobným obratem jako výše odvodíme následující fakt.
Tvrzení.
Absolutní hodnoty Stirlingových čísel 1. druhu vyhovují rekurentní formuli
n
Sn+l,k\ - ^2 [n]j |Sa7-J,/c-1
platné pro všechna nezáporná celá čísla n a všechna kladná celá čísla k,
Viděli jsme už, že pro všechna nezáporná celá čísla n, k platí \sn^\ = (—l)n+ksn^ Odtud a z předchozího tvrzení pak plyne
n
Sn+1,k\ = (-iy+k+1sn+1,k = (-1)^+1        [n]j s^j^
n
j=0 n
7=0 ;=0 n
7=0
To ovšem bylo potřeba ukázat. □
Stirlingova čísla 2. druhu jsou definována následovně. Nechť a?, k jsou libovolná nezáporná celá čísla a nechť M je konečná množina mající n prvků. Označme Sn^ počet všech rozkladů množiny M na k neprázdných tříd. Tato čísla Sn^ se nazývají Stirlingova čísla 2. druhu.
Tvrzení.
Stirlingova čísla 2. druhu jsou dána počátečními hodnotami
S0,o = 1, Sn,o = 0 pro n > 0, S0,k = 0 pro k > 0
a rekurentní formulí
Sn+i,k — Sn,k-i + kSn,
platnou pro všechna nezáporná celá čísla n a všechna kladná celá čísla k,
Důkaz.
Uvedené počáteční hodnoty plynou ihned z definice Stirlingových čísel 2. druhu. Pokud jde o uvedenou rekurentní formuli, vezměme konečnou množinu M mající n prvků a nějaký další prvek b £ M. Představme si všechny rozklady množiny M U {b} na k tříd. Počet těchto rozkladů je dán číslem Sn+i^. V některých těchto rozkladech tvoří prvek b jednoprvkovou třídu. Ostatní třídy pak tvoří rozklad množiny M na k — 1 tříd. Počet těchto rozkladů je dán číslem Sn^-i-
V ostatních rozkladech množiny M U {b} na k tříd je prvek b obsažen v některé víceprvkové třídě. Vyjmutím prvku b z této třídy vznikne rozklad množiny M na k tříd. Počet těchto rozkladů je dán číslem Sn,k- Naopak ke každému rozkladu množiny M na k tříd je možno opačným postupem vytvořit celkem k rozkladů množiny M U {b} na k tříd, v nichž prvek b leží v některé víceprvkové třídě. Prostě přidáme prvek b ke kterékoliv třídě daného rozkladu množiny M na k tříd. Tato úvaha ukazuje, že číslo Sn+i:k je rovno hodnotě Sn,k-i + kSn,k- To ale dává dokazovanou rekurentní formuli. □
Pro Stirlingova čísla 2. druhu máme následující explicitní formuli.
Tvrzení.
Pro libovolná nezáporná celá čísla n, k platí
(kde klademe 0° = |00| = |{0}| = lj.
Označme hodnotu udanou ve výše uvedené rovnosti napravo symbolem Tn^. Chceme ukázat, že platí rovnosti Sn,k = Tn^ pro všechna nezáporná celá čísla a?, k. Toho docílíme, když ukážeme, že hodnoty Tn^ vyhovují počátečním podmínkám a rekurentní formuli uvedeným v předchozím tvrzení. Fakt, že 7~o5o = 1 a 7~n,o — 0 Pro n > 0, plyne ihned z definice hodnot Tn^. Abychom ukázali, že Tq^ = 0 pro k > 0, stačí si všimnout, že podle binomické věty je
E(-1)'í"í(/) = (1-1)'í = 0-
/=o
Věnujme se tedy požadované rekurentní formuli. Z definice hodnot Tn^ a s využitím vlastností binomických koeficientů dostáváme
k-l ,. k
M—i l * \ :n
/
/=0 v 7 /'=0
/c-1
/
v        7 i=0
i=l v 7
/=o v 7
To je ale právě potřebná rekurentní formule pro čísla Tn^. □
platné pro všechna nezáporná celá čísla n a všechna kladná celá čísla k.
Mějme konečnou množinu M mající n prvků a vezměme další prvek b ^ M. Uvažujme všechny rozklady množiny M U {b} na k tříd. Počet těchto rozkladů je dán číslem Sn+i^- V takovém rozkladu leží prvek b v některé třídě C. Tato třída C má / + 1 prvků a množina C — {b} má / prvků pro nějaké / = 0,1, 2,..., n. Zbývající třídy uvažovaného rozkladu pak tvoří rozklad množiny M — C na k — 1 tříd. Množina C — {b} je podmnožinou množiny M a lze ji vybrat (/) způsoby. Je-li tato množina už vybrána, pak k ní lze vzít kterýkoliv z rozkladů množiny M — C na k — 1 tříd. Počet těchto rozkladů je dán číslem Sn-i^-i- Dostáváme tak rovnost
Položíme-li nakonec j = n — /, přejde tato rovnost v rovnost
kterou bylo potřeba dokázat.
Stirlingova čísla 2. druhu postihují další souvislost mezi mocninami proměnné x a klesajícími faktoriály v proměnné x. Máme následující sdělení.
Uvedená rovnost je rovností dvou polynomů stupně n v proměnné x. Tyto polynomy se budou sobě rovnat, pokud jejich rozdíl bude polynomem majícím alespoň n + 1 různých kořenů. To nastane, pokud se hodnoty těchto dvou polynomů budou sobě rovnat pro alespoň n + 1 různých reálných čísel dosazených za proměnnou x. My ukážeme, že se hodnoty těchto dvou polynomů sobě rovnají dokonce pro všechna kladná celá čísla £ dosazená za proměnnou x.
Buď M konečná množina mající n prvků a buď L konečná množina mající^ prvků. Uvažujme libovolná zobrazení f : M —>► L. Počet těchto zobrazení je roven číslu £n. Rozdělme nyní tato zobrazení f podle toho, jaké jsou jejich obrazy f(M). Každé takové zobrazení f : M —>► L očividně určuje surjektivní zobrazení f : M —>► f (M).
Obrazy f (M) při těchto zobrazeních jsou nějakými podmnožinami množiny /_.
_j
15/18
Takto pro každou podmnožinu H C L pořídíme množinu všech surjektivních zobrazení f : M —>* H. Pro různé podmnožiny H C /.jsou tyto množiny surjektivních zobrazení navzájem disjunktní. Je-li k počet prvků podmnožiny H, pak počet všech surjektivních zobrazení f : M —>* H je roven číslu k\-Sn^-Skutečně každé takové surjektivní zobrazení f indukuje rozklad množiny M na k tříd; počet těchto rozkladů je dán číslem Sn^- Naopak ke každému rozkladu množiny M na k tříd lze pořídit k\ surjektivních zobrazení f : M —>* H, která tento rozklad indukují. Dostanou se libovolnými permutacemi prvků množiny H. Poněvadž pro každé k = 0,1, 2,..., n je počet všech podmnožin H C L majících k prvků dán binomickým koeficientem (jr), dostáváme tak rovnost
/c=0 ^  ^ /c=0     ' /c=0
To je ale potřebná rovnost hodnot polynomů xn a X^^=o^,^M^ ve všech kladných celých číslech £. □
Závěrem odvodíme z našich dosavadních zjištění následující poznatek. Bude to první příklad jevu, kterému se říká vzájemně inverzní formule. V daném případě by bylo možno mluvit o Stirlingových vzájemně inverzních formulích.
Důsledek.
Necht fg jsou dvě reálné funkce definované na množině všech nezáporných celých čísel. Pak platí rovnosti
n
s(n) — ^2sn,kf(k)   pro všechna nezáporná celá čísla n
k=0
právě tehdy, když platí rovnosti
n
f (n) = ^2 Sn,kg(k)   pro všechna nezáporná celá čísla n.
k=0
Důkaz.
Uvažme nekonečné matice
A = (sn,k) nk=012^     a   B = (Sn,k) nk=Q12/
Tyto matice mají v každém řádku jen konečný počet nenulových hodnot. Je tedy možné tyto matice mezi sebou násobit a je také možné je zprava násobit nějakými nekonečnými vektory zapsanými do sloupců. Uvažme nekonečné vektory
v= (x") „=0,1,2,...     3    W= (M")n=0,l,2,../
Pak výše uvedené formule [x]n = J2k=oSn,kxk a x" = S/Uo^^M^ p'stné pro všechna nezáporná celá čísla n lze přepsat jako rovnosti nekonečných vektorů
w = A v   a   v = 6 w.
Je tedy matice /4 maticí přechodu od báze w k bázi v ve vektorovém prostoru všech polynomů proměnné x a podobně matice B je maticí přechodu od báze v k bázi w v tomto vektorovém prostoru. To ale znamená, že matice A b B jsou k sobě navzájem inverzní. Uvažme dále nekonečné vektory
f = (ŕ("))„=0,l,2>...     3    8= (*(")) n=0)i,2,...
vytvořené z hodnot našich reálných funkcí f a g. Pak výše uvedené tvrzení o našich vzájemně inverzních formulích, které máme dokázat, říká, že rovnost vektorů
g = Af
platí právě tehdy, když platí rovnost vektorů
f = B ■ g.
Ale skutečně jedna z těchto rovností implikuje druhou, poněvadž matice A b B jsou k sobě navzájem inverzní, takže součiny A • B a B • A jsou nekonečnými jednotkovými maticemi. □