Stirling szám

A matematika , Stirling számok jelennek meg számos kombinatorikai problémák . Ezek nevüket James Stirling , aki bevezette őket a XVIII th  században. Háromféle van, az úgynevezett aláírt és aláíratlan Stirling-számok , és a második típusú Stirling-számok .

Jelölések

A Stirling-számokhoz különféle jelöléseket használnak, többek között:

• "aláírt" első típusú Stirling számok:s(nem,k){\ displaystyle s (n, k)} ;
• „Aláíratlan” első típusú Stirling számok:|s(nem,k)|=vs.(nem,k)=[nemk]{\ displaystyle | s (n, k) | = c (n, k) = \ balra [{n \ atop k} \ right]} ;
• Második stirling számok:S(nem,k)=Snem(k)={nemk}{\ displaystyle S (n, k) = S_ {n} ^ {(k)} = \ bal \ {{n \ at k} tetején \ jobb \}}.

A zárójeles jelölés, hasonlóan a binomiális együtthatókhoz , Jovan Karamatának köszönhető , aki 1935-ben javasolta. Használatát Donald Knuth ösztönözte, de megkérdőjelezhető ergonómiája mellett a binomiállal való összetévesztés kockázatát is magában hordozza. Gauss-együtthatók (a „ q -analógus  ” cikkben  mutatjuk be ). Ezért a három számtípus mindegyikére a fenti első megfelelő jelöléssel korlátozódunk.

Stirling első fajta száma

Az első típusú s ( n , k ) Stirling-számok a csökkenő faktoriális ( x ) n alakulásának együtthatói , azaz

(x)nem=x(x-1)(x-2)...(x-nem+1)=∑k=0nems(nem,k)xk{\ displaystyle (x) _ {n} = x (x-1) (x-2) \ ldots (x-n + 1) = \ összeg _ {k = 0} ^ {n} s (n, k) x ^ {k}}

( ( x ) 0 = 1, mert üres termék ).

Az s ( n , k ) számnak ugyanaz a jele, mint (–1) n - k .

Az első fajta Stirling-számok aláíratlanul | s ( n , k ) | ( az előzőek abszolút értékei ) a növekvő faktoriális ( x ) n alakulásának együtthatói , vagyis

(x)nem=x(x+1)(x+2)...(x+nem-1)=∑k=0nem|s(nem,k)|xk{\ displaystyle (x) ^ {n} = x (x + 1) (x + 2) \ ldots (x + n-1) = \ összeg _ {k = 0} ^ {n} | s (n, k ) | x ^ {k}}.

Kombinatorikus meghatározásuk is van: vö. § # Kombinatorikus értelmezés az alábbiakban.

Értéktáblázat

Itt van egy táblázat, amelyben néhány értékeit s ( n , k ) ( A008275 és A008276 a OEIS-ben ), amely ki tudjuk számítani soronként köszönhetően a rekurzív sorozat az alábbi §, valamint a Pascal-háromszög  :   

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

Megismétlődési képlet

Az első típusú aláírt Stirling-számok igazolják az ismétlődési összefüggést

∀k⩾1s(nem+1,k)=s(nem,k-1)-nems(nem,k){\ displaystyle \ összes k \ geqslant 1 \ quad s (n + 1, k) = s (n, k-1) -ns (n, k)}

a kezdeti feltételekkel

s(0,0)=1et∀nem⩾1s(nem,0)=s(0,nem)=0{\ displaystyle s (0,0) = 1 \ quad {\ rm {et}} \ quad \ összes n \ geqslant 1 \ quad s (n, 0) = s (0, n) = 0}.

Abszolút értékeik (ugyanazokkal a kezdeti feltételekkel) igazolják a megismétlődés összefüggését

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

A két ismétlődési kapcsolat mindkettőből levezethető. Sőt, az első a csökkenő tényezők ismétlődő viszonyából következik:

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

a második pedig a kombinatorikus érvelés vagy a növekvő faktoriálok megismétlődésének viszonya:

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

Egyszerű identitások

Vegye figyelembe, hogy

∀k>nems(nem,k)=0{\ displaystyle \ összes k> n \ quad s (n, k) = 0}, s(nem,nem)=1,s(nem,1)=(-1)nem-1(nem-1)!,s(nem,nem-1)=-(nem2){\ displaystyle s (n, n) = 1, \ quad s (n, 1) = (- 1) ^ {n-1} (n-1) !, \ quad s (n, n-1) = - {n \ select 2}}, s(nem,nem-2)=3nem-14(nem3),s(nem,nem-3)=-(nem2)(nem4){\ displaystyle s (n, n-2) = {\ frac {3n-1} {4}} {n \ select 3}, \ quad s (n, n-3) = - {n \ select 2} { n \ válassza a 4}} lehetőséget.

