Stirlingovo číslo

V matematice se Stirlingova čísla objevují v několika kombinačních problémech . Jejich jméno je odvozeno od Jamese Stirlinga , který je seznámil s XVIII. Stoletím  . Existují tři druhy, nazývané Stirlingova čísla se znaménkem a bez znaménka prvního druhu , a Stirlingova čísla druhého druhu .

Zápisy

Pro Stirlingova čísla se používají různé notace, včetně:

• "podepsaná" Stirlingova čísla prvního druhu:s(ne,k){\ displaystyle s (n, k)} ;
• „Nepodepsaná“ Stirlingova čísla prvního druhu:|s(ne,k)|=vs.(ne,k)=[nek]{\ displaystyle | s (n, k) | = c (n, k) = \ doleva [{n \ nahoře k} \ doprava]} ;
• Stirlingova čísla druhého druhu:S(ne,k)=Sne(k)={nek}{\ displaystyle S (n, k) = S_ {n} ^ {(k)} = \ vlevo \ {{n \ nahoře k} \ vpravo \}}.

Zápis s držáky, podobných těm, které používají pro kombinační číslo , je vzhledem k Jovan Karamata , který navrhla v roce 1935. Jeho použití bylo podpořeno Donald Knuth , ale kromě svých pochybných ergonomii, to s sebou nese riziko záměny s spárování Gaussovy koeficienty (uvedené v článku „  q -analog  “). Proto se omezíme pro každý ze tří typů čísel na první odpovídající notaci výše.

Stirlingovo číslo prvního druhu

Tyto počty Stirling prvního druhu podepsané s ( n , k ) jsou koeficienty vývoje klesající factorial ( x ) n , to znamená

(X)ne=X(X-1)(X-2)...(X-ne+1)=∑k=0nes(ne,k)Xk{\ displaystyle (x) _ {n} = x (x-1) (x-2) \ ldots (x-n + 1) = \ součet _ {k = 0} ^ {n} s (n, k) x ^ {k}}

( ( x ) 0 = 1, protože se jedná o prázdný produkt ).

Číslo s ( n , k ) má stejné znaménko jako (–1) n - k .

Tyto počty Stirling prvního druhu unsigned | s ( n , k ) | ( absolutní hodnoty předchozích) jsou koeficienty vývoje rostoucího faktoriálu ( x ) n , to znamená, že

(X)ne=X(X+1)(X+2)...(X+ne-1)=∑k=0ne|s(ne,k)|Xk{\ displaystyle (x) ^ {n} = x (x + 1) (x + 2) \ ldots (x + n-1) = \ součet _ {k = 0} ^ {n} | s (n, k ) | x ^ {k}}.

Mají také kombinatorickou definici: srov. § # Kombinatorický výklad níže.

Tabulka hodnot

Zde je tabulka uvádí některé hodnoty z s ( n , k ) ( A008275 a A008276 z OEIS ), který lze vypočítat řádek po řádku díky vztah opakování z následujících §, stejně jako Pascalova trojúhelníku  :   

n  \  k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	–1	1
3	0	2	–3	1
4	0	–6	11	–6	1
5	0	24	–50	35	–10	1
6	0	–120	274	–225	85	–15	1
7	0	720	–1764	1624	–735	175	–21	1
8	0	–5040	13068	–13132	6769	–1960	322	–28	1
9	0	40320	–109584	118124	–67284	22449	–4536	546	–36	1

Vzorec opakování

Podepsaná Stirlingova čísla prvního druhu ověřují relaci opakování

∀k⩾1s(ne+1,k)=s(ne,k-1)-nes(ne,k){\ displaystyle \ forall k \ geqslant 1 \ quad s (n + 1, k) = s (n, k-1) -ns (n, k)}

s původními podmínkami

s(0,0)=1Et∀ne⩾1s(ne,0)=s(0,ne)=0{\ displaystyle s (0,0) = 1 \ quad {\ rm {et}} \ quad \ forall n \ geqslant 1 \ quad s (n, 0) = s (0, n) = 0}.

