Stirling getallen

© h.hofstede (h.hofstede@hogeland.nl)

Stirling getallen
-van de eerste soort-

Deze les is een intermezzo-lesje waarin de Stirling-getallen van de eerste soort worden besproken (er zijn ook Stirling getallen van de tweede soort, die staan in deze les)
We bekijken het aantal manieren waarop een verzameling van n elementen verdeeld kan worden in k cykels. Dat aantal noemen we het Stirling-getal Sⁿ_k

Laten we er maar een paar uitproberen, naar opklimmende n.

n = 1

een verzameling met maar één element kan maar op 1 manier op zichzelf worden afgebeeld, dus S¹₁ = 1

n = 2

nu zijn er twee mogelijkheden, namelijk (1)(2) met twee cykels, en (1, 2) met één cykel
dus S²₁ = 1 en S²₂ = 1

n = 3

nou wordt het al wat moeilijker.
met één cykel zijn er twee mogelijkheden: (123) en (132) dus S³₁ = 2
met twee cykels zijn de mogelijkheden (1)(23) en (2)(13) en (3)(12) dus S³₂ = 3
met drie cykels is er uiteraard maar één mogelijkheid; S³₃ = 1

Voor hogere n zullen we weer gaan proberen een recursierelatie op te stellen. Voordat we dat doen kunnen we al wel een paar algemene opmerkingen maken.

• als k = n moet elk element een cykle op zichzelf zijn, dus Sⁿ_n = 1
• als k = 1 moet er één cykel van alle elementen zijn. Die staan dus allemaal in één cirkel. De eerste is willekeurig maar de anderen kun je dan op (n - 1)! manieren kiezen. Sⁿ_{1 =}(n - 1)!
• als je voor één bepaalde alle Sⁿ_k bij elkaar opteltdan krijg je alle mogelijk permutaties, en dat zijn er n!

Hier is een tabel met een aantal Sⁿ_kwaarden

S^k_n		k
S^k_n		1	2	3	4	5	6	7	8
n	1	1	0	0	0	0	0	0	0
	2	1	1	0	0	0	0	0	0
	3	2	3	1	0	0	0	0	0
	4	6	11	6	1	0	0	0	0
	5	24	50	35	10	1	0	0	0
	6	120	274	225	85	15	1	0	0
	7	720	1764	1624	735	175	21	1	0
	8	5040	13068	13132	6769	1960	322	28	1

Een recursieformule.

Stel je stapt een kamer binnen met daarin n mensen die al in allerlei cykels hebben plaatsgenomen. Dan kun jij je daaraan toevoegen op twee verschillende manieren:

•

Je bent asociaal en vormt in je eentje een nieuwe cykel van lengte 1. Als er dan k cykels in totaal moeten zijn, dan moeten die andere mensen k - 1 cykels vormen en dat kan op Sⁿ_k_-1 manieren

•

Je sluit je aan bij een bestaande cykel. Dat betekent dat er al k cykels moeten zijn en dat kan op Sⁿ_kmanieren. Op hoeveel manieren kun jij plaatsnemen in een bestaande cykel? Nou, dan moet jij tussen twee mensen in gaan staan. Dus er zijn evenveel manieren om dat te doen als er mensen zijn, dus n manieren.
In totaal zijn er dus n • Sⁿ_k

Samen geeft dat precies alle manieren om n + 1 mensen in k cykels te zetten, dus:

Sⁿ⁺¹_{k
=}Sⁿ_k-1 + nSⁿ_k

Met deze formule kun je de tabel hierboven makkelijk kolom na kolom vullen.
Neem bijvoorbeeld de S⁶₂ = 276. Die kun je vinden door 24 + 5 • 50 uit de vorige rij te combineren (die 5 is de n).