Subfaculteit (wiskunde)

Permutaties en derangementen van $n$ elementen, vergeleken met $10^n$

In de combinatoriek is de subfaculteit van $n$, genoteerd als $!n$ of $!(n)$, het aantal derangementen van een verzameling van $n$ elementen. De subfaculteit wordt naar Pierre Rémond de Montmort ook wel het montmort-getal genoemd.

Geschiedenis

Montmort - Essay d'analyse sur les jeux de hazard (1713, 2e editie)

Het tellen van het aantal derangementen van een permutatie is in 1708 voor het eerst genoemd door Pierre Rémond de Montmort (1678–1719) in zijn “Essay d'analyse sur les jeux de hazard” (Paris: Jacques Quillau). Montmort poneert het probleem, in vereenvoudigde vorm, via 13 geschudde en gesloten speelkaarten van een zelfde kleur (Problême du Treize): er wordt door de spelleider telkens een kaart open gelegd en tegelijk hardop geteld van 1 (= aas) tot en met 13 (= heer). Winst is er als de opengelegde kaart en het gesproken getal overeenkomen. Montmort besprak het probleem van de kans op winst met Johan Bernoulli (1667–1748) en met Nicolaas (I) Bernoulli (1687–1759). In de tweede editie van het Essay, gepubliceerd in 1713, staat het opgeloste probleem en worden ook enkele generalisaties gegeven.

Formules

De subfaculteit van $n$ kan voor $n>1$ recursief uitgedrukt worden in de formule:

$!(n)=n\cdot !(n-1)+(-1{)}^n$

Als startwaarde geldt:

$!(1)=0$

Er is ook een directe formule:

$!(n)=n!\cdot \sum _{k=0}^n\frac{(-1{)}^k}{k!}$

Voorbeelden

• De verzameling $V=\{1,2,3\}$ heeft slechts 2 derangementen. Aangezien geen van de getallen 1, 2 en 3 op zichzelf mag worden afgebeeld, kan 1 alleen op 2 of op 3 afgebeeld worden, waarmee de andere beelden ook vastliggen. De twee derangementen zijn:

$\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)=(231)$ en $\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)=(321)$,

weergegeven in matrix- en in cykelvorm.

Dus $!(3)=2$.

• Voor sinterklaas willen vier personen, genummerd 1, 2, 3 en 4, lootjes trekken, voorzien van die nummers, op zo'n manier dat geen van hen zichzelf trekt. Hoeveel verschillende trekkingen zijn er mogelijk?

Oplossing. Van de 24 permutaties voldoen de volgende 9:

$(2143),(2341),(2413),(3142),(3412),(3421),(4123),(4312),(4321)$

Overzicht

De waarden van de subfaculteit van $n$ voor $n=0,1,...,9$ zijn:

$n=$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$!(n)=$	$1$	$0$	$1$	$2$	$9$	$44$	$265$	$1854$	$14833$	$133496$

Opmerking

Een subfaculteit is (ook) een zogeheten rencontre-getal (Fr. rencontre = ontmoeting). Het aantal permutaties van $n$ elementen waarvan er $k$ op zichzelf worden afgebeeld, wordt namelijk rencontre-getal genoemd; zo'n getal kan worden genoteerd als $R(n,k)$. Voor $k=0$ is dan $!(n)=R(n,0)$.

Afleiding van de formules

Met recursie

Stel $n$ personen die met $1,2,3,\dots ,n$ zijn genummerd, doen lootjes voorzien van hun eigen nummer in een vaas en trekken elk een lootje. Hoeveel mogelijkheden zijn er waarbij geen van hen zijn eigen nummer trekt. De eerste persoon (nummer 1) trekt een lootje met het nummer $k\ne 1$. Daarvoor heeft hij $n-1$ mogelijkheden. Dan zijn er voor de persoon met nummer $k$ twee mogelijkheden.

1. Persoon $k$ trek het lot met nummer 1.
2. Persoon $k$ trekt een lot met een nummer dat ongelijk is aan 1.

Beide mogelijkheden zijn hieronder met een matrix in beeld gebracht.

$\left(\begin{array}{ccccccc}1& 2& 3& \dots & k& \dots & n\\ k& \ne 2& \ne 3& \dots & 1& \dots & \ne n\end{array}\right)$, $\left(\begin{array}{ccccccc}1& 2& 3& \dots & k& \dots & n\\ k& \ne 2& \ne 3& \dots & \ne 1& \dots & \ne n\end{array}\right)$

In het eerste geval is het probleem teruggebracht tot een trekking met $n-2$ personen; in het tweede geval mag persoon $k$ lot nummer 1 niet trekken, wat op hetzelfde aantal neerkomt als wanneer $k$ zijn eigen nummer niet mag trekken, dus een trekking met $n-1$ personen.

Stellen we (alleen voor de duidelijkheid) $d_n=!(n)$. Dan is dus:

$d_n=(n-1)(d_{n-2}+d_{n-1})$

Uitgewerkt:

$d_n-n{d}_{n-1}=-(d_{n-1}-(n-1)d_{n-2})$,

dus volgt, met gebruikmaking van

$d_2=1$ en $d_1=0$

