Dismutazione (matematica)

In combinatoria vengono dette dismutazioni (o sconvolgimenti, o permutazioni complete) le permutazioni di un insieme che non fissano alcun elemento, ovvero nessuno degli elementi dell'insieme iniziale compare nella sua posizione originaria.

Formalmente, se le permutazioni di un insieme X sono le funzioni biiettive $p:X \rightarrow X$, le dismutazioni di X sono le funzioni biiettive $p:X \rightarrow X$ tali che $\forall x \in X, p(x)\neq x$.

Si verifica facilmente che non esiste alcuna dismutazione per un insieme di un solo elemento, ne esiste 1 per un insieme di 2 elementi, 2 per un insieme di 3 elementi, 9 per uno di 4 elementi...

Ad esempio, le 9 dismutazioni possibili della parola "ABCD" sono:

BADC BCDA BDAC 
CADB CDAB CDBA
DABC DCAB DCBA

Contare le dismutazioni

Il numero di dismutazioni di un insieme di n elementi è $\sum_{i=0}^n \left (-1 \right)^i \frac{n!}{i!} \sim \frac{n!}{e}$.

La dimostrazione di questo fatto è un esempio di applicazione del principio di inclusione ed esclusione. Dato un insieme $X$ di $n$ elementi, siano $P, D \subset P \,$ rispettivamente l'insieme delle sue permutazioni e quello delle sue dismutazioni. Sia $A_i \,$ l'insieme delle permutazioni che fissano l'$i \,$-esimo elemento. La sua cardinalità sarà evidentemente $(n-1)! \,$, perché gli altri elementi possono muoversi liberamente.

Per calcolare la cardinalità di $D=P \setminus \bigcup_{i=1}^n A_i \,$, vorremmo sottrarre dal numero totale delle permutazioni il numero di quelle che fissano (almeno) 1 elemento. Cerchiamo quindi $T_1=\left |\bigcup_{i=1}^n A_i \right |$. Sia $S_1 = \sum_{i=1}^n \left | A_i \right |$. Osserviamo che $T_1 \leq S_1 \,$, perché in $S_1$ le intersezioni del tipo $A_i \cap A_j \,$ saranno contate 2 volte. Più precisamente, $S_1 = T_1 + T_2 \,$, dove $T_2 = \left | \bigcup_{0 \leq k_1 < k_2 \leq n} A_{k_1} \cap A_{k_2} \right |$.

In generale, definiti $S_i = \sum_{1 \leq k_1 < \cdots < k_i \leq n} \left | A_{k_1} \cap \cdots \cap A_{k_i} \right |$ e $T_i = \left | \bigcup_{1 \leq k_1 < \cdots < k_i \leq n} A_{k_1} \cap \cdots \cap A_{k_i} \right |$, abbiamo che $S_i = T_i + T_{i+1} \Rightarrow T_i = S_i - T_{i+1} \,$.

In particolare ne ricaviamo $T_1 = S_1 - S_2 + S_3 - S_4 \cdots = \sum_{i=1}^n \left ( -1 \right )^{i+1} S_i$

Calcolare la cardinalità di $S_i$ non è difficile: i modi di scegliere $i$ elementi (quelli da fissare) sono ${n \choose \ i}$, e per ognuno di questi gli altri elementi possono permutare liberamente, quindi in $\left ( n-i \right ) ! \,$ modi. Ne segue che $S_i = {n \choose \ i} \left(n-i \right )! = \frac{n!}{\left (n-i \right)! i!} \left( n-i \right)!= \frac{n!}{i!}$.

A questo punto sappiamo che il numero di permutazioni che fissano almeno un elemento è $T_1 = \sum_{i=1}^n \left ( -1 \right )^{i+1} \frac{n!}{i!}$. Quindi quelle che non ne fissano nessuno sono $\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+1} \frac{1}{i!}$.

Questa espressione viene talvolta chiamata subfattoriale di $n$ e denotata con $!n$.

Comportamento asintotico

Per conoscere il comportamento asintotico del numero di dismutazioni di un insieme di $n \,$ elementi (ovvero cosa succede per $n \rightarrow +\infty \,$) possiamo notare che $\sum_{i=0}^{+ \infty} \frac{\left (-1 \right)^ { i }}{i!}$ è proprio la serie di Taylor di $\frac{1}{e} \,$, e che quindi $n! \sum_{i=0}^{+ \infty} \frac{ \left (-1 \right)^ { i } }{i!} \sim \frac{n!}{e}$ (dove il simbolo $\sim$ significa è asintoticamente equivalente a).

Un altro modo di vedere questo risultato è che, dato $n$ sufficiente grande, la probabilità che una permutazione scelta a caso di un insieme di $n$ elementi sia una dismutazione è circa $\frac{\frac{n!}{e}}{n!} = \frac{1}{e} \approx 36,8%$

Generalizzazioni

Talora servono dismutazioni che, oltre a non ammettere punti fissi, soddisfano restrizioni ulteriori.

Le dismutazioni costituiscono un esempio della ampia collezione degli insiemi di permutazioni soggette a vincoli. Ad esempio il problema dei ménages chiede per n coppie di coniugi, in quanti modi possono essere sistemati ad un tavolo rotondo in modo che si alternino uomini e donne e in modo che nessuno si trovi di fianco al coniuge.

Su un piano più formale, dati due insiemi A ed S e date due collezioni U e V di suriezioni da A in S, ci si può chiedere il numero delle coppie di funzioni (f,g) con f in U e g in V, tali che per tutti gli a in A si abbia f(a) ≠ g(a); in altre parole ci si chiede quando per ogni f e g esiste una dismutazione φ di S tale che f(a) = φ(g(a)).

Voci correlate

• Combinatoria
• Combinazione
• Permutazione

Collegamenti esterni

• Sequenza A000166 della OEIS di Neil Sloane
• Derangements and applications di Mehdi Hassani
• Non-sexist solution of the ménage problem di Kenneth P. Bogart, Peter G. Doyle
• Derangement in MathWorld di Eric Weisstein

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica