Dismutazione (matematica)

Da Wikipedia, l'enciclopedia libera.

In combinatoria vengono dette dismutazioni (o sconvolgimenti, o permutazioni complete, in inglese derangements) le permutazioni di un insieme che non fissano alcun elemento. 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

[modifica] Contare le dismutazioni

Il numero di dismutazioni di un insieme di n elementi è $\sum_{i=0}^n \left (-1 \right)^ { i+1 } \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 $T1 \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$ .

[modifica] 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{n!}{\frac{n!}{e}} = \frac{1}{e} \approx 36,8%$

[modifica] 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)).