Stirling-szám

A matematikában a Stirling-számok számos területen fordulnak elő analízisbeli és kombinatorikai problémáknál. A James Stirling (1692–1770) skót matematikusról elnevezett Stirling-számoknak két fajtája különböztethető meg:

• Elsőfajú Stirling-számok
• Másodfajú Stirling-számok

Jelölés

A Stirling-számokra többféle jelölés is használatos. Az elsőfajú Stirling-számokat kis s, a másodfajú Stirling-számokat nagy S betű jelöli. Az elsőfajú Stirling-számok negatívak is lehetnek, a másodfajú Stirling-számok csak pozitív számok lehetnek. Az általános jelölés:

$s(n,k)\,$

Elsőfajú Stirling-számokra:

$c(n,k)=\left[{n \atop k}\right]=|s(n,k)|\,$

Másodfajú Stirling-számokra:

$S(n,k)=\left\{{n \atop k}\right\}\,$

Milton Abramowitz és Irene Stegun nagybetűket és gót betűket használ, Jovan Karamata 1935-ben vezette be a szögletes és kapcsos zárójeles jelölést.

Elsőfajú Stirling-számok

A következő képletben a Stirling-szám az együttható $(x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k}.$

ahol $(x)_{n}$ (a Pochhammer-szimbólum) a csökkenő faktoriálist jelöli,

$(x)_{n}=x(x-1)(x-2)\cdots (x-n+1).$

Megjegyzés: (x)₀ = 1, mert ez egy üres szorzat. A kombinatorikában gyakran használják az $x^{\underline {n}}$ jelölést a csökkenő faktoriálisra és az $x^{\overline {n}}$ jelölést a növekvő faktoriálisra. Az $s(n,k)$ elsőfajú Stirling-szám $c(n,k)$ abszolút értéke n elem permutációinak számát adja k diszjunkt ciklus esetén. Az alábbi táblázat az első néhány elsőfajú Stirling-számot mutatja:

${\begin{array}{ccccccccccc}&&&&&~~1~~&&&&&\\&&&&-1&&~~1~~&&&&\\&&&2&&-3&&~~1~~&&&\\&&-6&&11&&-6&&~~1~~&&\\&24&&-50&&35&&-10&&~~1~~&\\-120&&274&&-225&&85&&-15&&~~1~~\\\end{array}}$

ahol:

$s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)$

Másodfajú Stirling-számok

Az $S(n,k)$ másodfajú Stirling-szám egy n elemű halmaz k osztályú osztályozásainak a száma. Rögzített n mellett az összegük az n-edik Bell-szám: $B_{n}=\sum _{k=0}^{n}S(n,k).$

Lah-számok

Az $L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}$ Lah-számokat néha harmadfajú Stirling-számnak is hívják.

Fordítottsági kapcsolat

Az első- és másodfajú Stirling-számok tekinthetők úgy is, mint egymás inverzei:

$\sum _{j=0}^{n}s(n,j)S(j,k)=\delta _{nk}$

és

$\sum _{j=0}^{n}S(n,j)s(j,k)=\delta _{nk},$

ahol $\delta _{nk}$ a Kronecker delta függvény.

Szimmetrikusság

Abramowitz és Stegun megad egy szimmetrikus összefüggést az első- és másodfajú Strirling-számokra:

$s(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}S(n-k+j,j)$

és

$S(n,k)=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}s(n-k+j,j).$

További információk

• Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Konkrét matematika, Műszaki Könyvkiadó, Budapest, 1998

Kapcsolódó szócikkek

• Kombinatorika
• Numerikus sorok
• Permutáció
• Hsien-Kuei Hwang (1995). "Asymptotic Expansions for the Stirling Numbers of the First Kind". Journal of Combinatorial Theory, Series A 71 (2): 343–351. doi:10.1016/0097-3165(95)90010-1