$d_n-n{d}_{n-1}=(-1{)}^{(n-2)}{d}_2=(-1{)}^{(n-2)}=(-1{)}^n$

Hieruit volgt de eenvoudige recursieve betrekking:

$!(n)=n\cdot !(n-1)+(-1{)}^n$

Om de formule ook te laten gelden voor $n=1$, moet worden afgesproken dat:

$!(0)=1$

Dan is immers:

$!(1)=1\cdot !(0)-1=0$

Met het inclusie-exclusie-principe

Met behulp van het principe van in- en exclusie kan aangetoond worden dat:

$!(n)=n!\cdot \sum _{k=0}^n\frac{(-1{)}^k}{k!}$

Daartoe worden in de verzameling $S_n$ van alle permutaties de deelverzamelingen $A_k$ onderscheiden die bestaan uit de permutaties die ten minste $k$ elementen ongewijzigd laten. Het aantal permutaties in $A_k$ is:

$(\genfrac{}{}{0ex}{}{n}{k})\cdot (n-k)!$

Het aantal derangementen, dus permutaties die geen enkel element ongewijzigd laten, kan gevonden worden door van het totaal van $n!$ mogelijke permutaties eerst het aantal permutaties af te trekken waarvan minstens één element ongewijzigd is, dus het aantal elementen van $A_1$ exclusie: $n!-(\genfrac{}{}{0ex}{}{n}{1})\cdot (n-1)!$

Nu zijn de permutaties uit $A_2$, die 2 of meer elementen ongewijzigd laten, er dubbel afgetrokken, daarom moeten die er weer bijgeteld worden:

inclusie: $n!-(\genfrac{}{}{0ex}{}{n}{1})(n-1)!+(\genfrac{}{}{0ex}{}{n}{2})(n-2)!$

Maar dan zijn de permutaties uit $A_3$, die 3 of meer elementen ongewijzigd laten, weer te veel meegeteld, dus die moeten er weer af:

exclusie: $n!-(\genfrac{}{}{0ex}{}{n}{1})\cdot (n-1)!+(\genfrac{}{}{0ex}{}{n}{2})(n-2)!-(\genfrac{}{}{0ex}{}{n}{3})(n-3)!$

Zo gaat het verder tot uiteindelijk na $n$ keer optellen en aftrekken:

$d_n=n!-(\genfrac{}{}{0ex}{}{n}{1})(n-1)!+(\genfrac{}{}{0ex}{}{n}{2})(n-2)!-(\genfrac{}{}{0ex}{}{n}{3})(n-3)!+\dots +(-1{)}^n(\genfrac{}{}{0ex}{}{n}{n})0!$

Uit de definitie van de binomiaalcoëfficiënt volgt:

$(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=\frac{n!}{k!(n-k)!}(n-k)!=\frac{n!}{k!}$

zodat:

$d_n=n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\dots +(-1{)}^n\frac{n!}{n!}$

Na buiten haakjes brengen van $n!$ volgt dan inderdaad de hierboven vermelde eigenschap.

Opmerking

Uit de theorie van de taylorreeksen blijkt dat:

$e^{-x}=1+\frac{-x}{1!}+\frac{x^2}{2!}+\frac{-x^3}{3!}+\frac{x^4}{4!}+\dots =\sum _{k=0}^{\mathrm{\infty }}\frac{(-1{)}^k}{x^k}k!$,

waaruit, samen met de zojuist bewezen eigenschap, voor $x=1$ volgt dat:

$\underset{n\to \mathrm{\infty }}{\lim }\frac{!(n)}{n!}=\frac{1}{e}=0,36787\dots$

Omdat de onderhavige reeks snel convergeert, is voor $n\ge 1$:

$!(n)=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor$

Zie ook

• Faculteit
• Combinatie
• Permutatiegroep

Externe links

• On-line Encyclopedia of Integer Sequences – A000166
• Sjabloon:Aut: Derangement. Op: MathWorld—A Wolfram Web Resource.
• Sjabloon:Aut: Subfactorial. Op: MathWorld—A Wolfram Web Resource.
• Sjabloon:EnRencontre-getallen op de Engelstalige Wikipedia

Literatuur

• Sjabloon:Aut (2003) Let’s get deranged! Riverside (CA, USA): Department of Mathematics, University of California. PDF-bestand.
• Sjabloon:Aut (1993): De wiskunde van Sinterklaas. In: Euclides, jrg. 69, nr. 4; pp. 114–115.
• Sjabloon:Aut (2003): Derangements and Applications. In: Journal of Integer Sequences, vol 6.
• Sjabloon:Aut (2012): Bewijzen en redeneren. Leuven: Katholieke Universiteit; hoofdstuk 6 (PDF-bestand).
• Sjabloon:Aut (2010) De boom staat niet ver van de appel. In: Nieuwe Wiskrant, jrg. 30, nr. 1; pp. 29–32 (PDF-bestand).

Bronnen en noten

• Sjabloon:Aut (1997): The Art of Computer Programming, vol. 1; pp. 178–182.
• Sjabloon:Aut (2016): Over getallen gesproken – Talking about numbers. Zaltbommel: Van Haren Publishing; pp. 382–383.
• Biografie van P.R. de Montmort. Op: MT Archive, Universiteit van St Andrews.

---