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 ${\displaystyle X}$ sono le funzioni biiettive ${\displaystyle p:X\rightarrow X}$, le dismutazioni di ${\displaystyle X}$ sono le funzioni biiettive ${\displaystyle p\colon X\to X}$ tali che ${\displaystyle p(x)\neq x}$ per ogni ${\displaystyle 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 ${\displaystyle n}$ elementi viene talvolta chiamato subfattoriale di ${\displaystyle n}$ e denotato con ${\displaystyle !n}$.

Il numero di dismutazioni di un insieme di ${\displaystyle n}$ elementi è

${\displaystyle \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 ${\displaystyle X}$ di ${\displaystyle n}$ elementi, siano ${\displaystyle P,D\subset P}$ rispettivamente l'insieme delle sue permutazioni e quello delle sue dismutazioni. Sia ${\displaystyle A_{i}}$ l'insieme delle permutazioni che fissano l'${\displaystyle i}$-esimo elemento. La sua cardinalità sarà evidentemente ${\displaystyle (n-1)!,}$ perché gli altri elementi possono muoversi liberamente.

Per calcolare la cardinalità di ${\displaystyle 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 ${\displaystyle T_{1}=\left|\bigcup _{i=1}^{n}A_{i}\right|}$. Sia ${\displaystyle S_{1}=\sum _{i=1}^{n}\left|A_{i}\right|}$. Osserviamo che ${\displaystyle T_{1}\leq S_{1},}$ perché in ${\displaystyle S_{1}}$ le intersezioni del tipo ${\displaystyle A_{i}\cap A_{j}}$ saranno contate 2 volte. Più precisamente, ${\displaystyle S_{1}=T_{1}+T_{2},}$ dove

${\displaystyle T_{2}=\left|\bigcup _{1\leq k_{1}<k_{2}\leq n}A_{k_{1}}\cap A_{k_{2}}\right|.}$

In generale, definiti

${\displaystyle S_{i}=\sum _{1\leq k_{1}<\cdots <k_{i}\leq n}\left|A_{k_{1}}\cap \cdots \cap A_{k_{i}}\right|}$

e

${\displaystyle 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

${\displaystyle S_{i}=T_{i}+T_{i+1}\Rightarrow T_{i}=S_{i}-T_{i+1}.}$

In particolare ne ricaviamo

${\displaystyle 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 ${\displaystyle S_{i}}$ non è difficile: i modi di scegliere ${\displaystyle i}$ elementi (quelli da fissare) sono ${\displaystyle {n \choose i}}$, e per ognuno di questi gli altri elementi possono permutare liberamente, quindi in ${\displaystyle \left(n-i\right)!}$ modi. Ne segue che

${\displaystyle 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 è ${\displaystyle T_{1}=\sum _{i=1}^{n}\left(-1\right)^{i+1}{\frac {n!}{i!}}}$. Quindi quelle che non ne fissano nessuno sono

${\displaystyle \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!}}.}$

Per conoscere il comportamento asintotico del numero di dismutazioni di un insieme di ${\displaystyle n}$ elementi (ossia cosa succede per ${\displaystyle n\rightarrow +\infty }$) possiamo notare che ${\displaystyle \sum _{i=0}^{+\infty }{\frac {\left(-1\right)^{i}}{i!}}}$ è proprio la serie di Taylor di ${\displaystyle e^{x}}$ calcolata in ${\displaystyle x=-1}$, e che quindi

${\displaystyle n!\sum _{i=0}^{+\infty }{\frac {\left(-1\right)^{i}}{i!}}\sim {\frac {n!}{e}},}$

dove il simbolo ${\displaystyle \sim }$ significa "è asintoticamente equivalente a".

Un altro modo di vedere questo risultato è che, dato ${\displaystyle n}$ sufficientemente grande, la probabilità che una permutazione scelta a caso di un insieme di ${\displaystyle n}$ elementi sia una dismutazione è circa ${\displaystyle {\frac {\frac {n!}{e}}{n!}}={\frac {1}{e}}\approx 36,8\%.}$

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

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

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

Questo è dimostrabile osservando che nella prima posizione può essere messa una qualsiasi tra ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.

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

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

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

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 ${\displaystyle 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)).

• Combinatoria
• Combinazione
• Permutazione

• (EN) derangement, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Dismutazione, su MathWorld, Wolfram Research.
• 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

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

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