Demutarea (matematica)

În combinatorie , permutațiile unui set care nu fixează niciun element, sau astfel încât niciunul dintre elementele setului inițial să nu apară în poziția sa inițială, se numesc dismutații (sau răsturnări sau permutări complete ).

În mod formal, dacă permutările unei mulțimi X sunt funcțiile bijective $p:X\rightarrow X$ ${\ displaystyle p: X \ rightarrow X}$ $p: X \ dreapta X$ , dismutațiile lui X sunt funcțiile bijective $p:X\rightarrow X$ ${\ displaystyle p: X \ rightarrow X}$ $p: X \ dreapta X$ astfel încât $\forall x\in X,p(x)\neq x$ ${\ displaystyle \ forall x \ în X, p (x) \ neq x}$ $\ forall x \ în X, p (x) \ neq x$ .

Este ușor să verificați dacă nu există nicio dismutație pentru un set de un singur element, există 1 pentru un set de 2 elemente, 2 pentru un set de 3 elemente, 9 pentru un set de 4 elemente ...

De exemplu, cele 9 posibile dismutații ale cuvântului „ABCD” sunt:

 BADC BCDA BDAC 
CADB CDAB CDBA
DABC DCAB DCBA

Numărarea dismutațiilor

Numărul dismutațiilor unui set de n elemente este $\sum _{i=0}^{n}\left(-1\right)^{i}{\frac {n!}{i!}}\sim {\frac {n!}{e}}$ ${\ displaystyle \ sum _ {i = 0} ^ {n} \ left (-1 \ right) ^ {i} {\ frac {n!} {i!}} \ sim {\ frac {n!} {e }}}$ $\ sum _ {{i = 0}} ^ {n} \ left (-1 \ right) ^ {i} {\ frac {n!} {i!}} \ sim {\ frac {n!} {e} }$ .

Demonstrarea acestui fapt este un exemplu de aplicare a principiului incluziunii-excluderii . Având un set $X$ ${\ displaystyle X}$ $X$ din $n$ ${\ displaystyle n}$ $n$ elemente, sunt $P,D\subset P$ ${\ displaystyle P, D \ subset P}$ $P, D \ subset P$ respectiv ansamblul permutațiilor sale și cel al dismutațiilor sale. Este $A_{i}$ ${\ displaystyle A_ {i}}$ $Către}$ setul de permutări care fixează $the$ ${\ displaystyle i}$ $the$ -elea element. Cardinalitatea sa va fi evident $(n-1)!\,$ ${\ displaystyle (n-1)! \,}$ $(n-1)! \,$ , deoarece celelalte elemente se pot deplasa liber.

Pentru a calcula cardinalitatea lui $D=P\setminus \bigcup _{i=1}^{n}A_{i}$ ${\ displaystyle D = P \ setminus \ bigcup _ {i = 1} ^ {n} A_ {i}}$ $D = P \ setminus \ bigcup _ {{i = 1}} ^ {n} A_ {i}$ , am dori să scădem din numărul total de permutări numărul celor care fixează (cel puțin) 1 element. Deci să încercăm $T_{1}=\left|\bigcup _{i=1}^{n}A_{i}\right|$ ${\ displaystyle T_ {1} = \ left | \ bigcup _ {i = 1} ^ {n} A_ {i} \ right |}$ $T_ {1} = \ left | \ bigcup _ {{i = 1}} ^ {n} A_ {i} \ right |$ . Este $S_{1}=\sum _{i=1}^{n}\left|A_{i}\right|$ ${\ displaystyle S_ {1} = \ sum _ {i = 1} ^ {n} \ left | A_ {i} \ right |}$ $S_ {1} = \ sum _ {{i = 1}} ^ {n} \ left | A_ {i} \ right |$ . Observăm că $T_{1}\leq S_{1}\,$ ${\ displaystyle T_ {1} \ leq S_ {1} \,}$ $T_ {1} \ leq S_ {1} \,$ , pentru că în $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ intersecțiile tipului $A_{i}\cap A_{j}\,$ ${\ displaystyle A_ {i} \ cap A_ {j} \,}$ $A_ {i} \ cap A_ {j} \,$ va fi numărat de 2 ori. Mai precis, $S_{1}=T_{1}+T_{2}\,$ ${\ displaystyle S_ {1} = T_ {1} + T_ {2} \,}$ $S_ {1} = T_ {1} + T_ {2} \,$ , unde este $T_{2}=\left|\bigcup _{0\leq k_{1}<k_{2}\leq n}A_{k_{1}}\cap A_{k_{2}}\right|$ ${\ displaystyle T_ {2} = \ left | \ bigcup _ {0 \ leq k_ {1} <k_ {2} \ leq n} A_ {k_ {1}} \ cap A_ {k_ {2}} \ right | }$ $T_ {2} = \ left | \ bigcup _ {{0 \ leq k_ {1} <k_ {2} \ leq n}} A _ {{k_ {1}}} \ cap A _ {{k_ {2} }} \ dreapta |$ .

