Nepořádek (permutace)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. prosince 2021; ověření vyžaduje 1 úpravu .

V kombinatorice je porucha permutací bez pevných bodů .

Příklady

Kontrola práce

Řekněme, že profesor dal čtyřem studentům (říkejme jim A, B, C a D) test a pak je požádal, aby si to navzájem zkontrolovali. Žádný student by samozřejmě neměl kontrolovat svůj vlastní test. Kolik možností má profesor pro distribuci kontrolních testů, ve kterých žádný student nedostane vlastní práci? Ze všech 24 permutací (4!) pro návrat práce je pro nás vhodných pouze 9 poruch:

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

V jakékoli jiné permutaci těchto 4 prvků dostane alespoň jeden student svůj test ke kontrole.

Problém s písmeny

Výpočet množství nepořádku je populární problém v matematice olympiády , který se vyskytuje v různých formulacích, jako je problém nepořádku , problém s písmeny , problém setkání a tak dále.

Pokud jsou dopisy náhodně umístěny do různých obálek, jaká je pravděpodobnost, že některé z dopisů skončí ve vlastní obálce?

n

n

Odpověď je dána výrazem

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

Odpověď tedy slabě závisí na počtu dopisů a obálek a je přibližně rovna konstantě . $1-{\frac {1}{e}}\cca 0{,}63212$

Počet nepokojů

Počet všech poruch řádu n lze vypočítat pomocí principu inkluze-vyloučení a je dán vztahem

!n=n!-{\frac {n!}{1!}}+{\frac {n!}{2!}}-{\frac {n!}{3!}}+\tečky +(-1)^{n}{\frac {n!}{n!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{ k!}},

který se nazývá subfaktoriál n .

Počet poruch odpovídá rekurzivním vztahům $!n=d(n)$

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

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

kde a . $d(1)=0$ $d(2)=1$

Vzhledem k tomu, že se hodnota chová jako . Navíc, když to může být reprezentováno jako výsledek zaokrouhlení čísla . $\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}$ $!n$ $n$ ${\frac {n!}{e))$ $n>0$ ${\frac {n!}{e))$

Nepořádek (permutace)

Příklady

Kontrola práce

Problém s písmeny

Počet nepokojů

Viz také

Poznámky

Odkazy