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

Geschiedenis

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  kan voor  recursief uitgedrukt worden in de formule:

Als startwaarde geldt:

Er is ook een directe formule:

Voorbeelden
 De verzameling  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: 
 en  ,
 weergegeven in matrix- en in cykelvorm.
 Dus .
 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:

Overzicht
De waarden van de subfaculteit van  voor  zijn: 
{| class="wikitable"
|-
|  ||  ||  ||  ||  ||  ||  ||  ||  ||  || 
|-
|  ||  ||  ||  ||  ||  ||  ||  ||  ||  || 
|}
Opmerking 
Een subfaculteit is (ook) een zogeheten rencontre-getal (Fr. rencontre = ontmoeting). Het aantal permutaties van  elementen waarvan er  op zichzelf worden afgebeeld, wordt namelijk rencontre-getal genoemd; zo'n getal kan worden genoteerd als . Voor  is dan .

Afleiding van de formules

Met recursie
Stel  personen die met  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 . Daarvoor heeft hij  mogelijkheden. Dan zijn er voor de persoon met nummer  twee mogelijkheden.
 Persoon  trek het lot met nummer 1.
 Persoon  trekt een lot met een nummer dat ongelijk is aan 1.
Beide mogelijkheden zijn hieronder met een matrix in beeld gebracht.
, 

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

Stellen we (alleen voor de duidelijkheid) . Dan is dus:

Uitgewerkt:
,

dus volgt, met gebruikmaking van
 en 

Hieruit volgt de eenvoudige recursieve betrekking:

Om de formule ook te laten gelden voor , moet worden afgesproken dat:

Dan is immers:

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

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

Het aantal derangementen, dus permutaties die geen enkel element ongewijzigd laten, kan gevonden worden door van het totaal van  mogelijke permutaties eerst het aantal permutaties af te trekken waarvan minstens één element ongewijzigd is, dus het aantal elementen van  
exclusie: 

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

inclusie: 

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

exclusie: 

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

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

zodat:

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

Opmerking
Uit de theorie van de taylorreeksen blijkt dat:
,

waaruit, samen met de zojuist bewezen eigenschap, voor  volgt dat:

Omdat de onderhavige reeks snel convergeert, is voor :

Zie ook
 Faculteit
 Combinatie
 Permutatiegroep

Externe links
 On-line Encyclopedia of Integer Sequences – A000166
 : Derangement. Op: MathWorld—A Wolfram Web Resource.
 : Subfactorial. Op: MathWorld—A Wolfram Web Resource.
 Rencontre-getallen op de Engelstalige Wikipedia

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

Bronnen en noten
  (1997): The Art of Computer Programming, vol. 1; pp. 178–182.
  (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.

Combinatoriek
Getaltheorie
Wiskundige schrijfwijze