Jejich absolutní hodnoty ověřují (se stejnými počátečními podmínkami) relaci opakování

∀k⩾1|s(ne+1,k)|=|s(ne,k-1)|+ne|s(ne,k)|{\ displaystyle \ forall k \ geqslant 1 \ quad | s (n + 1, k) | = | s (n, k-1) | + n | s (n, k) |}.

Každý ze dvou relací opakování lze odvodit od druhého. První navíc vyplývá z relace opakování klesajících faktoriálů:

(X)ne+1=X(X)ne-ne(X)ne{\ displaystyle (x) _ {n + 1} = x (x) _ {n} -n (x) _ {n}}

a za druhé kombinatorické uvažování nebo vztah opakování rostoucích faktoriálů:

(X)ne+1=X(X)ne+ne(X)ne{\ displaystyle (x) ^ {n + 1} = x (x) ^ {n} + n (x) ^ {n}}.

Jednoduché identity

Všimněte si, že

∀k>nes(ne,k)=0{\ displaystyle \ forall k> n \ quad s (n, k) = 0}, s(ne,ne)=1,s(ne,1)=(-1)ne-1(ne-1)!,s(ne,ne-1)=-(ne2){\ Displaystyle s (n, n) = 1, \ quad s (n, 1) = (- 1) ^ {n-1} (n-1) !, \ quad s (n, n-1) = - {n \ vyberte 2}}, s(ne,ne-2)=3ne-14(ne3),s(ne,ne-3)=-(ne2)(ne4){\ displaystyle s (n, n-2) = {\ frac {3n-1} {4}} {n \ zvolit 3}, \ quad s (n, n-3) = - {n \ zvolit 2} { n \ vyberte 4}}.

Existují i ​​jiné identity

s(ne,2)=(-1)ne(ne-1)!Hne-1{\ displaystyle s (n, 2) = (- 1) ^ {n} (n-1)! \; H_ {n-1}}

kde H n je harmonické číslo a

s(ne,3)=(-1)ne-1(ne-1)!2[(Hne-1)2-Hne-1(2)]{\ displaystyle s (n, 3) = (- 1) ^ {n-1} {\ frac {(n-1)!} {2}} \ left [(H_ {n-1}) ^ {2} -H_ {n-1} ^ {(2)} \ vpravo]}

kde H n ( m ) je zobecněné harmonické číslo .

Podobné vztahy spojují Stirlingova čísla prvního druhu s Bernoulliho polynomy . Velké množství vztahů souvisejících se Stirlingovými čísly skrývá podobné vztahy související s binomickými koeficienty . Studium vztahu mezi těmito dvěma čísly je ombralním kalkulem a je důležitou oblastí Shefferovy teorie sekvencí .

Explicitní vzorce

Můžeme ukázat následující vztah mezi Stirlingovými čísly prvního a druhého druhu:

s(ne,m)=∑k=0ne-m(-1)k(ne-1+kne-m+k)(2ne-mne-m-k)S(ne-m+k,k){\ displaystyle s (n, m) = \ součet _ {k = 0} ^ {nm} (- 1) ^ {k} {\ binom {n-1 + k} {n-m + k}} {\ binom { 2n-m} {nmk}} S (nm + k, k)}

tedy pomocí vzorce pro tyto, které budou uvedeny níže:

s(ne,m)=∑k=0ne-m∑j=0k(-1)2k-jk!(ne-1+kne-m+k)(2ne-mne-m-k)(kj)jne-m+k{\ displaystyle s (n, m) = \ součet _ {k = 0} ^ {nm} \ součet _ {j = 0} ^ {k} {\ frac {(-1) ^ {2k-j}} { k!}} {\ binom {n-1 + k} {nm + k}} {\ binom {2n-m} {nmk}} {k \ vyberte j} j ^ {nm + k}}

nebo znovu po zjednodušení:

