Dismutazione (matematica)

Da Wikipedia, l'enciclopedia libera.
Vai a: navigazione, cerca

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

Indice

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

[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{\frac{n!}{e}}{n!} = \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)).

[modifica] Voci correlate

[modifica] Collegamenti esterni


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Strumenti personali
Namespace

Varianti
Azioni
Navigazione
Comunità
Stampa/esporta
Strumenti
Altre lingue