Stirling-getallen van de eerste soort

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

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, S1(n,k) met n ≥ 1 en 1 ≤ kn is het aantal permutaties van n elementen in k disjuncte cykels.

Men gebruikt ook de notatie s(n, k) of [n,k].

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 (x z y) een cykel; (z y x) en (y x z) zijn dezelfde cykel, maar (x y z), (y z x) of (z x y) 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 (-1)^{n-k}. S1(n,k). 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 S1(4,2) = 11.

Berekening[bewerken]

S1(n,k) kan berekend worden door middel van een recursieve vergelijking:

S1(n,k) = S1(n-1,k-1) + (n-1)S1(n-1,k)

met als beginwaarden:

S1(0,0) = 1 en S1(n,0) = S1(0,n) = 0 voor n > 0.

Tabel met waarden[bewerken]

De Stirlinggetallen van de eerste orde (zonder teken) 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,
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 n-de rij is gelijk aan de som van zijn linkerbovenbuur met n-1 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:

  • S1(n,1) = (n-1)!
  • S1(n,2) = (n-1)!H_{n-1}
hierbij is Hi het i-de harmonisch getal (de harmonische getallen zijn 1, 3/2, 11/6, 25/12, 137/60 enz.)

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

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 n elementen in k 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 s, dan is de inverse matrix daarvan gelijk aan S, de benedendriehoeksmatrix van de Stirling-getallen van de tweede soort:

s^{-1} = S\,

waarbij de elementen van de matrix S gegeven worden door

[S]_{nk}=S2(n,k)=\{n,k\}.

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

Externe links[bewerken]

Bronnen, noten en/of referenties
  1. rij A008275 in OEIS