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[\genfrac{}{}{0ex}{}{n}{k}\right]=|s(n,k)|$

Másodfajú Stirling-számokra:

$S(n,k)=\left\{\genfrac{}{}{0ex}{}{n}{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^{\underset{\_}{n}}$ jelölést a csökkenő faktoriálisra és az $x^{\bar{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ó: $\left\{\begin{array}{c}n+1\\ k\end{array}\right\}=k\left\{\begin{array}{c}n\\ k\end{array}\right\}+\left\{\begin{array}{c}n\\ k-1\end{array}\right\}$ 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 $\left\{\begin{array}{c}n\\ k-1\end{array}\right\}$ 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\left\{\begin{array}{c}n\\ k\end{array}\right\}$ 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: $\left\{\begin{array}{c}n\\ k\end{array}\right\}=\frac{1}{k!}\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})(k-i{)}^n$ Bizonyítás: Legyen $A=\left\{\begin{array}{c}1,2,..,n\end{array}\right\}$ , $B=\left\{\begin{array}{c}1,2,..,k\end{array}\right\}$ és legyen $f:A\to B$ egy szürjektív függvény, illetve $n\ge 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\to B$ függvények száma $s_{n,k}=\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})(k-i{)}^n$. A másodfajú Stirling-számok és a csökkenő faktoriális kapcsolata: $x^n=\sum _{k=0}^n\left\{\begin{array}{c}n\\ k\end{array}\right\}(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=\left\{\begin{array}{c}1,2,...,n\end{array}\right\}$ és $B=\left\{\begin{array}{c}1,2,...,x\end{array}\right\}$, illetve $x\ge n$, ekkor összesen $x^n$ darab $f:A\to B$ függvény létezik. Legyen $f$ képhalmaza $f(A)$, ekkor $f:A\to f(A)$ függvény szürjektív. $f(A)$ halmazra fennáll, hogy $1\le |f(A)|\le n$. Ha $f(A)=\left\{\begin{array}{c}{x}_1,x_2,...,x_k\end{array}\right\}$, ahol $x_1,x_2,...,x_k\in B$, ( $x_1<x_2<...<x_k$), akkor $k!\left\{\begin{array}{c}n\\ k\end{array}\right\}$ ilyen $f:A\to f(A)$ függvény van, ezt a k elemet $B$-ből $(\genfrac{}{}{0ex}{}{x}{k})$ féleképpen választhatjuk ki, vagyis összesen $\left\{\begin{array}{c}n\\ k\end{array}\right\}k!(\genfrac{}{}{0ex}{}{x}{k})=\left\{\begin{array}{c}n\\ k\end{array}\right\}(x{)}_k$ darab $f:A\to f(A)$ függvény van, melyre $|f(A)|=k$. Mivel $1\le |f(A)|\le n$, ezért $\sum _{k=1}^n\left\{\begin{array}{c}n\\ k\end{array}\right\}(x{)}_k$ darab $f:A\to B$ függvény létezik. Az egyenlőség két oldalán n-edfokú polinom áll és a tételt minden $x\ge 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)=(\genfrac{}{}{0ex}{}{n-1}{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(\genfrac{}{}{0ex}{}{n-1+j}{n-k+j})(\genfrac{}{}{0ex}{}{2n-k}{n-k-j})S(n-k+j,j)$

és

$S(n,k)=\sum _{j=0}^{n-k}(-1{)}^j(\genfrac{}{}{0ex}{}{n-1+j}{n-k+j})(\genfrac{}{}{0ex}{}{2n-k}{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ó