Dismutazione (matematica)

In combinatoria vengono dette dismutazioni (o sconvolgimenti, o permutazioni complete) le permutazioni di un insieme che non fissano alcun elemento, ovvero tali che nessuno degli elementi dell'insieme iniziale compaia 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