Stirling-getallen van de tweede soort

Stirling-getallen van de tweede soort, genoemd naar de Schotse wiskundige James Stirling, komen voor in de combinatoriek en de studie van partities.

Definitie

Het Stirling-getal van de tweede soort, $S2(n,k)$ met $n\geq 1$ en $1\leq k\leq n,$ is het aantal mogelijkheden om een verzameling met $n$ elementen te schrijven als een disjuncte vereniging van $k$ niet-lege deelverzamelingen. Anders gezegd: het is het aantal mogelijke partities van een verzameling met $n$ elementen in $k$ niet-lege verzamelingen, of: het aantal manieren waarop men de $n$ elementen van de verzameling kan verdelen over $k$ niet-lege groepen. De volgorde van die groepen is niet van belang.

Men gebruikt ook de notaties $S(n,k)$ en $\lbrace \textstyle {n \atop k}\rbrace$ in plaats van $S2(n,k).$

Voorbeeld

Een verzameling van vier elementen, zeg $A=\{1,2,3,4\}$ kan op zes verschillende manieren over drie (niet-lege) groepen verdeeld worden. Permutaties van deze verdelingen tellen niet mee, omdat de volgorde niet van belang is. De mogelijkheden zijn:

{1} - {2} – {3,4}

{1} – {3} – {2,4}

{1} – {4} – {2,3}

{1,2} – {3} – {4}

{1,3} – {2} – {4}

{1,4} – {2} – {3}

Dus $S2(4,3)=6$.

Als de vier elementen van $A$ over twee groepen verdeeld moeten worden, zijn dit de mogelijkheden:

{1} – {2,3,4}

{1,2} – {3,4}

{1,3} – {2,4}

{1,4} – {2,3}

{1,2,3} – {4}

{1,2,4} – {3}

{1,3,4} – {2}

Dus $S2(4,2)=7$.

Berekening

De expliciete formule voor de berekening van deze getallen is:

$S2(n,k)={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{j}{k \choose j}(k-j)^{n}.$

$S2(n,k)$ kan ook berekend worden door middel van een recursieve vergelijking:

$S2(n,k)=k.\cdot S2(n-1,k)+S2(n-1,k-1),$

met de beginwaarden:

$S2(n,n)=1$ (als er evenveel groepen als elementen zijn) en

$S2(n,1)=1$ (als er maar één groep is)

Tabel met waarden

De Stirling-getallen van de tweede soort kan men uitschrijven in een driehoekige tabel. Bij elke rij wordt $n$ met 1 verhoogd en in elke rij gaat $k$ van 1 tot $n$:

1,
1,	1,
1,	3,	1,
1,	7,	6,	1,
1,	15,	25,	10,	1,
1,	31,	90,	65,	15,	1,
1,	63,	301,	350,	140,	21,	1,
1,	127,	966,	1701,	1050,	266,	28,	1,
1,	255,	3025,	7770,	6951,	2646,	462,	36,	1,
1,	511,	9330,	34105,	42525,	22827,	5880,	750,	45,	1,
	enz.

Deze driehoek bouwt men op door de recursieve vergelijking toe te passen. Dit betekent dat het eerste en het laatste getal in elke rij gelijk is aan 1, en voor de andere getallen geldt: het $k$-de getal in een rij is gelijk aan de som van zijn linkerbovenbuur en $k$ maal zijn bovenbuur. Bijvoorbeeld het vierde getal in de zevende rij, $S2(7,4)=90+4\times 65.$

Enkele eigenschappen

• De som van een rij in deze driehoek is het $n$-de getal van Bell:

$B_{n}=\sum _{k=1}^{n}S2(n,k)$,

dat is het totaal aantal mogelijke partities van een verzameling met $n$ elementen.

• Het voorlaatste getal in elke rij, $S2(n,n-1)$, is het $n$-de driehoeksgetal.
• Het tweede getal in elke rij, $S2(n,2)$, is gelijk aan $2^{n-1}-1$.
• Er geldt ook de volgende betrekking:

$S2(n,k)=\sum _{m=k}^{n}k^{n-m}\cdot S2(m-1,k-1)$.

Stirling-getallen van de tweede soort worden al gauw astronomisch groot bij toenemende $n$ en $k.$.

Verband met Stirling-getallen van de eerste soort

Stirling-getallen van de eerste soort zijn te beschouwen als de inverse van de Stirling-getallen van de tweede soort. Bouwt men een benedendriehoeksmatrix met de driehoek van de Stirling-getallen van de tweede soort, dan is de inverse matrix daarvan gelijk aan de benedendriehoeksmatrix met de Stirling-getallen van de eerste soort.

Een Stirling-getal van de eerste soort verschilt van een Stirling-getal van de tweede soort daarin, dat voor het laatste de volgorde van de elementen in de deelverzamelingen niet van belang is, terwijl dat voor het eerste wel van belang is (het gaat daar om cykels in plaats van verzamelingen).

Externe link

• Wolfram Mathworld: Stirling Number of the Second Kind

Bronnen, noten en/of referenties