În general, definit $S_{i}=\sum _{1\leq k_{1}<\cdots <k_{i}\leq n}\left|A_{k_{1}}\cap \cdots \cap A_{k_{i}}\right|$ ${\ displaystyle S_ {i} = \ sum _ {1 \ leq k_ {1} <\ cdots <k_ {i} \ leq n} \ left | A_ {k_ {1}} \ cap \ cdots \ cap A_ {k_ {i}} \ right |}$ $S_ {i} = \ sum _ {{1 \ leq k_ {1} <\ cdots <k_ {i} \ leq n}} \ left | A _ {{k_ {1}}} \ cap \ cdots \ cap A_ {{k_ {i}}} \ right |$ Și $T_{i}=\left|\bigcup _{1\leq k_{1}<\cdots <k_{i}\leq n}A_{k_{1}}\cap \cdots \cap A_{k_{i}}\right|$ ${\ displaystyle T_ {i} = \ left | \ bigcup _ {1 \ leq k_ {1} <\ cdots <k_ {i} \ leq n} A_ {k_ {1}} \ cap \ cdots \ cap A_ {k_ {i}} \ right |}$ $T_ {i} = \ left | \ bigcup _ {{1 \ leq k_ {1} <\ cdots <k_ {i} \ leq n}} A _ {{k_ {1}}} \ cap \ cdots \ cap A_ {{k_ {i}}} \ right |$ , avem asta $S_{i}=T_{i}+T_{i+1}\Rightarrow T_{i}=S_{i}-T_{i+1}\,$ ${\ displaystyle S_ {i} = T_ {i} + T_ {i + 1} \ Rightarrow T_ {i} = S_ {i} -T_ {i + 1} \,}$ $S_ {i} = T_ {i} + T _ {{i + 1}} \ Rightarrow T_ {i} = S_ {i} -T _ {{i + 1}} \,$ .

În special, îl obținem $T_{1}=S_{1}-S_{2}+S_{3}-S_{4}\cdots =\sum _{i=1}^{n}\left(-1\right)^{i+1}S_{i}$ ${\ displaystyle T_ {1} = S_ {1} -S_ {2} + S_ {3} -S_ {4} \ cdots = \ sum _ {i = 1} ^ {n} \ left (-1 \ right) ^ {i + 1} S_ {i}}$ $T_ {1} = S_ {1} -S_ {2} + S_ {3} -S_ {4} \ cdots = \ sum _ {{i = 1}} ^ {n} \ left (-1 \ right) ^ {{i + 1}} S_ {i}$

Calculați cardinalitatea lui $S_{i}$ ${\ displaystyle S_ {i}}$ $Da}$ nu este dificil: modalitățile de alegere $the$ ${\ displaystyle i}$ $the$ elementele (cele care urmează a fi fixate) sunt ${n \choose \ i}$ ${\ displaystyle {n \ choose \ i}}$ ${n \ alege \ i}$ , și pentru fiecare dintre acestea celelalte elemente pot permuta liber , prin urmare în $\left(n-i\right)!\,$ ${\ displaystyle \ left (ni \ right)! \,}$ $\ left (n-i \ right)! \,$ căi. Rezultă că $S_{i}={n \choose \ i}\left(n-i\right)!={\frac {n!}{\left(n-i\right)!i!}}\left(n-i\right)!={\frac {n!}{i!}}$ ${\ displaystyle S_ {i} = {n \ alege \ i} \ left (ni \ right)! = {\ frac {n!} {\ left (ni \ right)! i!}} \ left (ni \ right )! = {\ frac {n!} {i!}}}$ $S_ {i} = {n \ alege \ i} \ left (ni \ right)! = {\ Frac {n!} {\ Left (ni \ right)! I!}} \ Left (ni \ right)! = {\ frac {n!} {i!}}$ .

