WisFaq!

Aantal permutaties van een n-verzameling is gelijk aan n!

Geen idee waar ik moet beginnen. Wie kan me helpen?

Bewijs met behulp van volledige inductie dat het aantal permutaties van een n-verzameling gelijk is aan n!.

Loes van Voorst
5-10-2004

Antwoord

dag Loes,

Een bewijs met volledige inductie steunt op twee stappen:
Eerst bewijs je dat het gestelde waar is voor n=1.
Vervolgens neem je aan dat het waar is voor zekere n, en gaat daaruit bewijzen dat het dan ook waar moet zijn voor n+1.
Voor n=1 geldt dat je verzameling maar één element bevat, waardoor het aantal permutaties gelijk is aan 1. Dus dat zit alvast goed.
Neem nu aan dat het aantal permutaties van een verzameling met n elementen gelijk is aan n!
Neem dan een verzameling van n+1 elementen.
Haal hier één element x uit. Resteert een verzameling van n elementen. Deze n elementen kun je dus op n! manieren permuteren.
Neem een permutatie van deze n elementen.
Hier kun je je element x op n+1 plaatsen invoegen.
Het totaal aantal permutaties met x erbij is dus gelijk aan (n+1)·n!
en dit is juist gelijk aan (n+1)!
Duidelijk?
groet,

Anneke
5-10-2004