Hoe groot is de kans dat je met kerstmis voor jezelf een cadeau moet kopen?

Sebastiaan, 17 jaar
11 januari 2010

Wij zijn thuis met 5. Als we namen trekken voor wie we moeten kopen, moeten we het telkens vele keren opnieuw doen omdat iemand zichzelf heeft getrokken.

Mijn vraag is dus: hoe bereken je de kans dat iemand zichzelf trekt in functie van het aantal personen die aan de trekking meedoen?.

Antwoord

Beste Sebastiaan


We zullen het vraagstuk eerst voor vijf personen bekijken en stap voor stap oplossen, maar je zal merken dat dit nogal snel omslachtig wordt als het aantal personen zou toenemen. Daarna bekijken we een algemenere formule voor een willekeurig aantal personen.

Namen trekken met vijf personen

De trekking loopt "mis" wanneer minstens iemand zijn eigen naam trekt. Als we de vijf personen voorstellen met de letters a, b, c, d en e, dan kunnen we een trekking voorstellen als een permutatie van "abcde", bijvoorbeeld: decab. Hiermee bedoelen we dan: persoon a koopt voor d, persoon b voor e, enzovoort. Dit is duidelijk een "slechte trekking" want c heeft zichzelf getrokken.

Laten we proberen het aantal mogelijkheden te tellen waarbij minstens één letter op dezelfde plaats terechtkomt, door de verschillende gevallen af te gaan.

- vijf letters op de juiste plaats: 1 mogelijkheid (abcde);
- vier: 0 mogelijkheden, want als er vier juist staan, moet de vijfde ook juist staan;
- drie: 3 uit 5 kiezen (combinatie) en er is maar één manier waarbij de overige twee niet op de juiste plaats staan: 5C3 = 10, bv. adcbe;
- twee: 2 uit 5 kiezen (combinatie) en er zijn twee manieren waarbij de overige drie niet op de juiste plaats staan: 5C2*2 = 20, bv. aecbd;
- een: 1 uit 5 kiezen (combinatie) en er zijn negen manieren waarbij de overige vier niet op de juiste plaats staan: 5C1*9 = 45, bv: adebc.

Als je niet direct inziet hoe we aan die getallen komen voor de overige plaatsen (1, 2, 9), dit kan je halen uit het gelijkaardig vraagstuk met minder personen, recursief dus.

Het totaal aantal mogelijkheden waarbij dus minstens iemand zichzelf trekt, is: 1+10+20+45 = 76 en het totaal aantal mogelijke permutaties is 5! = 120.
De kans dat er minstens iemand zichzelf trekt is bijgevolg 76/120 = 19/30 of 63,33...% en de kans op een succesvolle trekking is dan 1-76/120 = 44/120 = 11/30 of 36,66...%.

Het algemeen geval: n objecten herschikken

Nu weten we al waarom je vaak een nieuwe trekking moet doen (in jouw situatie heb je maar ongeveer 1 kans op 3 om een succesvolle trekking te hebben), maar hoe zit het in het algemeen wanneer we werken met n personen?

Daarvoor zoeken we opnieuw het aantal mogelijkheden waarbij geen enkel object op dezelfde plaats terechtkomt wanneer we n verschillende objecten herschikken. Voor n = 5 was dat 44, in het algemeen is dat een aantal d(n) met:

d(n) = n! . SOM(i van 0 tot n) (-1)i/(i!) 

We controleren bijvoorbeeld dit aantal voor n = 5, dan is:

d(5) = 5! . SOM(i van 0 tot 5) (-1)i/(i!) = 5! (1 - 1 + 1/2 - 1/6 + 1/24 - 1/120) = 44

We vinden opnieuw 44, maar deze formule laat toe het eenvoudig voor andere aantallen te bepalen. Om de kans te vinden, moet je nog delen door het totaal aantal permutaties en dat is n!. Met andere woorden: de kans dat bij een herschikking van n verschillende objecten, geen enkel object op de oorspronkelijke plaats terechtkomt, wordt gegeven door d(n)/n! met d(n) zoals hierboven.