s(ne,m)=(2ne-m)!(m-1)!∑k=0ne-m1(ne+k)(ne-m-k)!(ne-m+k)!∑j=0k(-1)jjne-m+kj!(k-j)!{\ displaystyle s (n, m) = {\ frac {(2n-m)!} {(m-1)!}} \ součet _ {k = 0} ^ {nm} {\ frac {1} {( n + k) (nmk)! (nm + k)!}} \ sum _ {j = 0} ^ {k} {\ frac {(-1) ^ {j} j ^ {nm + k}} {j ! (kj)!}}}.

Funkce generátoru

Manipulací s funkcí generátoru můžeme demonstrovat několik identit  :

(1+t)X=∑ne=0∞(Xne)tne=∑ne=0∞tnene!∑k=0nes(ne,k)Xk=∑k=0∞Xk∑ne=k∞tnene!s(ne,k)=EXln⁡(1+t){\ displaystyle (1 + t) ^ {x} = \ součet _ {n = 0} ^ {\ infty} {x \ zvolit n} t ^ {n} = \ součet _ {n = 0} ^ {\ infty } {\ frac {t ^ {n}} {n!}} \ sum _ {k = 0} ^ {n} s (n, k) x ^ {k} = \ sum _ {k = 0} ^ { \ infty} x ^ {k} \ sum _ {n = k} ^ {\ infty} {\ frac {t ^ {n}} {n!}} s (n, k) = \ operatorname {e} ^ { x \ ln (1 + t)}}.

Zejména můžeme obrátit pořadí součtu a vzít derivace, pak opravit t nebo x .

Konečné částky

∑k=0ne(-1)ks(ne,k)=(-1)nene!{\ displaystyle \ sum _ {k = 0} ^ {n} (- 1) ^ {k} s (n, k) = (- 1) ^ {n} n!}

Nekonečné částky

∑ne=m∞s(ne,m)Xnene!=(ln⁡(1+X))mm!{\ displaystyle \ sum _ {n = m} ^ {\ infty} s (n, m) {\ frac {x ^ {n}} {n!}} = {\ frac {\ left (\ ln (1+ x) \ right) ^ {m}} {m!}}}

platí pro . X<1{\ displaystyle x <1}

Kombinatorický výklad

Absolutní hodnota počtu Stirling prvního druhu počítá počet permutací z n objektů složených z přesně k disjunktní cykly . Například odpovídá skutečnosti, že symetrická skupina má tři permutace formuláře s(4,2)=11{\ displaystyle s (4,2) = 11} S4{\ displaystyle S_ {4}}

(∗∗)(∗∗){\ displaystyle (**) (**)} - 2 cykly délky 2

a osm permutací formuláře

(∗∗∗){\ displaystyle (***)} - 1 cyklus délky 3 a 1 cyklus délky 1.

Absolutní hodnota čísla Stirling prvního druhu také počítá počet permutací z n objekty s přesně K Records . Tato identita mezi záznamy a cykly vyplývá ze základní korespondence Foata . Forma produktu generující řady Stirlingových čísel prvního druhu vyplývá z nezávislosti podmínek Lehmerova kódu permutace, kódu úzce spojeného se záznamy permutace. Interpretace Stirlingových čísel jako funkce počtu záznamů vysvětluje výskyt Stirlingových čísel v analýze maximálního vyhledávacího algoritmu, což je první analýza algoritmu popsaná v Knuthově zakladatelské knize The Art of Computer Programming .

Stirlingovo číslo druhého druhu

Kombinatorická definice

Tyto počty Stirling druhého druhu S ( n , k ), jsou definovány combinatorily do tří ekvivalentních způsoby:

• S ( n , k ) je počet relací ekvivalence majících k tříd ekvivalence definovaných na množině n prvků;
• S ( n , k ) je počet oddílů sady s n prvky do k podmnožin;
• k ! × S ( n , k ) je počet surjekcí množiny s n prvky na množině s k prvky. Pozor, toto poslední číslo je také často označováno S ( n , k ) nebo s ( n , k ) .

