Dismutazione (matematica)

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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} \frac{1}{i!} .

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

Comportamento asintotico[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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