Stirling-getallen van de eerste soort

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

Definitie

Het Stirling-getal van de eerste soort, zonder teken, ${\displaystyle S1(n,k)}$ met ${\displaystyle n\geq 1}$ en ${\displaystyle 1\leq k\leq n,}$ is het aantal permutaties van ${\displaystyle n}$ elementen in ${\displaystyle k}$ disjuncte cykels.

Men gebruikt ook de notatie ${\displaystyle s(n,k)}$ en ${\displaystyle \textstyle \left[{n \atop k}\right].}$

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 ${\displaystyle (-1)^{n-k}S1(n,k).}$ Deze getallen zijn dus afwisselend positief en negatief.

Voorbeeld

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 ${\displaystyle S1(4,2)=11}$.

Berekening

${\displaystyle S1(n,k)}$ kan berekend worden door middel van een recursieve vergelijking:

${\displaystyle S1(n,k)=S1(n-1,k-1)+(n-1)S1(n-1,k)}$

met als beginwaarden:

${\displaystyle S1(0,0)=1}$ en

${\displaystyle S1(n,0)=S1(0,n)=0}$ voor ${\displaystyle n>0.}$

Tabel met waarden

De Stirlinggetallen van de eerste orde (zonder teken) kan men uitschrijven in een driehoekige tabel. Bij elke rij wordt ${\displaystyle n}$ verhoogd met 1, en in elke rij gaat ${\displaystyle k}$ van 1 tot ${\displaystyle 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 ${\displaystyle n}$-de rij is gelijk aan de som van zijn linkerbovenbuur met ${\displaystyle 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:

• ${\displaystyle S1(n,1)=(n-1)!}$
• ${\displaystyle S1(n,2)=(n-1)!H_{n-1}}$

hierbij is ${\displaystyle H_{i}}$ het ${\displaystyle i}$-de harmonisch getal (de harmonische getallen zijn 1, 3/2, 11/6, 25/12, 137/60 enz.)

• ${\displaystyle S1(n,n-1)={n \choose 2}}$ is het ${\displaystyle (n-1)}$-ste driehoeksgetal.

Als men deze driehoek vormt met de Stirling-getallen van de eerste soort mét teken, is de som van de ${\displaystyle n}$-de rij steeds nul (voor ${\displaystyle 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

Stirling-getallen van de tweede soort tellen het aantal mogelijke partities van een verzameling met ${\displaystyle n}$ elementen in ${\displaystyle 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 ${\displaystyle s,}$ dan is de inverse matrix daarvan gelijk aan ${\displaystyle S,}$ de benedendriehoeksmatrix van de Stirling-getallen van de tweede soort:

${\displaystyle s^{-1}=S}$

waarbij de elementen van de matrix ${\displaystyle S}$ gegeven worden door

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

De matrices ${\displaystyle s}$ en ${\displaystyle S}$ zijn oneindig, maar deze vergelijking gaat ook op voor eindige matrices die beperkt zijn tot de eerste ${\displaystyle N}$ rijen.

Externe links

• Wolfram Mathworld: Stirling Number of the First Kind