Twee voorbeelden:
- drie personen: d(3)/3! = 1/3 of 33,33...%
- zeven personen: d(7)/7! =  103/280 of ongeveer 36,8%

Interessante opmerking: deze kans zal niet veel meer veranderen als je n laat toenemen en convergeert naar 1/e (ongeveer 0.36788) met e de constante van Euler (e = 2.71828...), als je n naar oneindig laat gaan.

Meer informatie over deze formule voor d(n) vind je op de Engelstalige wikipediapagina over "Derangements". Een manier om deze formule aan te tonen steunt op het principe van "inclusie en exclusie". Voor de wiskundige details of de afleiding, kan je een kijkje nemen op bijgevoegde links.

Hopelijk is je vraag hiermee beantwoord, anders reageer je maar.

Groeten
Tom

Reacties op dit antwoord

  • 11/01/2010 - Sebastiaan (vraagsteller)

    Beste Tom, Bedankt voor het antwoord! Het is zoals ik verwachtte dus echt wel een tamelijk ingewikkelde formule voor zoiets banaals. Graag had ik er eigenlijk ook nog een afgeleide van berekend, maar dit lijkt dus vrij onmogelijk omdat je met de faculteiten en de sommatie zit... Of bestaat er wel een manier om dit af te leiden of is dit een "functie" die enkel als rij te beschouwen valt?

  • 11/01/2010 -  (wetenschapper)

    Beste Sebastiaan De formule lijkt inderdaad vrij ingewikkeld, maar uiteindelijk valt het nogal mee: om de kans te bepalen moet je die d(n) delen door n!, maar in de formule voor d(n) stond een factor n!. Deze valt dus weg, voor de kans hou je precies die sommatie over: dit zijn breuken met in de noemers oplopende faculteiten en het teken van de breuk wisselt steeds. Die sommatie is natuurlijk "discreet", dit bestaat alleen voor natuurlijke getallen n. Je kan de faculteit wel uitbreiden naar een continue functie, maar dat heeft voor dit vraagstuk niet veel zin want dan gaat de realistische interpretatie verloren: je kan immers moeilijk namen trekken met bijvoorbeeld 2*pi-sqrt(2)+7 personen... Ik vermoed dat je de functie wou afleiden om de minimale en/of maximale kans te bepalen, als functie van het aantal personen. Aangezien de "uitschieters" in het begin (bij lage aantallen personen) zitten, kan dat nog vrij eenvoudig door ze gewoon af te gaan. Ik heb een grafiek bijgevoegd die de kans (op een "succesvolle trekking") geeft in functie van het aantal personen. Merk op dat de ook "speciale gevallen" kloppen: - bij 0 personen trekt niemand zichzelf, maar dit heeft weinig betekenis natuurlijk, - bij 1 persoon trek je sowieso jezelf, dus je hebt kans 0 op een "goede trekking". Vlak daarna, met twee personen, heb je de beste kans. Dit is 1/2 en dat is ook eenvoudig te begrijpen: met twee namen in de doos heb je 50 % kans om jezelf te trekken, 50 % om de andere naam te trekken. Wanneer het aantal personen oploopt, verkleint de kans wel dat een persoon zijn eigen naam trekt, maar de kans stijgt dat minstens iemand zichzelf trekt. Als je de speciale gevallen van n=0 en n=1 buiten beschouwing laat, heb je de grootste kans bij twee personen en de kleinste bij drie personen, zoals je in de grafiek kan zien. Merk ook op dat de kans snel 'stabiliseert' rond een vaste waarde, dit is precies 1/e zoals ik reeds in mijn vorig antwoord aangaf. Deze asymptotische waarde heb ik in de grafiek aangegeven met een stippellijn. Het is in elk geval een interessante vraag aangezien er ongetwijfeld veel gezinnen zijn die met een dergelijk systeem van namen trekken werken. Groeten Tom

Enkel de vraagsteller en de wetenschapper kunnen reageren op een antwoord.

Zoek andere vragen

© 2008-2018
Ik heb een vraag wordt gecoördineerd door het
Koninklijk Belgisch Instituut voor Natuurwetenschappen