Stirling-getallen van de eerste soort

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

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

Definitie[bewerken]

Het Stirling-getal van de eerste soort, zonder teken, met en is het aantal permutaties van elementen in disjuncte cykels.

Men gebruikt ook de notatie en

Cyclus van X,Y,Z

Een cykel verschilt van een verzameling doordat de volgorde van de elementen erin wel van belang is (waarbij men zich moet voorstellen dat de elementen in een kring zijn geplaatst). In de figuur hiernaast is (XZY) een cykel; (ZYX) en (YXZ) zijn dezelfde cykel, maar (XYZ, (YZX) en (ZXY) vormen een andere cykel. Drie elementen kunnen dus op twee manieren een cykel vormen; twee elementen of één element slechts op 1 manier.

Het Stirling-getal van de eerste orde, mét teken, is gelijk aan Deze getallen zijn dus afwisselend positief en negatief.

Voorbeeld[bewerken]

De verzameling met vier elementen {1,2,3,4} kan op de volgende manieren in twee disjuncte cykels verdeeld worden:

(1) – (2 3 4)
(1) – (2 4 3)
(2) – (1 3 4)
(2) – (1 4 3)
(3) – (1 2 4)
(3) – (1 4 2)
(4) – (1 2 3)
(4) – (1 3 2)
(1 2) – (3 4)
(1 3) – (2 4)
(1 4) – (2 3)

Dus .

Berekening[bewerken]

kan berekend worden door middel van een recursieve vergelijking:

met als beginwaarden:

en
voor

Tabel met waarden[bewerken]

De Stirlinggetallen van de eerste orde (zonder teken) kan men uitschrijven in een driehoekige tabel. Bij elke rij wordt verhoogd met 1, en in elke rij gaat van 1 tot [1]:

1,
1, 1,
2, 3, 1,
6, 11, 6, 1,
24, 50, 35, 10, 1,
120, 274, 225, 85, 15, 1,
720, 1764, 1624, 735, 175, 21, 1,
5040, 13068, 13132, 6769, 1960, 322, 28, 1,
40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1,

...

Men bouwt deze driehoek op door de recursieve vergelijking toe te passen als volgt: de eerste rij bestaat enkel uit een 1. Een getal in de -de rij is gelijk aan de som van zijn linkerbovenbuur met maal zijn bovenbuur. Voor het eerste getal in elke rij neemt men 0 aan als linkerbovenbuur en voor het laatste getal 0 als bovenbuur.

Met deze driehoek kan men onder meer de volgende eigenschappen nagaan:

hierbij is het -de harmonisch getal (de harmonische getallen zijn 1, 3/2, 11/6, 25/12, 137/60 enz.)
  • is het -ste driehoeksgetal.

Als men deze driehoek vormt met de Stirling-getallen van de eerste soort mét teken, is de som van de -de rij steeds nul (voor ):

1,
-1, 1,
2, -3, 1,
-6, 11, - 6, 1,
24, -50, 35, -10, 1,
-120, 274, -225, 85, - 15, 1,

...

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

Stirling-getallen van de tweede soort tellen het aantal mogelijke partities van een verzameling met elementen in niet-lege deelverzamelingen. Hierbij is de volgorde van de elementen niet van belang. Als men het bovenstaande voorbeeld schrijft met verzamelingen in plaats van in cykelnotatie moet men een van de twee partities {1} – {2,3,4} en {1} – {2,4,3} laten wegvallen omdat deze identiek zijn.

Men kan Stirling-getallen van de eerste en de tweede soort beschouwen als inversen van elkaar. Als men de driehoek met Stirling-getallen van de eerste soort (mét teken) beschouwt als een benedendriehoeksmatrix dan is de inverse matrix daarvan gelijk aan de benedendriehoeksmatrix van de Stirling-getallen van de tweede soort:

waarbij de elementen van de matrix gegeven worden door

De matrices en zijn oneindig, maar deze vergelijking gaat ook op voor eindige matrices die beperkt zijn tot de eerste rijen.

Externe links[bewerken]