Inden for det matematiske felt kombinatorik beskriver en fuldstændig forstyrrelse (Engelsk: (complete) derangement) 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 kaldes her for subfakultet eller det ’te forstyrrelsestal (Engelsk: hhv. sub-factorial og derangement number) . Notationer for subfakultet inkluderer eller n¡.

For kan n¡ beskrives som det nærmeste heltal til , hvor er antallet af elementer der skal forstyrres, og er Eulers tal.

Subfakultet kan benyttes i sandsynlighedsregning, hvor man kan bestemme sandsynligheden for at samtlige elementer er forstyrret, nærmer sig for .

Eksempel thumb|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.|450x450pxMan 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, , hvor den stokastiske variabel repræsenterer antal korrekte besvarede spørgsmål.

hvor sandsynligheden beregnes ved at bestemme antal måder man kan vælge 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 elementer, ved følgende formler:

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:

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

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

Enten sættes den på 's plads:

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

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

og det samlede antal måder er oppe på

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

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

Ved udvidelse af parenteserne fås:

Lukkede formel

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

Approksimation

Summen i den lukkede formel er et Taylorpolynomium for evalueret i , hvilket konvergerer mod for . Derfor kan subfakultet, for , estimeres ved at afrunde følgende udtryk til nærmeste heltal:

+ Eksakte og approksimative værdier for subfakultet012345678910111210129442651.85414.833133.4961.334.96114.684.570176.214.840−0,630,37−0,260,21−0,170,15−0,130,11−0,100,09−0,080,08−0,07

Delforstyrrelser thumb|Figur 2: Eulers differenstabel. Parenteserne repræsenterer og de røde tal repræsenterer . Venstre kant er , og højre kant er . 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.|right|450x450px En delforstyrrelse(Engelsk: sub-derangement) er en permutation, hvor de første elementer skal være forstyrrede. Antallet af delforstyrrelser for elementer, hvor elementer er forstyrrede, betegnes og kan beregnes rekursivt på følgende måde

hvilket også kan aflæses i Eulers differenstabel.

Referencer

Kategori:Heltalsfølger