Stirlingtal

Stirlingtal används inom matematiken för att beskriva antalet permutationer eller partitioner av storlek $m$ av en mängd av storlek $n$. Det finns två slags Stirlingtal, Stirlingtal av första slaget och Stirlingtal av andra slaget. Stirlingtalen är uppkallade efter matematikern James Stirling.

Notation

Stirlingtal av första slaget betecknas ibland $s(n,k)$ och Stirlingtal av andra slaget betecknas ibland $S(n,k)$. En annan notation är:

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

$S(n,k)=\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$

Denna notation med hak- och klammerparenteser, som är analog med notationen för binomialkoefficienter, infördes av Jovan Karamata.

Stirlingtal av första slaget

Stirlingtal av första slaget, $\left[{n \atop k}\right]$, är antalet sätt att ordna $n$ element i $k$ icke-tomma cykler, d.v.s. ordningar av tal som är cykliska permutationer av varandra. Om vi har mängden $A=\{1,2,3\}$ kan vi från den konstruera 2 olika cykler med 3 element i varje (vi betecknar en cykel med $[1,2,...,n]$):

$[1,2,3]~~[1,3,2]$

Så att $\left[{3 \atop 1}\right]=2$. Observera alltså att $[1,2,3]=[2,3,1]=[3,1,2]$, vi kan plocka en siffra framifrån och sätta längst bak.

Man ser att $\left[{0 \atop 0}\right]=1$, det finns ett sätt att placera inga element i noll icke-tomma cykler, i övrigt gäller att $\left[{n \atop 0}\right]=0$ ($n\neq 0$), för det finns inget sätt att placera ut $n$ element i noll icke-tomma cykler. För Stirlingtal av första slaget ser man att $\left[{n \atop n}\right]=1$, för det finns ett sätt att placera ut $n$ element i $n$ icke-tomma cykler (varje cykel innehåller då ett element).

Man kan räkna ut Stirlingtal av första slaget med följande rekursiva ekvation:

$\left[{n \atop k}\right]=(n-1)\left[{n-1 \atop k}\right]+\left[{n-1 \atop k-1}\right]$

Några exempel på Stirlingtal av första slaget:

n\k	0	1	2	3	4	5
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1

Stirlingtal av andra slaget

Stirlingtal av andra slaget, $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$, ger antal sätt att dela in en mängd med $n$ element i $k$ icke-tomma mängder.

Alternativt kan Stirlingtalet S(n,k) definieras som antalet oordnade surjektioner av en mängd av n element på en mängd av k element. Om det totala antalet surjektioner är N, så är S(n,k) = N/k!. S(n,k) kan även beskrivas som antalet möjligheter att placera n numrerade bollar i k identiska (onumrerade) lådor, med restriktionen minst en boll i varje låda.

Om vi t.ex. har en mängd med fyra element, exempelvis $A=\{1,2,3,4\}$ och vill veta på hur många sätt vi kan dela upp $A$ i två mängder, d.v.s. räkna ut $\left\{{\begin{matrix}4\\2\end{matrix}}\right\}$, ser vi att vi kan göra det på sju sätt:

$\{1,2,3\}\cup \{4\}~~\{1,2,4\}\cup \{3\}~~\{1,3,4\}\cup \{2\}~~\{2,3,4\}\cup \{1\}~~\{1,2\}\cup \{3,4\}~~\{1,3\}\cup \{2,4\}~~\{1,4\}\cup \{2,3\}$

d.v.s., $\left\{{\begin{matrix}4\\2\end{matrix}}\right\}=7$.

Stirlingtal av andra slaget på formen $\left\{{\begin{matrix}n\\1\end{matrix}}\right\}=1$ för positiva $n$, eftersom en mängd bara kan delas upp i en mängd med lika många element på ett sätt. Om $k=0$ kan vi säga att det bara finns ett sätt att dela in en tom mängd i noll icke-tomma mängder, så att $\left\{{\begin{matrix}0\\0\end{matrix}}\right\}=1$, men en icke-tom mängd kan inte delas upp i noll mängder på något sätt, så att $\left\{{\begin{matrix}n\\0\end{matrix}}\right\}=0$. Man inser också att det går att dela in en mängd med $n$ element i $n$ mängder på ett sätt, så att $\left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1$.

Stirlingtal av andra slaget kan räknas ut rekursivt med:

$\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=k\left\{{\begin{matrix}n-1\\k\end{matrix}}\right\}+\left\{{\begin{matrix}n-1\\k-1\end{matrix}}\right\}$

Några Stirlingtal av andra slaget är:

n\k	0	1	2	3	4	5
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1

Relationer med Stirlingtal

Man kan se att antalet möjliga cykler av en mängd är större än eller lika med antalet möjliga mängder, d.v.s.:

$\left[{n \atop k}\right]\geq \left\{{\begin{matrix}n\\k\end{matrix}}\right\}$

Det är ganska lätt att inse att:

$\left[{n \atop n}\right]=\left\{{\begin{matrix}n\\n\end{matrix}}\right\}$

Man kan också koppla ihop Stirlingtalen med binomialkoefficienter: När man ska ordna $n$ element i $n-1$ cykler eller delmängder får man exakt en cykel eller delmängd som innehåller två element, och då $[a,b]=[b,a]$ så är detta samma sak som att välja ut de två element som kommer hamna i samma delmängd eller cykel, så att:

$\left[{n \atop n-1}\right]=\left\{{\begin{matrix}n\\n-1\end{matrix}}\right\}={\begin{pmatrix}n\\2\end{pmatrix}}$

Stirlingtalen av första och andra slaget kan ses som varandras inverser:

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

och

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

där $\delta _{nk}$ är Kroneckerdeltat. Två andra liknande formler är

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

och

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