Sinterklaas is weer in het land. Rond Sinterklaas zijn er veel onzekerheden. Heeft de boot alle cadeaus bij zich en kan de Wegwijspiet de weg vinden? Hoe ziet Piet er dit jaar uit? Wie heeft wie met lootjes trekken? Achter dat laatste zit veel wiskunde. Zo kun je uitrekenen hoeveel mogelijke manieren er zijn om lootjes te trekken, en wat de kans is dat niemand zichzelf heeft. Hier komt het getal e om de hoek kijken. En je kan partities gebruiken om te kijken naar de “structuur” van het lootjes trekken.
Bij lootjes trekken stop je ieders naam in een bak, en trek je één voor één een naam uit het bakje. Het lootjes trekken is pas geslaagd als niemand zichzelf heeft. Je moet dus minimaal met z’n tweeën zijn. Laten we de mensen als naam de letters van het alfabet geven. Als je met twee bent is er maar één mogelijke uitkomst, namelijk a heeft b, en b heeft a. Als je met z’n drieën bent zijn er twee mogelijke uitkomsten: a heeft b, b heeft c en c heeft a, of a heeft c, c heeft b en b heeft a. Beide uitkomsten zijn weer te geven als een cirkel. We kunnen zeggen dat er maar één mogelijke “structuur” is als je met z’n drieën lootjes trekt. Als je met z’n vieren bent zijn er in totaal twee mogelijke structuren. Of je vormt een cirkel met z’n vieren, of je hebt twee paren die elkaar hebben. Zo’n cirkel kan op zes manieren, de paren op drie manieren. In totaal zijn er dus negen mogelijkheden om met z’n vieren lootjes te trekken.
Aantal mogelijke manieren om lootjes te trekken met n mensen
Dit vraagt natuurlijk om een algemene formule voor het aantal manieren om lootjes te trekken met een willekeurig aantal mensen, dat we n noemen. Het aantal mogelijkheden om lootjes te trekken zonder dat iemand zichzelf heeft noemen we . Op deze site is mooi te zien dat de volgende formule geldt:
.
Als je in deze formule n=4 invult kom je inderdaad uit op negen:
Het aantal mogelijkheden loopt snel op. Met tien mensen zijn er al meer dan een miljoen mogelijke uitkomsten. Het totale aantal manieren om lootjes te trekken, inclusief de uitkomsten waarbij iemand wel zichzelf heeft is n!. De eerste persoon heeft keuze uit n, de tweede nog uit n-1, etc. De kans dat niemand zichzelf heeft is daarom:
Als n naar oneindig gaat nadert dit 1/e, ongeveer 36,79%. En die kans komt al heel snel bij 1/e in de buurt. Als het aantal mensen toeneemt, neemt de kans dat bijvoorbeeld de eerste persoon zichzelf heeft af, maar er zijn meer personen waarbij het “mis” kan gaan. Deze twee effecten heffen elkaar op, waardoor de kans dat niemand zichzelf heeft vanaf zeven mensen altijd afgerond 36,79% is.
Aantal “structuren” om lootjes te trekken
Er zijn bij vier mensen dus negen mogelijkheden, maar slechts twee verschillende structuren. Hoeveel van die structuren zijn er mogelijk bij een willekeurig aantal mensen? De twee structuren, 4 en 2+2 zijn partities van 4. Een partitie is een manier om een getal te splitsen in gehele getallen. In totaal zijn er vijf partities van 4: (1+1+1+1), (1+1+2), (1+3), (2+2) en (4). Bij partities zet je getallen altijd op volgorde van klein naar groot, zodat je (1+3) en (3+1) niet dubbel telt. Berekenen wat het aantal partities van n is is trouwens een hele klus. Als je daar meer over wilt weten kun je bijvoorbeeld hier kijken.
Het aantal structuren om lootjes te trekken met n mensen is dus gelijk aan het aantal partities van n, p(n), waar geen 1 in voorkomt. Hoeveel mogelijke partities zijn er met een 1? Als er een 1 in voorkomt, is wat overblijft een partitie van (n-1). Er zijn dus p(n)-p(n-1) structuren. Het aantal structuren is een stuk kleiner dan het aantal manieren om lootjes te trekken. Bijvoorbeeld, als je met 14 mensen bent zijn er ruim 32 miljard mogelijke uitkomsten, maar slechts 34 structuren.
Ik kwam op het idee om naar deze structuren te kijken door een lezing van Rogier Bos over “Muzikale reflecties op symmetrie, symmetrische bespiegelingen over muziek” op de dag van de Nederlandse Vereniging van Wiskundeleraren. Hij heeft samen met Susanne Tak ook een boek geschreven over symmetrie in telproblemen en puzzles.
In mijn familie hebben we met negen mensen lootjes getrokken. Dat kan op 133.496 verschillende manieren, en met acht mogelijke structuren. Hieronder is voor de liefhebbers van combinatoriek te zien hoeveel mogelijkheden er per structuur zijn. Omdat ik weet wie ik heb, en van nog drie mensen weet wie ze hebben vallen er al flink wat mogelijke structuren af. Hoe het precies zit merken we over een week tijdens het voorlezen van de gedichten!
Lootjes trekken met 9 mensen: totaal 133.496 manieren
Bronnen:
http://www.hhofstede.nl/modules/lootjestrekken.htm
Leuk stukje, en volgens mij werkt lootjestrekken.nl altijd met een circulaire structuur. Empirisch onderzoek (n=6, 4 jaar – oeps, 1 jaar n=7) heeft aangetoond dat we nooit iemand opnieuw als “eerste gever” hebben moeten aanwijzen.