WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Formule herleiden

Ik zit met het volgende probleem:

Hoe kun je aantonen dat de formule

P(n)=^A(n)/_n!

herleid kan worden tot

P(n)=^n-1/_n·P(n-1)+¹/_n·P(n-2)

, waarbij
P(n) is de kans op een permutatie van n zonder dekpunten, en A(n) het aantal permutaties van n zonder dekpunten
Bas
Leerling bovenbouw havo-vwo - vrijdag 15 april 2005

Antwoord

Hallo Bas
De formule die je wilt bewijzen voor P(n)'s volgt direct uit de volgende relatie voor de A(n)'s:
A(n) = (n - 1)[ A(n - 1) + A(n - 2) ] (deel maar door n!)
Denk voor het gemak aan het probleem van de sinterklaassurprises. Namen trekken.
Personen 1, 2, . . . , n trekken ieder een kaartje uit een doos met kaartjes genummerd 1 t/m n.
Totaal aantal mogelijkheden n!. Aantal goede mogelijkheden A(n), waarbij niemand zijn eigen nummer trekt.(Dit is het aantal permutaties van {1, . . , n} waarbij geen enkel element op zijn eigen plaats terecht komt)
We kijken nu naar persoon 1;
We verdelen het aantal goede trekkingen in n -1 groepen, groep 2 t/m groep n.
In groep k stoppen we de goede trekkingen waarbij persoon 1 kaart k getrokken heeft.
Die n -1 groepen zijn allemaal even groot. We bepalen het aantal trekkingen in groep 2.
Groep 2 splitsen we in twee delen:
Deel 1 bevat de trekkingen waarbij 1 en 2 elkaar getrokken hebben en verder niemand van de overige n - 2 personen zichzelf. Deel 1 bevat dus A(n-2) permutaties.
Deel 2 bevat de trekkingen waarbij persoon 1 kaart 2 trekt maar persoon 2 niet kaart 1 trekt.
Deel 2 bevat A(n-1) trekkingen. Immers nu is er voor ieder van de n -1 personen(2 t/m n) een verboden kaart. ( Nadat persoon 1 kaart 2 getrokken heeft, zijn de kaarten 1, 3, 4, . . , n nog in de doos. Nu mag persoon 2 niet kaart 1 trekken, 3 niet 3, 4 niet 4 enz)
Dus het aantal goede permutaties in ieder van de n -1 groepen is gelijk aan A(n-1) + A(n-2)
Daarmee is de formule bewezen.
Groeten

JCS

Vragen naar aanleiding van dit antwoord? Klik rechts..!
donderdag 21 april 2005