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 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 verhoogd 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