Stirling-getallen van de tweede soort

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

Definitie[bewerken]

Het Stirling-getal van de tweede soort, S2(n, k) met n ≥ 1 en 1 ≤ kn 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) of {n,k} in plaats van S2(n,k).

Voorbeeld[bewerken]

Gegeven de verzameling van vier elementen A = {1,2,3,4}. Er zijn zes verschillende manieren waarop de vier elementen over drie groepen kunnen verdeeld worden (permutaties van deze verdelingen tellen niet mee omdat de volgorde niet van belang is):

{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} en {1,3,4} – {2}. Dus S2(4,2) = 7.

Berekening[bewerken]

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. S2(n-1,k) + S2(n-1, k-1)

Als beginwaarden hebben we:

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[bewerken]

De Stirling-getallen van de tweede orde kan men uitschrijven in een driehoekige tabel. Bij elke rij verhoogt n met 1 en in elke rij gaat k van 1 tot n [1]:

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,

...

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) is gelijk aan 90 + 4 x 65.

Enkele eigenschappen[bewerken]

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}.S2(m-1,k-1) .

Stirling-getallen van de tweede soort worden algauw astronomisch hoog als n en k groter worden[2].

Verband met Stirling-getallen van de eerste soort[bewerken]

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[bewerken]

Bronnen, noten en/of referenties