Stel, dat je met je vader, moeder en zusje of met drie vrienden besluit om Sinterklaas te vieren. Voor het gemak noemen we de personen $A, B, C$ en $D$. Je maakt 4 briefjes (of ook wel lootjes) met de namen van de 4 personen die meedoen. Vervolgens trekt iedereen een lootje. Het aantal manieren dat de lootjes getrokken kunnen worden is $4! = 4 \times 3 \times 2 \times 1 = 24$.

Stel, dat de trekking $A \Rightarrow C, B \Rightarrow B, C \Rightarrow D, D \Rightarrow A$ oplevert. Dat betekent, $A$ trekt $C$, $B$ trekt zichzelf, $C$ trekt $D$, en $D$ trekt $A$. Na deze trekking kan het Sinterklaasfeest nog niet worden gevierd. Iedereen moet immers een lootje met de naam van een ander trekken. Er is maar één manier, waarop ieder zijn eigen lootje trekt en dat is ($A \Rightarrow A, B \Rightarrow B, C \Rightarrow C, D \Rightarrow D$). De kans daarop is $1/24$. Hoe groot is de kans dat twee personen zichzelf trekken? Dat laten we als een opdracht voor de lezer. Via de knop [Bekijk oplossing] hieronder is het antwoord terug te vinden. Op hoeveel manieren krijgt niemand zijn eigen lootje? Er zijn $9$ oplossingen. Het zoeken van deze oplossingen laten we aan de lezer over. Ook deze $9$ oplossingen vind je hieronder. Het aantal manieren waarop niemand zijn eigen lootje trekt wordt wiskundig als $!4 = 9$ genoteerd. $!4$ wordt uitgesproken als subfaculteit $4$. Soms wordt de naam verstoring gebruikt, omdat je het resultaat niet wenst. Oorspronkelijk gebruikte men het Engelse/Franse woord ervoor: derangement. Tenslotte wordt dit getal ook het ontmoetingsgetal van 4 genoemd.

Opgave 1 Probeer nu zelf $!1$, $!2$ en $!3$ te vinden.

ReCursie

Net zoals je $n!$ kunt maken uit $(n – 1)!$ door met n te vermenigvuldigen, kunnen we $!n$ uit eerdere subfaculteiten maken. Zo'n constructie heet recursie.

In ons geval geldt $!n = (n-1) \times (!(n-2) + !(n -1))$. In opgave 1 kon je vinden $!1 = 0$ en $!2 = 1$. We leiden deze recursie af in het kader. Nu kunnen we voor elk aantal personen berekenen hoeveel derangementen er zijn:

1. $0$ (gegeven)
2. $1$ (gegeven)
3. $2 \times (0 + 1) = 2$
4. $3 \times (1 + 2) = 9$
5. $4 \times (2 + 9) = 44$
6. $5 \times (9 + 44) = 265$

De volgende waarden zijn: $1\,854$,   $14\,833$,   $133\,496$,   $1\,334\,961$,   $14\,684\,570$,   $176\,214\,841$,   $2\,290\,792\,932$,   $32\,071\,101\,049$,   $481\,066\,515\,734$,   $7\,697\,064\,251\,745$,   $130\,850\,092\,279\,664$,   $2\,355\,301\,661\,033\,953$, $\dots$.

Een andere ReCursie

Er bestaat ook een andere recursie. We gaan hier niet afleiden hoe je er aan komt, maar we geven de recursie: $!n = n \times !(n - 1) + (-1)^n$.

Opgave 2 Controleer dat de recursie voor bovenstaande waarden van subfaculteit klopt.

Hoe groot is de kans dat het trekken van lootjes slaagt?

Uiteraard ben je geïnteresseerd in deze vraag. Maar daarmee kom je uit op nogal lastige wiskunde. Je kunt afleiden dat $!n = n!/0! - n!/1! + n!/2! - n!/3! + n!/4! \cdots +(-1)^n n!/n!$. Dit zijn de eerste $n+1$ termen van de reeks $n!e^x$ in met $x = -1$. Dat klopt inderdaad. Het blijkt dat $!n/n! \approx e^{-1} \approx 0{,}3679$. En dit is de kans dat een trekking slaagt.

		Bewijs voor de reCursie $$!n = (n - 1)(!(n - 2) + !(n - 1)).$$ We drukken $!n$ uit in $!(n - 1)$ en $!(n - 2)$. Dat doen we door de lootjes trekkingen in twee soorten te splitsen. We kijken naar de persoon $P_k$ die door persoon $P_n$ getrokken wordt. Soort 1: $P_k$ trekt $P_1$; hier horen dan $!(n - 2)$ goede trekkingen binnen de groep van de andere $n - 2$ personen. Dit kunnen we $n - 1$ keer doen, en dat levert totaal $(n - 1) \cdot !(n - 2)$ goede trekkingen waarbij $P_1$ en een andere persoon elkaar trekken. Soort 2: $P_k$ trekt $P_1$ niet, maar wel $P_l$, en verder is er nog $P_m$ die het lootje van $P_1$ trekt. Hiermee maken we een goede trekking in de groep $\{P_1, \dots, P_{n-1}\}$, namelijk door $P_m$ het lootje van $P_k$ te geven. En van elke goede trekking in de groep $\{P_1, \dots, P_{n-1}\}$ kunnen de zo $n - 1$ trekkingen voor de hele groep maken: neem persoon $P_k$ en nummer $m$ en $l$ zó dat $P_m$ het lootje van $P_k$ krijgt en $P_k$ het lootje van $P_l$. Geef nu $P_1$ het lootje van $P_k$ en $P_m$ het lootje van $P_1$. (Het kan zijn dat $m = l$, dan vormen $P_1, P_k$ en $P_l$ een driehoek.) Van deze soort zijn er dus $(n - 1) \cdot !(n - 1)$ goede trekkingen. In totaal zijn dat er dus $(n - 1) \cdot (!(n - 1) + !(n - 2))$ goede trekkingen.