Vannak más identitások is, például

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

ahol H n egy harmonikus szám és

s(nem,3)=(-1)nem-1(nem-1)!2[(Hnem-1)2-Hnem-1(2)]{\ displaystyle s (n, 3) = (- 1) ^ {n-1} {\ frac {(n-1)!} {2}} \ balra [(H_ {n-1}) ^ {2} -H_ {n-1} ^ {(2)} \ jobbra]}

ahol H n ( m ) egy általánosított harmonikus szám .

Hasonló kapcsolatok kapcsolják az első fajta Stirling-számokat a Bernoulli-polinomokhoz . A Stirling-számokkal kapcsolatos összefüggések nagy száma elrejti a binomiális együtthatókhoz kapcsolódó hasonló kapcsolatokat . A két szám kapcsolatának vizsgálata az ombrális számítás, és Sheffer szekvenciaelméletének fontos területe .

Kifejezett képletek

A következő összefüggést mutathatjuk meg az első és a második fajta Stirling-számok között:

s(nem,m)=∑k=0nem-m(-1)k(nem-1+knem-m+k)(2nem-mnem-m-k)S(nem-m+k,k){\ displaystyle s (n, m) = \ sum _ {k = 0} ^ {nm} (- 1) ^ {k} {\ binom {n-1 + k} {n-m + k}} {\ binom { 2n-m} {nmk}} S (nm + k, k)}

ezért az alábbiakban megadott képletet használva:

s(nem,m)=∑k=0nem-m∑j=0k(-1)2k-jk!(nem-1+knem-m+k)(2nem-mnem-m-k)(kj)jnem-m+k{\ displaystyle s (n, m) = \ sum _ {k = 0} ^ {nm} \ sum _ {j = 0} ^ {k} {\ frac {(-1) ^ {2k-j}} { k!}} {\ binom {n-1 + k} {nm + k}} {\ binom {2n-m} {nmk}} {k \ select j} j ^ {nm + k}}

vagy az egyszerűsítés után:

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

Generátor funkció

A generátor funkciójának manipulálásával több azonosságot is bemutathatunk  :

(1+t)x=∑nem=0∞(xnem)tnem=∑nem=0∞tnemnem!∑k=0nems(nem,k)xk=∑k=0∞xk∑nem=k∞tnemnem!s(nem,k)=exln⁡(1+t){\ displaystyle (1 + t) ^ {x} = \ sum _ {n = 0} ^ {\ infty} {x \ select n} t ^ {n} = \ sum _ {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) = \ operátor neve {e} ^ { x \ ln (1 + t)}}.

Különösen megfordíthatjuk az összegzés sorrendjét, és derivatívákat vehetünk fel, majd rögzíthetjük t vagy x .

Véges összegek

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

Végtelen összegek

∑nem=m∞s(nem,m)xnemnem!=(ln⁡(1+x))mm!{\ displaystyle \ sum _ {n = m} ^ {\ infty} s (n, m) {\ frac {x ^ {n}} {n!}} = {\ frac {\ balra (\ ln (1+) x) \ right) ^ {m}} {m!}}}

-ig érvényes . x<1{\ displaystyle x <1}

Kombinatorikus értelmezés

Az abszolút értéke a Stirling szám az első fajta számít száma permutációk az n objektumok tagjai pontosan k diszjunkt ciklusok . Például megfelel annak a ténynek, hogy a szimmetrikus csoportnak három alakja van s(4,2)=11.{\ displaystyle s (4,2) = 11} S4{\ displaystyle S_ {4}}

(∗∗)(∗∗){\ displaystyle (**) (**)} - 2 ciklus 2 hosszúsággal

és a forma nyolc permutációja

(∗∗∗){\ displaystyle (***)} - 1 ciklus 3 hosszúságú és 1 ciklus 1 hosszúságú.

