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

Definíció: 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).$

A másodfajú Stirling-számokra vonatkozó rekurzió:

${\begin{Bmatrix}n+1\\k\end{Bmatrix}}=k{\begin{Bmatrix}n\\k\end{Bmatrix}}+{\begin{Bmatrix}n\\k-1\end{Bmatrix}}$

Bizonyítás: A definíció szerint ez az (n+1) elemű halmaz az összes k-részre való partícióinak (osztályfelbontásának) számát jelenti. Egy ilyen partíciónak a halmaz (n+1)-edik elemét tartalmazó blokkja (halmaza) vagy egyelemű, vagy egynél több elemű. Ha ez a blokk egyelemű, akkor összesen ${\begin{Bmatrix}n\\k-1\end{Bmatrix}}$ ilyen eset van (a maradék n elemet a maradék (k-1) részhalmazra kell partícionálnunk, majd a partícióhoz hozzávesszük az (n+1)-edik elemet tartalmazó egyelemű halmazt). Ha a blokk egynél több elemű, akkor összesen $k{\begin{Bmatrix}n\\k\end{Bmatrix}}$ ilyen eset van (a maradék n elemet k részhalmazra kell partícionálnunk, majd az egyik részhalmazhoz hozzávesszük az (n+1)-edik elemet, ezt k féleképpen tehetjük meg).

Másodfajú Stirling-számok képlete:

${\begin{Bmatrix}n\\k\end{Bmatrix}}={\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{i}{\binom {k}{i}}(k-i)^{n}$

Bizonyítás: Legyen $A={\begin{Bmatrix}1,2,..,n\end{Bmatrix}}$ , $B={\begin{Bmatrix}1,2,..,k\end{Bmatrix}}$ és legyen $f:A\rightarrow B$ egy szürjektív függvény, illetve $n\geq k$, ekkor $f^{-1}(1)\cup f^{-1}(2)\cup ...\cup f^{-1}(k)$ az $A$ halmaz egy k osztályú partíciója. Ha összesen $s_{n,k}$ ilyen $f$ függvény van, akkor ${\frac {1}{k!}}s_{n,k}$ k osztályú partíciója van az $A$ halmaznak, mivel $f^{-1}(1),f^{-1}(2),...,f^{-1}(k)$ halmazokat permutálva a partíció ugyanaz marad, de $f$ megváltozik. A Szitaformula alapján megmutatható, hogy a szürjektív $f:A\rightarrow B$ függvények száma ${\displaystyle s_{n,k}}=\sum _{i=0}^{k}(-1)^{i}{\binom {k}{i}}(k-i)^{n}$.

A másodfajú Stirling-számok és a csökkenő faktoriális kapcsolata:

$x^{n}=\sum _{k=0}^{n}{\begin{Bmatrix}n\\k\end{Bmatrix}}(x)_{k}$

ahol $(x)_{k}$ (Pochhammer-szimbólum) a csökkenő faktoriálist jelöli: $(x)_{k}=x(x-1)(x-2)\cdots (x-k+1).$

Bizonyítás: Legyen $A={\begin{Bmatrix}1,2,...,n\end{Bmatrix}}$ és $B={\begin{Bmatrix}1,2,...,x\end{Bmatrix}}$, illetve $x\geq n$, ekkor összesen $x^{n}$ darab $f:A\rightarrow B$ függvény létezik. Legyen $f$ képhalmaza $f(A)$, ekkor $f:A\rightarrow f(A)$ függvény szürjektív. $f(A)$ halmazra fennáll, hogy $1\leq |f(A)|\leq n$. Ha $f(A)={\begin{Bmatrix}x_{1},x_{2},...,x_{k}\end{Bmatrix}}$, ahol $x_{1},x_{2},...,x_{k}\in B$, ( $x_{1}<x_{2}<...<x_{k}$), akkor $k!{\begin{Bmatrix}n\\k\end{Bmatrix}}$ ilyen $f:A\rightarrow f(A)$ függvény van, ezt a k elemet $B$-ből ${\binom {x}{k}}$ féleképpen választhatjuk ki, vagyis összesen ${\begin{Bmatrix}n\\k\end{Bmatrix}}k!{\binom {x}{k}}={\begin{Bmatrix}n\\k\end{Bmatrix}}(x)_{k}$ darab $f:A\rightarrow f(A)$ függvény van, melyre $|f(A)|=k$. Mivel $1\leq |f(A)|\leq n$, ezért $\sum _{k=1}^{n}{\begin{Bmatrix}n\\k\end{Bmatrix}}(x)_{k}$ darab $f:A\rightarrow B$ függvény létezik. Az egyenlőség két oldalán n-edfokú polinom áll és a tételt minden $x\geq n$ természetes számra bizonyítottuk, ezért a tétel minden valós x-re igaz.

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).$

Források

• Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Konkrét matematika, Műszaki Könyvkiadó, Budapest, 1998
• 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

Kapcsolódó szócikkek

• Kombinatorika
• Numerikus sorok
• Permutáció