Dismutazione (matematica)

permutazioni di un insieme che non fissano alcun elemento

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 , le dismutazioni di X sono le funzioni biiettive tali che .

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 dismutazioniModifica

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

La dimostrazione di questo fatto è un esempio di applicazione del principio di inclusione-esclusione. Dato un insieme   di   elementi, siano   rispettivamente l'insieme delle sue permutazioni e quello delle sue dismutazioni. Sia   l'insieme delle permutazioni che fissano l' -esimo elemento. La sua cardinalità sarà evidentemente  , perché gli altri elementi possono muoversi liberamente.

Per calcolare la cardinalità di  , vorremmo sottrarre dal numero totale delle permutazioni il numero di quelle che fissano (almeno) 1 elemento. Cerchiamo quindi  . Sia  . Osserviamo che  , perché in   le intersezioni del tipo   saranno contate 2 volte. Più precisamente,  , dove  .

In generale, definiti   e  , abbiamo che  .

In particolare ne ricaviamo  

Calcolare la cardinalità di   non è difficile: i modi di scegliere   elementi (quelli da fissare) sono  , e per ognuno di questi gli altri elementi possono permutare liberamente, quindi in   modi. Ne segue che  .

A questo punto sappiamo che il numero di permutazioni che fissano almeno un elemento è  . Quindi quelle che non ne fissano nessuno sono  .

Questa espressione viene talvolta chiamata subfattoriale di   e denotata con  .

Comportamento asintoticoModifica

Per conoscere il comportamento asintotico del numero di dismutazioni di un insieme di   elementi (ovvero cosa succede per  ) possiamo notare che   è proprio la serie di Taylor di   calcolata in  , e che quindi   (dove il simbolo   significa è asintoticamente equivalente a).

Un altro modo di vedere questo risultato è che, dato   sufficientemente grande, la probabilità che una permutazione scelta a caso di un insieme di   elementi sia una dismutazione è circa  

GeneralizzazioniModifica

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 correlateModifica

Collegamenti esterniModifica

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