Derangement

Denne artikel bør gennemlæses af en person med fagkendskab for at sikre den faglige korrekthed.

Inden for det matematiske felt kombinatorik beskriver en fuldstændig forstyrrelse (Engelsk: (complete) derangement)[kilde mangler] en permutation af en sekvens, hvor ingen elementer er på deres originale plads.

Antallet af mulige fuldstændige forstyrrelser af en sekvens af længden n kaldes her for n subfakultet[kilde mangler] eller det n’te forstyrrelsestal (Engelsk: hhv. sub-factorial og derangement number)[kilde mangler] . Notationer for subfakultet inkluderer !n,Dn,dn eller n¡.

For n>0 kan n¡ beskrives som det nærmeste heltal til n!/e, hvor n er antallet af elementer der skal forstyrres, og e≈2,718281 er Eulers tal.

Subfakultet kan benyttes i sandsynlighedsregning, hvor man kan bestemme sandsynligheden for at samtlige n elementer er forstyrret, nærmer sig 1/e≈37% for n→∞.

Eksempel

Figur 1: Samtlige parringer, hvor ét spørgsmål (1-4) forbindes til ét svar (A-D). Streger for korrekte svar er grønne, forkerte svar er mørkerøde og for prøvebesvarelser, hvor alle svar er forkerte, er alle streger farvet røde.

Man kan betragte en parringstest, hvor der skal sættes streg mellem spørgsmål og svar. Hvert spørgsmål må kun parres med ét svar, og alle svar har ét tilhørende spørgsmål. Ved en forstyrrelse, er ingen svar korrekte, dvs. stemmer overens med svararket. Se figur 1, hvor de grønne streger illustrerer et korrekt svar, lyserøde streger et forkert svar og de røde streger viser, at det er en fuldt forstyrret sekvens, altså ingen svar er korrekte.

Ud fra figur 1 kan det ses, at der i alt er 9 svarkombinationer, hvor ingen af dem er rigtige  (rød farve).

Det kan også bruges til at finde forventningsværdien, E(X), hvor den stokastiske variabel X repræsenterer antal korrekte besvarede spørgsmål.

E(X)=∑x=0nx⋅P(X=x)=∑x=0nx⋅|X=x||P(n,n)|=∑x=0nx⋅(nx)⋅(n−x)¡n!=∑x=0nx⋅n!x!(n−x)!⋅(n−x)¡n!=∑x=0n(n−x)¡(x−1)!(n−x)!

hvor sandsynligheden beregnes ved at bestemme antal måder man kan vælge x svar til at være rigtige, via kombinationer og gange med hvor mange måder man kan forstyrre resten, via multiplikationsprincippet, og dividere med størrelsen af hele udfaldsrummet, dvs. samtlige permutationer af svarene.

Formler og sætninger

Rekursive formler

Subfakultet for en sekvens kan bestemmes rekursivt ved at konstruere Eulers differenstabel(figur 2), eller, for n≥2 elementer, ved følgende formler:

n¡=(n−1)!∑k=0n−2k¡k!=(n−1)((n−1)¡+(n−2)¡)Bevis

Hvis man betragter hvert element, som en individuel størrelse der omplaceres, hvor ingen må forblive på deres oprindelige position, kan en konfiguration opstilles, hvorved man først forstyrrer første element. Hvis man repræsenterer sekvensen af elementer som:

ABCDE…

Skal A placeres valgfrit på de øvrige pladser, hvilket kan gøres på: n−1 måder. Eftersom det er et symmetrisk valg kan det fx antages at den er placeret på B's plads. Her får vi:_ A _ _ _ ...

Nu kan B placeres valgfrit på to asymmetriske måder.

Enten sættes den på A's plads:B A _ _ _ ...

Hvorefter de resterende elementer også skal forstyrres, derigennem bliver det samlede antal måder at forstyrre alle elementer i sekvensen:

(n−1)((n−2)¡)

Ellers skal den sættes på en af de øvrige n−2 pladser helt symmetrisk, hvilket kan antages at være C

_ A B _ _ ...

og det samlede antal måder er oppe på(n−1)((n−2)¡+(n−2))

Nu skal C placeres præcis som B med én færre valgmuligheder, hvilket giver følgende antal måder:

(n−1)((n−2)¡+(n−2)((n−3)¡+(n−3)))

Dette argument kan føres gennem hele sekvensen, hvoraf følgende formel kan udledes:

n¡=(n−1)((n−2)¡+(n−2)((n−3)¡+(n−3)((n−4)¡+...+3(2¡+2(1¡+1⋅0¡))...))

Ved udvidelse af parenteserne fås:

n¡=(n−1)(n−2)¡+(n−1)(n−2)(n−3)¡+(n−1)(n−2)(n−3)(n−4)¡+...+(n−1)!2!2¡+(n−1)!1!1¡+(n−1)!0!0¡=∑k=0n−2(n−1)!k!k¡=(n−1)!∑k=0n−2k¡k!

Lukkede formel

Subfakultet kan også udtrykkes ved en lukket formel baseret på en alternerende sum:

n¡=n!∑k=0n(−1)kk!

Approksimation

Summen i den lukkede formel er et Taylorpolynomium for e−x evalueret i x=−1, hvilket konvergerer mod 1e for n→∞. Derfor kan subfakultet, for n>0, estimeres ved at afrunde følgende udtryk til nærmeste heltal:

n¡=[n!e]

Eksakte og approksimative værdier for subfakultet
n 0 1 2 3 4 5 6 7 8 9 10 11 12
n¡ 1 0 1 2 9 44 265 1.854 14.833 133.496 1.334.961 14.684.570 176.214.840
n!e−n¡ −0,63 0,37 −0,26 0,21 −0,17 0,15 −0,13 0,11 −0,10 0,09 −0,08 0,08 −0,07

Delforstyrrelser

Figur 2: Eulers differenstabel. Parenteserne repræsenterer (n,n−k) og de røde tal repræsenterer D(n,n−k). Venstre kant er D(n,n)=n¡, og højre kant er D(n,0)=n!. Den er dannet ved at starte med højre kant, og så bestemmer man et felt ved at trække feltet ovenover til højre fra feltet til højre.

En delforstyrrelse(Engelsk: sub-derangement) er en permutation, hvor de første k elementer skal være forstyrrede. Antallet af delforstyrrelser for n elementer, hvor k elementer er forstyrrede, betegnes D(n,k) og kan beregnes rekursivt på følgende måde

D(n,k+1)=D(n,k)−D(n−1,k)

hvilket også kan aflæses i Eulers differenstabel.