Použití exponenciální generující funkce (EFG)Stirlingova čísla kombinatorická matematika a možná kanonický příklad toho, jak symbolická kombinatorika se používá. Také ilustruje paralely v konstrukci těchto dvou typů čísel a poskytuje podporu pro binomický zápis, který se pro ně používá.
Tento článek používá operátor extrakce koeficientů [ z n ] { displaystyle [z ^ {n}]} formální mocenské řady , jakož i (označené) operátory C { displaystyle { mathfrak {C}}} P { displaystyle { mathfrak {P}}} symbolická kombinatorika . Vzhledem k tomu, kombinatorická třída, operátor cyklu vytvoří třídu získanou umístěním objektů ze zdrojové třídy podél cyklu určité délky, kde se berou v úvahu cyklické symetrie, a operátor množiny vytvoří třídu získanou umístěním objektů ze zdrojové třídy do množina (symetrie ze symetrické skupiny, tj. „nestrukturovaná taška“). Dvě kombinatorické třídy (zobrazené bez dalších značek) jsou
obměny (pro nepodepsaná Stirlingova čísla prvního druhu): P = SOUBOR ( CYC ( Z ) ) , { displaystyle { mathcal {P}} = operatorname {SET} ( operatorname {CYC} ({ mathcal {Z}}))),} a
nastavit oddíly do neprázdných podmnožin (pro Stirlingova čísla druhého druhu): B = SOUBOR ( SOUBOR ≥ 1 ( Z ) ) , { displaystyle { mathcal {B}} = operatorname {SET} ( operatorname {SET} _ { geq 1} ({ mathcal {Z}}))),} kde Z { displaystyle { mathcal {Z}}}
Varování : Zde použitá notace pro Stirlingova čísla není taková jako u článků na Wikipedii o Stirlingových číslech; hranaté závorky zde označují podepsaná Stirlingova čísla.
Stirlingova čísla prvního druhu Nepodepsaná Stirlingova čísla prvního druhu počítají počet permutací [n ] s k cykly. Permutace je množina cyklů, a tedy množina P { displaystyle { mathcal {P}} ,}
P = SOUBOR ( U × CYC ( Z ) ) , { displaystyle { mathcal {P}} = operatorname {SET} ({ mathcal {U}} times operatorname {CYC} ({ mathcal {Z}}))), ,} kde singleton U { displaystyle { mathcal {U}}} statistika náhodných permutací .
Při převodu na generující funkce získáme smíšenou generační funkci nepodepsaných Stirlingových čísel prvního druhu:
G ( z , u ) = exp ( u log 1 1 − z ) = ( 1 1 − z ) u = ∑ n = 0 ∞ ∑ k = 0 n [ n k ] u k z n n ! . { displaystyle G (z, u) = exp left (u log { frac {1} {1-z}} right) = left ({ frac {1} {1-z}} vpravo) ^ {u} = sum _ {n = 0} ^ { infty} sum _ {k = 0} ^ {n} left [{ begin {matrix} n k end {matrix} } right] u ^ {k} , { frac {z ^ {n}} {n!}}.} Nyní jsou podepsaná Stirlingova čísla prvního druhu získána z nepodepsaných prostřednictvím relace
( − 1 ) n − k [ n k ] . { displaystyle (-1) ^ {n-k} left [{ begin {matrix} n k end {matrix}} right].} Proto generující funkce H ( z , u ) { displaystyle H (z, u)}
H ( z , u ) = G ( − z , − u ) = ( 1 1 + z ) − u = ( 1 + z ) u = ∑ n = 0 ∞ ∑ k = 0 n ( − 1 ) n − k [ n k ] u k z n n ! . { displaystyle H (z, u) = G (-z, -u) = doleva ({ frac {1} {1 + z}} doprava) ^ {- u} = (1 + z) ^ { u} = sum _ {n = 0} ^ { infty} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k end {matrix}} right] u ^ {k} , { frac {z ^ {n}} {n!}}.} Manipulací s tímto lze odvodit různé identity generující funkce :
( 1 + z ) u = ∑ n = 0 ∞ ( u n ) z n = ∑ n = 0 ∞ z n n ! ∑ k = 0 n ( − 1 ) n − k [ n k ] u k = ∑ k = 0 ∞ u k ∑ n = k ∞ z n n ! ( − 1 ) n − k [ n k ] = E u log ( 1 + z ) . { displaystyle (1 + z) ^ {u} = součet _ {n = 0} ^ { infty} {u vybrat n} z ^ {n} = součet _ {n = 0} ^ { infty } { frac {z ^ {n}} {n!}} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k end {matrix}} right] u ^ {k} = sum _ {k = 0} ^ { infty} u ^ {k} sum _ {n = k} ^ { infty} { frac {z ^ {n}} {n!}} (- 1) ^ {nk} left [{ begin {matrix} n k end {matrix}} right] = e ^ {u log (1+ z)}.} Zejména lze vyměnit pořadí součtu a vzít deriváty a poté z nebo u mohou být opraveny.
Konečné částky Jednoduchá částka je
∑ k = 0 n ( − 1 ) k [ n k ] = ( − 1 ) n n ! . { displaystyle sum _ {k = 0} ^ {n} (- 1) ^ {k} left [{ begin {matrix} n k end {matrix}} right] = (- 1) ^ {n} n !.} Tento vzorec platí, protože exponenciální generující funkce součtu je
H ( z , − 1 ) = 1 1 + z a tudíž n ! [ z n ] H ( z , − 1 ) = ( − 1 ) n n ! . { displaystyle H (z, -1) = { frac {1} {1 + z}} quad { mbox {a tedy}} quad n! [z ^ {n}] H (z, -1 ) = (- 1) ^ {n} n !.} Nekonečné částky Některé nekonečné částky zahrnují
∑ n = k ∞ [ n k ] z n n ! = ( log ( 1 + z ) ) k k ! { displaystyle sum _ {n = k} ^ { infty} left [{ begin {matrix} n k end {matrix}} right] { frac {z ^ {n}} {n !}} = { frac { left ( log (1 + z) right) ^ {k}} {k!}}} kde | z | < 1 { displaystyle | z | <1} z = 0 { displaystyle z = 0} log ( 1 + z ) { displaystyle log (1 + z)} z = − 1. { displaystyle z = -1.}
Tento vztah platí, protože
[ u k ] H ( z , u ) = [ u k ] exp ( u log ( 1 + z ) ) = ( log ( 1 + z ) ) k k ! . { displaystyle [u ^ {k}] H (z, u) = [u ^ {k}] exp left (u log (1 + z) right) = { frac { left ( log (1 + z) vpravo) ^ {k}} {k!}}.} Stirlingova čísla druhého druhu Tato čísla počítají počet oddílů [n ] do k neprázdné podmnožiny. Nejprve zvažte celkový počet oddílů, tj. B n
B n = ∑ k = 1 n { n k } a B 0 = 1 , { displaystyle B_ {n} = součet _ {k = 1} ^ {n} vlevo {{ začátek {matice} n k konec {matice}} doprava } { mbox {a} } B_ {0} = 1,} tj Čísla zvonků . The Flajolet – Sedgewickova základní věta platí (označený případ) B { displaystyle { mathcal {B}} ,}
B = SOUBOR ( SOUBOR ≥ 1 ( Z ) ) . { displaystyle { mathcal {B}} = operatorname {SET} ( operatorname {SET} _ { geq 1} ({ mathcal {Z}})))} Tento rozklad je zcela analogický konstrukci soupravy P { displaystyle { mathcal {P}} ,}
P = SOUBOR ( CYC ( Z ) ) . { displaystyle { mathcal {P}} = operatorname {SET} ( operatorname {CYC} ({ mathcal {Z}})))} a získá Stirlingova čísla prvního druhu. Odtud název "Stirlingova čísla druhého druhu."
Rozklad je ekvivalentní EGF
B ( z ) = exp ( exp z − 1 ) . { Displaystyle B (z) = exp left ( exp z-1 right).} Diferencovat získat
d d z B ( z ) = exp ( exp z − 1 ) exp z = B ( z ) exp z , { displaystyle { frac {d} {dz}} B (z) = exp left ( exp z-1 right) exp z = B (z) exp z,} což z toho vyplývá
B n + 1 = ∑ k = 0 n ( n k ) B k , { displaystyle B_ {n + 1} = součet _ {k = 0} ^ {n} {n zvolit k} B_ {k},} konvolucí exponenciální generující funkce a protože diferenciace EGF snižuje první koeficient a posouvá se B n +1z n /n !.
EGF Stirlingových čísel druhého druhu se získá označením každé podmnožiny, která jde do oddílu, výrazem U { displaystyle { mathcal {U}} ,}
B = SOUBOR ( U × SOUBOR ≥ 1 ( Z ) ) . { displaystyle { mathcal {B}} = operatorname {SET} ({ mathcal {U}} times operatorname {SET} _ { geq 1} ({ mathcal {Z}})))} V překladu k generujícím funkcím získáme
B ( z , u ) = exp ( u ( exp z − 1 ) ) . { Displaystyle B (z, u) = exp left (u left ( exp z-1 right) right).} Tento EGF poskytuje vzorec pro Stirlingova čísla druhého druhu:
{ n k } = n ! [ u k ] [ z n ] B ( z , u ) = n ! [ z n ] ( exp z − 1 ) k k ! { displaystyle left {{ begin {matrix} n k end {matrix}} right } = n! [u ^ {k}] [z ^ {n}] B (z, u) = n! [z ^ {n}] { frac {( exp z-1) ^ {k}} {k!}}} nebo
n ! [ z n ] 1 k ! ∑ j = 0 k ( k j ) exp ( j z ) ( − 1 ) k − j { displaystyle n! [z ^ {n}] { frac {1} {k!}} sum _ {j = 0} ^ {k} {k vybrat j} exp (jz) (- 1) ^ {kj}} což zjednodušuje na
n ! k ! ∑ j = 0 k ( k j ) ( − 1 ) k − j j n n ! = 1 k ! ∑ j = 0 k ( k j ) ( − 1 ) k − j j n . { displaystyle { frac {n!} {k!}} součet _ {j = 0} ^ {k} {k vybrat j} (- 1) ^ {kj} { frac {j ^ {n} } {n!}} = { frac {1} {k!}} sum _ {j = 0} ^ {k} {k vyberte j} (- 1) ^ {kj} j ^ {n}. } Reference Ronald Graham , Donald Knuth , Oren Patashnik (1989): Konkrétní matematika Addison – Wesley, ISBN 0-201-14236-8D. S. Mitrinovic , Sur une classe de nombre spoléhá na aux nombres de Stirling C. R. Acad. Sci. Paris 252 (1961), 2354–2356.A. C. R. Belton, Monotónní Poissonův proces , v: Kvantová pravděpodobnost (M. Bozejko, W. Mlotkowski a J. Wysoczanski, eds.), Banach Center Publications 73, Polská akademie věd, Varšava, 2006 Milton Abramowitz a Irene A. Stegun , Příručka matematických funkcí se vzorci, grafy a matematickými tabulkami , USGPO, 1964, Washington DC, ISBN 0-486-61272-4
![[z ^ {n}]](https://wikimedia.org/api/rest_v1/media/math/render/svg/16378bf9f6c602c971e93212ae4fc4a18658fa9f)
![{ displaystyle G (z, u) = exp left (u log { frac {1} {1-z}} right) = left ({ frac {1} {1-z}} vpravo) ^ {u} = sum _ {n = 0} ^ { infty} sum _ {k = 0} ^ {n} left [{ begin {matrix} n k end {matrix} } right] u ^ {k} , { frac {z ^ {n}} {n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9b03c145e3a6dca53c5b8b983a0d099886606ed)
![{ displaystyle (-1) ^ {n-k} doleva [{ začátek {matice} n k konec {matice}} doprava].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ee2adc72f418a3b3db07de990da9d16ef8f9317)
![{ displaystyle H (z, u) = G (-z, -u) = doleva ({ frac {1} {1 + z}} doprava) ^ {- u} = (1 + z) ^ { u} = sum _ {n = 0} ^ { infty} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k end {matrix}} right] u ^ {k} , { frac {z ^ {n}} {n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b593bd2afc37e0074a4e4f72d0883afa36c54504)
![{ displaystyle (1 + z) ^ {u} = součet _ {n = 0} ^ { infty} {u vybrat n} z ^ {n} = součet _ {n = 0} ^ { infty } { frac {z ^ {n}} {n!}} sum _ {k = 0} ^ {n} (- 1) ^ {nk} left [{ begin {matrix} n k end {matrix}} right] u ^ {k} = sum _ {k = 0} ^ { infty} u ^ {k} sum _ {n = k} ^ { infty} { frac {z ^ {n}} {n!}} (- 1) ^ {nk} left [{ begin {matrix} n k end {matrix}} right] = e ^ {u log (1+ z)}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a3a9c96d6694c2cb22364df476a972e8aa08d41)
![sum _ {{k = 0}} ^ {n} (- 1) ^ {k} left [{ begin {matrix} n k end {matrix}} right] = (- 1) ^ {n} n !.](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0fb7d6d9e8c79703544a251891d048c88d922f9)
![H (z, -1) = { frac {1} {1 + z}} quad { mbox {a tedy}} quad n! [Z ^ {n}] H (z, -1) = ( -1) ^ {n} n !.](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b163f781f1c4e4fcb912cd5458123426b318c88)
![sum _ {{n = k}} ^ { infty} left [{ begin {matrix} n k end {matrix}} right] { frac {z ^ {n}} {n! }} = { frac { left ( log (1 + z) right) ^ {k}} {k!}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97f3bf2836729d248d4b9a372dddcdd648eeb4d8)
![[u ^ {k}] H (z, u) = [u ^ {k}] exp left (u log (1 + z) right) = { frac { left ( log (1+ z) right) ^ {k}} {k!}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6c88aea4798576902f921bb1268b67347580bbe)
![left {{ begin {matrix} n k end {matrix}} right } = n! [u ^ {k}] [z ^ {n}] B (z, u) = n! [z ^ {n}] { frac {( exp z-1) ^ {k}} {k!}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a67aa854ea914d34f8be2d5f6ea7f175ce9d75c)
![n! [z ^ {n}] { frac {1} {k!}} sum _ {{j = 0}} ^ {k} {k vyberte j} exp (jz) (- 1) ^ {{kj}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e127b7f0efa5602037974f23a1a513f1e51fc65a)
