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

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

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

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