Stirlingtal

Stirlingtal används inom matematiken för att beskriva antalet permutationer eller partitioner av storlek ${\displaystyle m}$ av en mängd av storlek ${\displaystyle 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 ${\displaystyle s(n,k)}$ och Stirlingtal av andra slaget betecknas ibland ${\displaystyle S(n,k)}$. En annan notation är:

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

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

${\displaystyle [1,2,3]~~[1,3,2]}$

Så att ${\displaystyle \left[{3 \atop 1}\right]=2}$. Observera alltså att ${\displaystyle [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 ${\displaystyle \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 ${\displaystyle \left[{n \atop 0}\right]=0}$ (${\displaystyle n\neq 0}$), för det finns inget sätt att placera ut ${\displaystyle n}$ element i noll icke-tomma cykler. För Stirlingtal av första slaget ser man att ${\displaystyle \left[{n \atop n}\right]=1}$, för det finns ett sätt att placera ut ${\displaystyle n}$ element i ${\displaystyle 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:

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

Stirlingtal av andra slaget

Stirlingtal av andra slaget, ${\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}}$, ger antal sätt att dela in en mängd med ${\displaystyle n}$ element i ${\displaystyle 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 ${\displaystyle A=\{1,2,3,4\}}$ och vill veta på hur många sätt vi kan dela upp ${\displaystyle A}$ i två mängder, d.v.s. räkna ut ${\displaystyle \left\{{\begin{matrix}4\\2\end{matrix}}\right\}}$, ser vi att vi kan göra det på sju sätt:

${\displaystyle \{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., ${\displaystyle \left\{{\begin{matrix}4\\2\end{matrix}}\right\}=7}$.

Stirlingtal av andra slaget på formen ${\displaystyle \left\{{\begin{matrix}n\\1\end{matrix}}\right\}=1}$ för positiva ${\displaystyle n}$, eftersom en mängd bara kan delas upp i en mängd med lika många element på ett sätt. Om ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \left\{{\begin{matrix}n\\0\end{matrix}}\right\}=0}$. Man inser också att det går att dela in en mängd med ${\displaystyle n}$ element i ${\displaystyle n}$ mängder på ett sätt, så att ${\displaystyle \left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1}$.

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

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

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.:

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

Det är ganska lätt att inse att:

${\displaystyle \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 ${\displaystyle n}$ element i ${\displaystyle n-1}$ cykler eller delmängder får man exakt en cykel eller delmängd som innehåller två element, och då ${\displaystyle [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:

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

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

och

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

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

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

och

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