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
Student universiteit België - maandag 7 december 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.