Explicitní vzorec

Stirlingova čísla druhého druhu jsou dána explicitním vzorcem

S(ne,k)=1k!∑j=0k(-1)k-j(kj)jne{\ displaystyle S (n, k) = {\ frac {1} {k!}} \ součet _ {j = 0} ^ {k} (- 1) ^ {kj} {\ binom {k} {j} } j ^ {n}},

který se získá například poznámkou, že počet surjection (ze sady s n prvky na sadu s k prvky) lze spočítat podle vzorce zahrnutí-vyloučení  : počítáme všechny aplikace minus ty, které nedosahují určitého prvku, čím více nedosáhne dvou prvků, tím méně ...

Vztah opakování

Z kombinatorické definice můžeme také ukázat, že tato čísla uspokojují relaci opakování

∀ne,k⩾1S(ne,k)=S(ne-1,k-1)+kS(ne-1,k){\ displaystyle \ forall n, k \ geqslant 1 \ quad S (n, k) = S (n-1, k-1) + kS (n-1, k)}

s původními podmínkami

S(0,0)=1Et∀ne⩾1S(ne,0)=S(0,ne)=0{\ Displaystyle S (0,0) = 1 \ quad {\ rm {et}} \ quad \ forall n \ geqslant 1 \ quad S (n, 0) = S (0, n) = 0}.

Algebraická charakterizace

Z výše uvedeného odvozujeme vztah opakování

∑k=0neS(ne,k)(X)k=Xne{\ displaystyle \ sum _ {k = 0} ^ {n} S (n, k) (X) _ {k} = X ^ {n}},

kde ( symbol Pochhammer ), (X)k=X(X-1)...(X-k+1){\ displaystyle (X) _ {k} = X (X-1) ... (X-k + 1)}

který poskytuje algebraickou definici Stirlingových čísel druhého druhu, ekvivalentní počáteční kombinační definici.

Tento vzorec se používá například při vyjádření součtů .∑k=1nekp{\ displaystyle \ sum _ {k = 1} ^ {n} k ^ {p}}

Tabulka hodnot

Zde jsou některé hodnoty Stirling počtu druhého druhu (apartmány A008277 a A008278 z OEIS )   

n  \  k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1
8	0	1	127	966	1701	1050	266	28	1
9	0	1	255	3025	7770	6951	2646	462	36	1

Jednoduché identity

Máme například S ( n , n ) = 1 ,

S(ne,ne-1)=(ne2){\ displaystyle S (n, n-1) = {\ binom {n} {2}}}

a

S(ne,2)=2ne-1-1{\ displaystyle S (n, 2) = 2 ^ {n-1} -1}.

Celkový počet oddílů sady s n prvky,

Bne=∑k=1neS(ne,k){\ displaystyle B_ {n} = \ součet _ {k = 1} ^ {n} S (n, k)},

je n- té číslo Bell .

Vztah k Poissonově rozdělení

Pokud X je náhodná proměnná sledující Poissonovo rozdělení se střední hodnotou λ, pak je její n -tý okamžik

E(Xne)=∑k=1neS(ne,k)λk{\ displaystyle E (X ^ {n}) = \ součet _ {k = 1} ^ {n} S (n, k) \ lambda ^ {k}}.

Zejména n- tý okamžik Poissonova rozdělení střední hodnoty 1 je přesně počet oddílů množiny velikosti n , což je n- té číslo Bell ( Dobinského vzorec ).

Vzájemný vztah

Podle jejich algebraické charakterizace tvoří Stirlingova čísla prvního a druhého druhu, uspořádaná, jak je uvedeno v tabulkách hodnot výše, ve dvou nekonečných trojúhelníkových maticích , dvě matice přechodu (v jednom směru a ve druhém) mezi dvě báze z prostoru polynomů  : na kanonický základ z monomials X k a základem z Pochhammer symbolů X ( X - 1) ( X - 2) ... ( X - k- + 1) . Skutečnost, že tyto dvě matice jsou naproti sobě, vede k:

