Subfaculteit (wiskunde)

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
Permutaties en derangementen van n elementen, vergeleken met 10n

In de combinatoriek is de subfaculteit van , genoteerd als of ,[1] het aantal derangementen van een verzameling van elementen. Dit aantal wordt wel het montmort-getal genoemd zie de alinea Geschiedenis).

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.[2]
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:

Formules[bewerken]

De subfacuteit van kan voor recursief uitgedrukt worden in de formule:

Als startwaarde geldt:

Er is ook een directe formule:

Overzicht[bewerken]

De waarden van de subfaculteit van voor zijn:

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[bewerken]

Met recursie[bewerken]

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.

  1. Persoon trek het lot met nummer 1.
  2. 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[bewerken]

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 :

Geschiedenis[bewerken]

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.

Zie ook[bewerken]

Externe links[bewerken]

Literatuur[bewerken]

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

Bronnen en noten[bewerken]


  1. In de literatuur komen ook de schrijfwijzes ¡ en ¡ voor
  2. In 1815 is de notatie in matrix- en cykelvorm door A.L. Cauchy (1789-1857) geïntroduceerd.
    Zie: A.L. Cauchy (1815): Memoire sur le Nombre des Valeurs. In: Journal de l'École Polytechnique, tome X; pp. 1-28. Via: Google Boeken.