Stirling-szám

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

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

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:

${\displaystyle s(n,k)\,}$

Elsőfajú Stirling-számokra:

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

Másodfajú Stirling-számokra:

${\displaystyle 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.

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

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

${\displaystyle (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 ${\displaystyle x^{\underline {n}}}$ jelölést a csökkenő faktoriálisra és az ${\displaystyle x^{\overline {n}}}$ jelölést a növekvő faktoriálisra.^[1] Az ${\displaystyle s(n,k)}$ elsőfajú Stirling-szám ${\displaystyle 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:

${\displaystyle {\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:

${\displaystyle s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)}$

Definíció: Az ${\displaystyle 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: ${\displaystyle B_{n}=\sum _{k=0}^{n}S(n,k).}$

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

${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle 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:

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

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

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

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

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

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

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

és

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

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

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

${\displaystyle 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

${\displaystyle 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).}$

• 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

• Kombinatorika
• Numerikus sorok
• Permutáció