WisFaq!

Re: Zes rijbewijzen, zes mensen

Dank je, helaas ken ik dat niet, derangementen... De vraag zou beantwoord moeten kunnen worden met de klassieke groeperingen die onze lln kennen; te weten (herhalings)variaties, -permutaties en -combinaties...Is dat dan niet mogelijk??

Nathalie Meulemans
6-3-2009

Antwoord

Het enige is voor kleine waarden, ik zou zeggen t/m n=4 is het niet al te moeilijk om gewoon systematisch alle mogelijkheden op te schrijven, eventueel met een boom, maar daarboven zal lastig worden. Vraag c is dan wel te doen.

Misschien kunnen de leerlingen met wat hulp ook een recursie formule van graad 2 bedenken:
Gegeven een derangement met n-1 elementen, bijvoorbeeld n-1=5. Nu kan een extra element (een zesde) op alle plaatsen staan behalve op plaats 6, dus op n-1=5 plaatsen. Daarmee hebben we al (n-1)·d(n-1)=5·d(5) derangementen voor n (=6) elementen. Maar als er van die eerste n-1 elementen een op z'n plaats staat kunnen we die verwisselen met het n-de element. Bijvoorbeeld als het derde element op z'n plaats staat en de andere 1,2,4 en 5 niet, dan zetten we de 6 op plaats 3 en de 3 op plaats 6. Daarmee hebben we weer een derangement.
Dat zijn er dus (n-1)·d(n-2).
Gevolg: d(n)=(n-1)(d(n-1)+d(n-2)).
Zo kan je beginnen met d(0)=1, d(1)=0 geeft d(2)=1·(1+0)=1;
d(3)=2·(d(2)+d(1))=2(1+0)=2; d(4)=3·(1+2)=9; d(5)=4·(2+9)=44 en tenslotte d(6)=5(9+44)=265.
Met behulp van formele machtrekksen kan je hiervan een direct formule opstellen, maar ik neem aan dat dat zeker te ver voert.

Het probleem staat overigens bekend als het het Sinterklaas lootjes probleem, waarbij n mensen hun naam op een briefje schrijven, die dan worden uitgedeeld, zodat iedereen een cadeautje maakt voor de persoon op zijn getrokken briefje. De kans dat niemand zichzelf trekt blijk dan ook bij groten groepen slechts 1/e te zijn.

Groet,
Lieke.

ldr
6-3-2009