WisFaq!

Kansrekenen volgorde boeken

De 6 delen van een encyclopedie worden één voor één op een boekenplank gezet. Wat is de kans dat er precies 5 delen fout staan?
Ik kom hier wel tot de goede oplossing:
Aantal mogelijkheden om 6 boeken te ordenen zonder restricties: 6! = 720
5 boeken uit 6 kiezen = 6 mogelijkheden (6 nCr 5) = 6
En er zijn dan 44 mogelijke manieren waarop je 5 boeken allemaal fout kan zetten. Aan die 44 kom ik dan wel door de mogelijkheden echt uit te schrijven (5! = 120 mogelijkheden om 5 boeken te plaatsen) en dan de opties te schrappen waarbij er 1 of meerdere boeken juist staan. Is er ook een manier om via logisch denken tot die 6 * 44 te komen? Want als ik wil berekenen wat de kans is dat alle 6 de boeken fout staan, zit ik op mijn werkwijze vast natuurlijk (of heeeel lang bezig :))
Alvast bedankt!

IK
7-12-2015

Antwoord

Hallo IK,

Dit is een zeer interessant probleem!

Wanneer je de getallen 1 t/m n op een rijtje moet zetten, zodat geen van de getallen op zijn eigen plaats blijft, dan noemen we zo'n rijtje een derangement. Het aantal derangementen van 1...n wordt de subfaculteit van n genoemd, notatie !n (lijkt veel op n faculteit: n!). Soms spreekt men ook van Montmortgetallen.

Het is duidelijk dat:

• !0 = 1
  
• !1 = 0
  
• !2 = 1
  

Om een formule te verzinnen, stellen we ons voor dat we te maken met personen genummerd van 1 t/m n een beker kiezen uit een groep bekers genummerd 1 t/m n. Het is de bedoeling dat niemand de beker met het "eigen nummer" kiest.
Persoon 1 begint en pakt beker i en kan dat op n-1 manieren doen. Nu gaan we naar persoon i. Voor de berekening is het nu interessant om twee gevallen te onderscheiden:

• We hernoemen beker 1 naar beker i. Dan hebben we een groep personen én bekers genummerd van 2 t/m n. Het aantal derangementen van deze groep is !(n-1). Dus dit levert in totaal (n-1)·!(n-1) mogelijkheden.
  
• In de situatie hierboven kan 1 situatie niet: persoon i kiest beker 1. Dan kiezen personen 1 en i elkaars beker. De overige n-2 personen hebben het oorspronkelijke probleem voorgeschoteld gekregen, met !(n-2) derangementen. We hebben dan dus in totaal (n-1)·!(n-2) mogelijkheden.
  

Hieruit blijkt dat de volgende recursieve formule geldt:
$$!n = (n-1)\cdot(!(n-1)+!(n-2))$$

Er blijken ook directe formules te zijn van deze subfaculteiten, zoals de volgende die faculteiten gebruikt:
$$!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$

Meer informatie vind je bij de Online Encyclopedia of Integer Sequences, zie de link hieronder.

Met vriendelijke groeten,

Zie A000166 - OEIS [https://oeis.org/A000166]

FvL
7-12-2015