Mizerie (permutare)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 decembrie 2021; verificarea necesită 1 editare .

În combinatorică , o tulburare este o permutare fără puncte fixe .

Exemple

Verificare lucru

Să presupunem că un profesor a dat patru studenți (să le numim A, B, C și D) un test și apoi le-a cerut să-l verifice între ei. Desigur, niciun student nu ar trebui să-și verifice propriul test. Câte opțiuni are profesorul pentru distribuirea testelor de control în care niciun student nu își primește propria muncă? Din toate cele 24 de permutări (4!) pentru întoarcerea muncii, doar 9 tulburări ne sunt potrivite:

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

În orice altă permutare a acestor 4 elemente, cel puțin un student își face testul pentru a fi verificat.

Problema scrisorilor

Calcularea cantității de dezordine este o problemă populară în matematica olimpiadei , care apare în diferite formulări, cum ar fi problema tulburării , problema literelor , problema întâlnirii și așa mai departe.

Dacă scrisorile sunt plasate aleatoriu în plicuri diferite, care este probabilitatea ca oricare dintre scrisori să ajungă în propriul plic?

n

n

Răspunsul este dat de expresia

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

Astfel, răspunsul depinde slab de numărul de scrisori și plicuri și este aproximativ egal cu constanta . $1-{\frac {1}{e}}\aprox 0{,}63212$

Numărul de revolte

Numărul tuturor tulburărilor de ordin n poate fi calculat utilizând principiul de includere-excludere și este dat de

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

care se numește subfactorialul lui n .

Numărul tulburărilor satisface relaţiile recursive $!n=d(n)$

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

și

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

unde si . $d(1)=0$ $d(2)=1$

Având în vedere faptul că , valoarea se comportă ca . Mai mult, atunci când poate fi reprezentat ca rezultat al rotunjirii numărului . $\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}$ $!n$ $n$ ${\frac {n!}{e))$ $n>0$ ${\frac {n!}{e))$

Mizerie (permutare)

Exemple

Verificare lucru

Problema scrisorilor

Numărul de revolte

Vezi și

Note

Link -uri