∑m≤k≤nes(k,m)S(ne,k)=∑m≤k≤neS(k,m)s(ne,k)=δmne{\ Displaystyle \ suma _ {m \ leq k \ leq n} s (k, m) S (n, k) = \ součet _ {m \ leq k \ leq n} S (k, m) s (n, k) = \ delta _ {mn}}

kde je symbol Kronecker . δmne{\ displaystyle \ delta _ {mn}}

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „  Stirlingovo číslo  “ ( viz seznam autorů ) .

1. Ještě další používají Abramowitz a Stegun .
2. (in) Knuth, Dvě poznámky k hodnocení (zdroj TeX ).
3. Louis Comtet , Elementární kombinatorická analýza , Techniques Ingénieur, kol.  "Betonová matematika",1997, 687  s. ( ISBN  978-2-84180-981-3 , číst online ) , s.  24.
4. Demonstraci viz například Louis Comtet, Combinatorial Analysis , t.  2, PUF ,1970, str.  51.
5. Comtet 1970 , str.  38.
6. Viz také toto opravené cvičení na Wikiversity .
7. Viz například Louis Comtet, Analyse Combinatoratique Profit , Techniques Ingénieur, kol.  "Betonová matematika",2003( číst online ) , s.  3-4.
8. Comtet 2003 , s.  5.
9. vektorový prostor K [ X ] o polynomů v jedné proměnné v průběhu komutativním pole K , nebo dokonce bez modul [ X ] polynomů s koeficienty v komutativní kruhu A .
10. Abramowitz a Stegun , str.  825.

Podívejte se také

Bibliografie

• (en) Milton Abramowitz a Irene Stegun , Příručka matematických funkcí se vzorci, grafy a matematickými tabulkami [ podrobnosti vydání ] ( číst online ), „Stirling čísla“, § 24.1.3-4, p. 824-825
• (en) Louis Comtet , Advanced Combinatorics: The Art of Finite and Infinite Expansions , D. Reidel ,1974, 343  s. ( ISBN  978-90-277-0441-2 , číst online )
• (en) Victor Adamchik, „  On Stirling Numbers and Euler Sums  “ , Journal of Computational and Applied Mathematics  (en) , sv.  79,1997, str.  119-130 ( číst online )
• (en) Arthur T. Benjamin , Gregory O. Preston a Jennifer J. Quinn, „  Stirlingovo setkání s harmonickými čísly  “ , Mathematics Magazine , roč.  75, n O  22002, str.  95-103 ( číst online )
• (en) JM Sixdeniers, KA Penson a AI Solomon, „  Extended Bell and Stirling Numbers From Hypergeometric Exponentiation  “ , Journal of Integer Sequences , sv.  4, n O  01.1.4,2001( číst online )
• (en) Hsien-Kuei Hwang , „  Asymptotic Expansions for the Stirling numbers of the first kind  “ , Journal of Combinatorial Theory , a, sv.  71, n O  21995, str.  343-351 ( DOI  10.1016 / 0097-3165 (95) 90010-1 , číst online )

Související články

• Lehmerův kód
• Základní korespondence Foata
• Cykly a pevné body
• Eulerianovo číslo
• Počet Lah
• Polynom zvonů
• Dotykový polynom
• Polynomiální sekvence
• Stirlingova čísla a exponenciální generující funkce v symbolické kombinatorice  ( fr )
• Transformace Stirling  (en)

externí odkazy

• (en) Eric W. Weisstein , „  Stirlingovo číslo prvního druhu  “ , na MathWorld
• (en) E. Weisstein, „  Stirlingovo číslo druhého druhu  “ , na MathWorld
• (en) rmilson (146), „  Stirlingova čísla prvního druhu  “ , na PlanetMath
• (en) rmilson (146), „  Stirlingova čísla druhého druhu  “ , na PlanetMath

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">