Dismutazione (matematica)

In combinatoria vengono dette dismutazioni (o sconvolgimenti, o permutazioni complete) le permutazioni di un insieme che non fissano alcun elemento, ossia 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\colon X\to X$ tali che $p(x)\neq x$ per ogni $x\in 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

Il numero di dismutazioni di un insieme di $n$ elementi viene talvolta chiamato subfattoriale di $n$ e denotato con $!n$ .

Contare le dismutazioni

Il numero di dismutazioni di un insieme di $n$ elementi è

\sum _{i=0}^{n}\left(-1\right)^{i}{\frac {n!}{i!}}.

La dimostrazione di questo fatto è un esempio di applicazione del principio di inclusione-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 _{1\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!}}.

Comportamento asintotico

Per conoscere il comportamento asintotico del numero di dismutazioni di un insieme di $n$ elementi (ossia 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 $e^{x}$ calcolata in $x=-1$ , 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$ sufficientemente 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\%.$

Forma ricorsiva

Il numero di dismutazioni di un insieme di $n$ elementi può essere calcolato anche in forma ricorsiva, in particolare vale che:

D_{n}=(n-1)(D_{n-1}+D_{n-2}),

{\begin{cases}D_{1}=0,\\D_{2}=1.\end{cases}}

Questo è dimostrabile osservando che nella prima posizione può essere messa una qualsiasi tra $n-1$ lettere (tutte tranne la A nella tabella riportata), da ora chiameremo questa lettera K. Per proseguire si possono distinguere due casi, se il primo elemento (A nel nostro caso) va a finire nella cella corrispondente a K, posso continuare in un numero di modi pari a $D_{n-2}$ (è uguale al numero di dismutazioni senza considerare la A e la K). Altrimenti, se la A va a finire in una cella diversa da quella corrispondente a k, il numero di modi di continuare è uguale a $D_{n-1}$ , questo perché possiamo considerare le dismutazioni di tutto l'insieme esclusa la A, e metterla nella posizione in cui verrebbe messa K.

A	B	C	D	E	F	G
(n-1)

In numero di dismutazioni di $n$ elementi può essere espresso in forma ricorsiva anche nella maniera seguente:

D_{n}=nD_{n-1}+(-1)^{n}.

La validità di questa relazione è dimostrabile partendo dalla precedente per via induttiva.

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 a 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

Collegamenti esterni

(EN) derangement, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
(EN) Eric W. Weisstein, Derangement, su MathWorld, Wolfram Research.
(EN) Derangement, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
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