Az abszolút értéke a Stirling szám az első fajta is számolja a permutációk az n rendelkező objektumok pontosan k feljegyzések . Ez a rekordok és ciklusok közötti azonosság a Foata alapvető levelezéséből adódik . Az első fajta Stirling-számok generáló sorozatának termékformája a permutáció Lehmer-kódjának feltételeinek függetlenségéből származik , amely kód szorosan kapcsolódik a permutáció rekordjaihoz. A Stirling-számok értelmezése a rekordok számának függvényében magyarázza a Stirling-számok megjelenését a maximális keresési algoritmus elemzésében, amely az első algoritmus-elemzés, amelyet Knuth alapító könyve, a Számítógépes programozás művészete tárgyal .

Stirling száma a második fajtának

Kombinatorikus meghatározás

A második típusú S ( n , k ) Stirling-számokat kombinatív módon, három egyenértékű módon határozzuk meg:

• S ( n , k ) az a szám, az egyenértékűség kapcsolatok , amelynek K ekvivalencia osztályok meghatározott egy sor, az n elemek;
• S ( n , k ) az a szám, partíciók tartalmazó készlet n elemek k részhalmazok;
• k ! × S ( n , k )a k eleműhalmaz n eleműhalmazának túladagolása . Figyelem, ezt az utolsó számot gyakran megjegyezzük S ( n , k ) vagy s ( n , k ) értékkel is .

Kifejezett képlet

A második fajta Stirling-számokat az explicit képlet adja meg

S(nem,k)=1k!∑j=0k(-1)k-j(kj)jnem{\ displaystyle S (n, k) = {\ frac {1} {k!}} \ sum _ {j = 0} ^ {k} (- 1) ^ {kj} {\ binom {k} {j} } j ^ {n}},

amelyet például úgy kapunk, hogy megjegyezzük, hogy a túladagolások számát ( n elemű halmazból k elemű halmazig) meg lehet számlálni a befogadás-kizárási képlettel  : az összes alkalmazást megszámoljuk, levonva azokat, amelyek nem érnek el egy bizonyos elemet, minél több nem éri el a két elemet, annál kevesebb ...

Ismétlődés relációja

A kombinatorikus definícióból azt is megmutathatjuk, hogy ezek a számok kielégítik az ismétlődési összefüggést

∀nem,k⩾1S(nem,k)=S(nem-1,k-1)+kS(nem-1,k){\ displaystyle \ összes n, k \ geqslant 1 \ quad S (n, k) = S (n-1, k-1) + kS (n-1, k)}

a kezdeti feltételekkel

S(0,0)=1et∀nem⩾1S(nem,0)=S(0,nem)=0{\ displaystyle S (0,0) = 1 \ quad {\ rm {et}} \ quad \ összes n \ geqslant 1 \ quad S (n, 0) = S (0, n) = 0}.

Algebrai jellemzés

A fenti megismétlődési összefüggésből következtethetünk

∑k=0nemS(nem,k)(x)k=xnem{\ displaystyle \ sum _ {k = 0} ^ {n} S (n, k) (X) _ {k} = X ^ {n}},

hol ( Pochhammer szimbólum ), (x)k=x(x-1)...(x-k+1){\ displaystyle (X) _ {k} = X (X-1) ... (X-k + 1)}

amely a második típusú Stirling-számok algebrai meghatározását nyújtja, amely megegyezik a kezdeti kombinatorikus definícióval.

Ezt a képletet használjuk például összegek kifejezésére .∑k=1nemko{\ displaystyle \ sum _ {k = 1} ^ {n} k ^ {p}}

Értéktáblázat

Íme néhány Stirling-szám második értékének értéke ( OEIS A008277 és A008278 csomagok )   

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

Egyszerű identitások

Például S ( n , n ) = 1 ,

S(nem,nem-1)=(nem2){\ displaystyle S (n, n-1) = {\ binom {n} {2}}}

és

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

N elemű halmaz partícióinak teljes száma ,

Bnem=∑k=1nemS(nem,k){\ displaystyle B_ {n} = \ sum _ {k = 1} ^ {n} S (n, k)},

az n- edik harangszám .

Kapcsolat a Poisson-eloszlással

Ha X egy véletlen változó, amely Poisson-eloszlást követ λ átlaggal, akkor n- edik momentuma az

E(xnem)=∑k=1nemS(nem,k)λk{\ displaystyle E (X ^ {n}) = \ sum _ {k = 1} ^ {n} S (n, k) \ lambda ^ {k}}.

Pontosabban, az 1. átlag Poisson-eloszlásának n- edik momentuma pontosan az n méretű halmaz partícióinak száma , amely az n- edik Bell-szám ( Dobinski-formula ).

Kölcsönös kapcsolat