În acest moment știm că numărul permutațiilor care fixează cel puțin un element este $T_{1}=\sum _{i=1}^{n}\left(-1\right)^{i+1}{\frac {n!}{i!}}$ ${\ displaystyle T_ {1} = \ sum _ {i = 1} ^ {n} \ left (-1 \ right) ^ {i + 1} {\ frac {n!} {i!}}}$ $T_ {1} = \ sum _ {{i = 1}} ^ {n} \ left (-1 \ right) ^ {{i + 1}} {\ frac {n!} {I!}}$ . Deci cei care nu se uită la niciunul sunt $\left|P\right|-T_{1}=n!-\sum _{i=1}^{n}\left(-1\right)^{i+1}{\frac {n!}{i!}}=n!\sum _{i=0}^{n}\left(-1\right)^{i}{\frac {1}{i!}}$ ${\ displaystyle \ left | P \ right | -T_ {1} = n! - \ sum _ {i = 1} ^ {n} \ left (-1 \ right) ^ {i + 1} {\ frac {n !} {i!}} = n! \ sum _ {i = 0} ^ {n} \ left (-1 \ right) ^ {i} {\ frac {1} {i!}}}$ $\ left | P \ right | -T_ {1} = n! - \ sum _ {{i = 1}} ^ {n} \ left (-1 \ right) ^ {{i + 1}} {\ frac { n!} {i!}} = n! \ sum _ {{i = 0}} ^ {n} \ left (-1 \ right) ^ {{i}} {\ frac {1} {i!}}$ .

Această expresie este uneori numită subfactorială a $n$ ${\ displaystyle n}$ $n$ și notat cu $! n$ ${\ displaystyle! n}$ $! n$ .

Comportamentul asimptotic

Să cunoască comportamentul asimptotic al numărului de dismutații ale unui set de $n\,$ ${\ displaystyle n \,}$ $n \,$ elemente (adică cu ce se întâmplă $n\rightarrow +\infty$ ${\ displaystyle n \ rightarrow + \ infty}$ $n \ rightarrow + \ infty$ ) putem observa că $\sum _{i=0}^{+\infty }{\frac {\left(-1\right)^{i}}{i!}}$ ${\ displaystyle \ sum _ {i = 0} ^ {+ \ infty} {\ frac {\ left (-1 \ right) ^ {i}} {i!}}}$ $\ sum _ {{i = 0}} ^ {{+ \ infty}} {\ frac {\ left (-1 \ right) ^ {{i}}} {i!}}$ este propria serie a lui Taylor $e^{x}$ ${\ displaystyle e ^ {x}}$ $și ^ {x}$ calculat în $x=-1$ ${\ displaystyle x = -1}$ $x = -1$ și, prin urmare $n!\sum _{i=0}^{+\infty }{\frac {\left(-1\right)^{i}}{i!}}\sim {\frac {n!}{e}}$ ${\ displaystyle n! \ sum _ {i = 0} ^ {+ \ infty} {\ frac {\ left (-1 \ right) ^ {i}} {i!}} \ sim {\ frac {n!} {Și}}}$ $n! \ sum _ {{i = 0}} ^ {{+ \ infty}} {\ frac {\ left (-1 \ right) ^ {{i}}} {i!}} \ sim {\ frac { nici}}$ (unde simbolul $\sim$ ${\ displaystyle \ sim}$ $\ sim$ înseamnă este asimptotic echivalent cu ).

Un alt mod de a privi acest rezultat este cel dat $n$ ${\ displaystyle n}$ $n$ suficient de mare, probabilitatea ca o permutare aleasă aleatoriu a unui set de $n$ ${\ displaystyle n}$ $n$ elemente atât o dismutație este de aprox ${\frac {\frac {n!}{e}}{n!}}={\frac {1}{e}}\approx 36,8\%$ ${\ displaystyle {\ frac {\ frac {n!} {e}} {n!}} = {\ frac {1} {e}} \ approx 36,8 \%}$ ${\ displaystyle {\ frac {\ frac {n!} {e}} {n!}} = {\ frac {1} {e}} \ approx 36,8 \%}$

Generalizări

Uneori sunt necesare dismutații care, pe lângă faptul că nu acceptă puncte fixe, satisfac restricții suplimentare.

Demutările sunt un exemplu de mare colecție de seturi de permutare restricționate. De exemplu, problema menajelor solicită n cupluri căsătorite, în câte moduri pot fi aranjate la o masă rotundă, astfel încât bărbații și femeile să alterneze și astfel încât nimeni să nu fie lângă soț.

La un nivel mai formal, având în vedere două seturi A și S și având două colecții U și V de surjecții de la A la S , putem întreba numărul de perechi de funcții ( f , g ) cu f în U și g în V , astfel că pentru toate a din A avem f ( a ) ≠ g ( a ); cu alte cuvinte, ne întrebăm când pentru fiecare f și g există o dismutație φ a lui S astfel încât f ( a ) = φ ( g ( a )).

Elemente conexe

linkuri externe

( EN ) Dismutation , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
Secvența OEIS a lui Neil Sloane A000166
Deranjamente și aplicații de Mehdi Hassani
Soluția non-sexistă a problemei menajului de Kenneth P. Bogart, Peter G. Doyle
Derangement in MathWorld de Eric Weisstein

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică