Mess (permutation)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 december 2021; verifiering kräver 1 redigering .

Inom kombinatorik är en störning en permutation utan fixpunkter .

Exempel

Kontrollerar arbete

Låt oss säga att en professor gav fyra elever (låt oss kalla dem A, B, C och D) ett test och bad dem sedan kontrollera det med varandra. Naturligtvis ska ingen elev kontrollera sitt eget prov. Hur många alternativ har professorn för att distribuera kontrollprov där ingen student får eget arbete? Av alla 24 permutationer (4!) för återgång av arbete är endast 9 störningar lämpliga för oss:

BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA.

I någon annan permutation av dessa 4 element får minst en elev sitt test för att kontrolleras.

Bokstavsproblem

Att beräkna mängden störningar är ett populärt problem i Olympiadens matematik , som förekommer i olika formuleringar som störningsproblemet , bokstavsproblemet , mötesproblemet och så vidare.

Om brev slumpmässigt placeras i olika kuvert, vad är sannolikheten för att någon av breven hamnar i sitt eget kuvert?

n

n

Svaret ges av uttrycket

1-{\frac {!n}{n!}}\approx 1-{\frac {1}{e}}.

Svaret beror således svagt på antalet bokstäver och kuvert och är ungefär lika med konstanten . $1-{\frac {1}{e}}\approx 0{,}63212$

Antal upplopp

Antalet alla störningar av ordning n kan beräknas med hjälp av inkluderings-exkluderingsprincipen och ges av

!n=n!-{\frac {n!}{1!}}+{\frac {n!}{2!}}-{\frac {n!}{3!}}+\prickar +(-1)^{n}{\frac {n!}{n!}}=\summa _{k=0}^{n}(-1)^{k}{\frac {n!}{ k!}},

som kallas subfaktoriell av n .

Antalet störningar tillfredsställer de rekursiva relationerna $!n=d(n)$

d(n)=(n-1)[d(n-1)+d(n-2)]

och

d(n)=nd(n-1)+(-1)^{n},

var och . $d(1)=0$ $d(2)=1$

Med tanke på att värdet beter sig som . Dessutom, när det kan representeras som ett resultat av avrundning av talet . $\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}$ $!n$ $n$ ${\frac {n!}{e))$ $n>0$ ${\frac {n!}{e))$

Mess (permutation)

Exempel

Kontrollerar arbete

Bokstavsproblem

Antal upplopp

Se även

Anteckningar

Länkar