Stirlingszámok

Stirlingszámok, vagy más néven Stirling-számok, a kombinatorikában előforduló két típusú számot jelölnek, amelyeket James Stirling tiszteletére neveztek el. Ezek a számok az objektumok csoportosításával és elrendezésével kapcsolatos problémákban jelennek meg.

Az első típusú Stirlingszámok, jelölésük S(n, k) vagy a mellékjelöléssel $\begin{bmatrix} n \\ k \end{bmatrix}$, azt a számot adják meg, ahányféleképpen n darab különböző elemet k darab nem üres, megkülönböztethetetlen halmazba lehet particionálni. Például, ha n=3, és az elemek {1, 2, 3}, akkor a lehetséges particionálások k=2 esetén a következők: {{1, 2}, {3}}, {{1, 3}, {2}}, {{2, 3}, {1}}. Tehát S(3, 2) = 3.

A második típusú Stirlingszámok, jelölésük s(n, k) vagy a mellékjelöléssel $\begin{Bmatrix} n \\ k \end{Bmatrix}$, azt a számot adják meg, ahányféleképpen n darab különböző elemet k darab megkülönböztethető, nem üres sorba lehet rendezni. Ez ekvivalens azzal is, hogy n elemet k darab megkülönböztethető, nem üres, jól rendezett "kosárba" helyezünk. A sorrend a kosarakon belül is számít. Például, ha n=3 és k=2, az első típusú Stirlingszámokkal ellentétben itt a sorrend és a megkülönböztethetőség is számít.

A Stirlingszámoknak rekurziós relációik vannak, amelyek lehetővé teszik kiszámításukat. Az első típusú Stirlingszámokra: $\begin{bmatrix} n \\ k \end{bmatrix} = k \begin{bmatrix} n-1 \\ k \end{bmatrix} + \begin{bmatrix} n-1 \\ k-1 \end{bmatrix}$, míg a második típusúra: $\begin{Bmatrix} n \\ k \end{Bmatrix} = k \begin{Bmatrix} n-1 \\ k \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}$. Az alapfeltételek, mint például $\begin{bmatrix} n \\ 0 \end{bmatrix} = 0$ (n>0 esetén) és $\begin{bmatrix} n \\ n \end{bmatrix} = 1$, segítik a rekurzió megindítását. Ezek a számok fontos szerepet játszanak a kombinatorikán kívül az analízisben és a valószínűségszámításban is.