Algebrai jellemzésük szerint az első és a második fajta Stirling-számok, amelyek a fenti értéktáblázatokhoz hasonlóan két végtelen háromszögmátrixban vannak elrendezve , alkotják a két átjárási mátrixot (az egyik és a másik irányban). két bázisok a tér polinomok  : a kanonikus alapján az egytagú X k és az alapján a Pochhammer szimbólumok X ( X - 1) ( X - 2) ... ( X - k + 1) . Az a tény, hogy ez a két mátrix ellentétes egymással, a következőket eredményezi:

∑m≤k≤nems(k,m)S(nem,k)=∑m≤k≤nemS(k,m)s(nem,k)=δmnem{\ displaystyle \ sum _ {m \ leq k \ leq n} s (k, m) S (n, k) = \ sum _ {m \ leq k \ leq n} S (k, m) s (n, k) = \ delta _ {mn}}

hol van a Kronecker szimbólum . δmnem{\ displaystyle \ delta _ {mn}}

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy egészben az angol Wikipedia "  Stirling number  " című cikkéből származik ( lásd a szerzők felsorolását ) .

1. Megint másokat Abramowitz és Stegun használ .
2. (in) Knuth, Két megjegyzés a minősítésről (forrás TeX ).
3. Louis Comtet , Elementary kombinatorikus elemzés , technikák Ingénieur, coll.  "Konkrét matematika",1997, 687  o. ( ISBN  978-2-84180-981-3 , online olvasás ) , p.  24..
4. A bemutatót lásd például Louis Comtet, Kombinatorikus elemzés , t.  2, PUF ,1970, P.  51.
5. Comtet 1970 , p.  38.
6. Lásd még ezt a javított gyakorlatot a Wikiverzióról .
7. Lásd például: Louis Comtet, Analyze Combinatoratique In-Depth , Techniques Ingénieur, coll.  "Konkrét matematika",2003( online olvasható ) , p.  3-4.
8. Comtet 2003 , p.  5.
9. vektortérnek K [ X ] a polinomok egyik variábilis egy kommutatív mezőt K , vagy akár szabad modul A [ X ] polinomok együtthatók egy kommutatív gyűrű A .
10. Abramowitz és Stegun , p.  825.

Lásd is

Bibliográfia

• (en) Milton Abramowitz és Irene Stegun , Matematikai függvények kézikönyve képletekkel, grafikonokkal és matematikai táblázatokkal [ kiadás részletei ] ( online ), „Stirling Numbers”, 24.1.3-4. §, p. 824-825
• (en) Louis Comtet , Haladó kombinatorika: A véges és végtelen bővítés művészete , D. Reidel ,1974, 343  p. ( ISBN  978-90-277-0441-2 , online olvasás )
• (en) Victor Adamchik, „  A Stirling-számokról és az Euler-összegekről  ” , Journal of Computational and Applied Mathematics  (en) , vol.  79,1997, P.  119–130 ( online olvasás )
• (en) Arthur T. Benjamin , Gregory O. Preston és Jennifer J. Quinn, „  Stirling Encounter with Harmonic Numbers  ” , Mathematics Magazine , vol.  75, n o  22002, P.  95–103 ( online olvasás )
• (en) JM Sixdeniers, KA Penson és AI Solomon, „  Extended Bell and Stirling Numbers From Hypergeometric Exponentiation  ” , Journal of Integer Sequences , vol.  4, n o  01.1.4,2001( online olvasás )
• (en) Hsien-Kuei Hwang , „  Asymptotic Expansions for the Stirling number of the first kind  ” , Journal of Combinatorial Theory , a, vol.  71, n o  21995, P.  343-351 ( DOI  10.1016 / 0097-3165 (95) 90010-1 , online olvasás )

Kapcsolódó cikkek

• Lehmer-kód
• Foata alapvető levelezése
• Ciklusok és rögzített pontok
• Euleri-szám
• Lah száma
• Harang polinom
• Érintett polinom
• Polinomiális szekvencia
• Stirling számok és exponenciális generáló függvények a szimbolikus kombinatorikában  ( fr )
• Transform Stirling  (en)

Külső linkek

• (en) Eric W. Weisstein , „  Az első fajta Stirling száma  ” , a MathWorld oldalon
• (en) E. Weisstein, „  Második Stirling száma  ” , a MathWorld- on
• (en) rmilson (146), "  Az első fajta Stirling számok  " , a PlanetMath oldalon
• (en) rmilson (146), "  Második Stirling számok  " , a PlanetMath oldalon

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