Stirling-getallen van de tweede soort

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Jump to search

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, met en is het aantal mogelijkheden om een verzameling met elementen te schrijven als een disjuncte vereniging van niet-lege deelverzamelingen. Anders gezegd: het is het aantal mogelijke partities van een verzameling met elementen in niet-lege verzamelingen, of: het aantal manieren waarop men de elementen van de verzameling kan verdelen over niet-lege groepen. De volgorde van die groepen is niet van belang.

Men gebruikt ook de notaties en in plaats van

Voorbeeld[bewerken]

Een verzameling van vier elementen, zeg 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 .

Als de vier elementen van 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 .

Berekening[bewerken]

De expliciete formule voor de berekening van deze getallen is:

kan ook berekend worden door middel van een recursieve vergelijking:

met de beginwaarden:

(als er evenveel groepen als elementen zijn) en
(als er maar één groep is)

Tabel met waarden[bewerken]

De Stirling-getallen van de tweede soort kan men uitschrijven in een driehoekige tabel. Bij elke rij wordt met 1 verhogd en in elke rij gaat van 1 tot [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,
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 -de getal in een rij is gelijk aan de som van zijn linkerbovenbuur en maal zijn bovenbuur. Bijvoorbeeld het vierde getal in de zevende rij,

Enkele eigenschappen[bewerken]

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

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

  • Het voorlaatste getal in elke rij, , is het -de driehoeksgetal.
  • Het tweede getal in elke rij, , is gelijk aan .
  • Er geldt ook de volgende betrekking:
.

Stirling-getallen van de tweede soort worden al gauw astronomisch groot bij toenemende en [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]