Brontekst bekijken van Stirling-getallen van de tweede soort

'''Stirling-getallen van de tweede soort''', genoemd naar de Schotse wiskundige [[James Stirling (wiskundige)|James Stirling]], komen voor in de [[combinatoriek]] en de studie van [[partitie (verzamelingenleer)|partities]].

==Definitie==
Het Stirling-getal van de tweede soort, <math>S2(n,k)</math> met <math>n\ge 1</math> en <math>1\le k \le n,</math> is het aantal mogelijkheden om een [[verzameling (wiskunde)|verzameling]] met <math>n</math> elementen te schrijven als een [[disjuncte verzamelingen|disjuncte]] [[vereniging (verzamelingenleer)|vereniging]] van <math>k</math> niet-lege [[deelverzameling]]en. Anders gezegd: het is het aantal mogelijke partities van een verzameling met <math>n</math> elementen in <math>k</math> niet-lege verzamelingen, of: het aantal manieren waarop men de <math>n</math> elementen van de verzameling kan verdelen over <math>k</math> niet-lege groepen. De volgorde van die groepen is niet van belang.

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

==Voorbeeld==
Een verzameling van vier elementen, zeg <math>A=\{1,2,3,4\}</math> kan op zes verschillende manieren over drie (niet-lege) groepen verdeeld worden. [[Permutatie]]s 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 <math>S2(4,3)=6</math>.

Als de vier elementen van <math>A</math> 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 <math>S2(4,2)=7</math>.

==Berekening==
De expliciete formule voor de berekening van deze getallen is:

:<math>S2(n,k) = \frac{1}{k!}\sum_{j=0}^k(-1)^j{k \choose j} (k-j)^n.</math>

<math>S2(n,k)</math> kan ook berekend worden door middel van een [[recursie]]ve vergelijking:

:<math>S2(n,k) = k.\cdot S2(n-1,k) + S2(n-1, k-1),</math>

met de beginwaarden:

:<math>S2(n,n) = 1 </math> (als er evenveel groepen als elementen zijn) en
:<math>S2(n,1) = 1 </math> (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 <math>n</math> met 1 verhogd en in elke rij gaat <math>k</math> van 1 tot <math>n</math><ref>{{Link OEIS|id=A008277}}</ref>:
:{| style="text-align:right;"
| 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 <math>k</math>-de getal in een rij is gelijk aan de som van zijn linkerbovenbuur en <math>k</math> maal zijn bovenbuur. Bijvoorbeeld het vierde getal in de zevende rij, <math>S2(7,4)=90+4\times 65.</math>

===Enkele eigenschappen===
* De som van een rij in deze driehoek is het <math>n</math>-de [[getal van Bell]]:

:<math>B_n=\sum_{k=1}^n S2(n,k)</math>,

dat is het totaal aantal mogelijke partities van een verzameling met <math>n</math> elementen.

* Het voorlaatste getal in elke rij, <math>S2(n,n-1)</math>, is het <math>n</math>-de [[driehoeksgetal]].
* Het tweede getal in elke rij, <math>S2(n,2)</math>, is gelijk aan <math>2^{n-1}-1</math>.
* Er geldt ook de volgende betrekking:
::<math>S2(n,k) = \sum_{m=k}^n k^{n-m}\cdot S2(m-1,k-1) </math>.

Stirling-getallen van de tweede soort worden al gauw astronomisch groot bij toenemende <math>n</math> en <math>k.</math><ref>[http://oeis.org/A008277/b008277.txt Zie hier voor de eerste honderd rijen van de driehoek]</ref>.

==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 [[driehoeksmatrix|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 [[cykel]]s in plaats van verzamelingen).

==Externe link==
* [http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html Wolfram Mathworld: Stirling Number of the Second Kind]

{{Appendix}}

[[Categorie:Combinatoriek]]
[[Categorie:Discrete wiskunde]]