DISMUTAZIONI - DERANGEMENTS


Una dismutazione è una permutazione senza punti fissi: A000166.
Utilizzerò questa pagina per salvare link utili riguardanti dismutazioni e problemi correlati.
Nello specifico mi interessa calcolare quante siano le permutazioni senza "punti in comune" con certe altre permutazioni, o più formalmente:

Sia $D_n$ il sottoinsieme delle dismutazioni del gruppo simmetrico $S_n$, quando non specificato il pedice sarà sottointeso $n$.
Date $\sigma_1, \sigma_2, \ldots, \sigma_k \in S_n$, mi interessa calcolare $|D \cap \sigma_1 D \cap ... \cap \sigma_k D|$.
Questo numero dipende fortemente dalla scelta delle $\sigma_i$, rendendo il problema complicato anche solo con $k=1$.

Nota 1:
Quando scrivo "$\tau$ non ha punti in comune con $\sigma$" intendo che $\forall i \ \tau(i) \neq \sigma(i)$, o meglio due permutazioni tali che scritte in one-line notation una sotto l'altra non hanno numeri in comune in nessuna colonna.
Dunque il mio problema è quante $\tau \in S_n$ non abbiano punti in comune con nessuna $\sigma_i$, nè con l'identità.
Non avere punti in comune con l'identità significa essere una dismutazione.
Chiamo le $\sigma_i$ vincoli.

Bene! Iniziamo a reinterpretare alcuni problemi classici tramite questa prospettiva.


Dismutazioni con ripetizione:
Permutazioni del multiset $\{1^{m_1}, 2^{m_2}, \ldots , k^{m_k} \}$ senza punti fissi, cioè permutazioni della parola $1, \ldots, 1, \ldots,k, \ldots , k$ tali che al posto di $i$ ci sia $j \neq i$, che chiameremo dismutazioni (con ripetizione) di $1^{m_1}2^{m_2} \cdots k^{m_k}$.
Siano $m=(m_1, m_2, \ldots , m_k)$, M=$\sum m_i$ e $A(m)$ il numero di dismutazioni come sopra.

Questo problema si può sempre reinterpretare nella nostra forma, nello specifico rinominando ogni carattere della parola $1^{m_1}2^{m_2} \cdots k^{m_k}$ con i numeri da 1 a M in ordine e aggiungendo vincoli. Ad esempio le dismutazioni di 1112344 sono in bigezione con le $\tau \in S_7$ senza punti in comune con 1234567 (id), 3124567, 2314567, 1234576.
L'aggiungere vincoli si può fare in molti modi diversi, ma se ne può facilmente scegliere uno canonico come nell'esempio, cioè facendo ciclare i numeri sui blocchi originali di numeri uguali. Lascio la formalizzazione di quanto detto al lettore.
Nota: questa scelta si basa solo sul fatto che <$(1,2,...,n)$> < $S_n$ sia un sottogruppo transitivo, secondo me il più naturale da scegliere.

Nota: successivamente vedremo alcuni casi specifici, dove i vincoli saranno messi come appena detto, ma accorpandone alcuni.
Ad esempio le dismutazioni di 112233 sono quelle senza punti in comune con 123456 e 214365. Ho accorpato i vincoli 213456, 124356, 123465 che avrei ottenuto con la suddetta scelta canonica.
Quindi per la Nota 1 sono $|D_6 \ \cap $ (1,2)(3,4)(5,6)$D_6|$.
In qualche senso, i cicli disgiunti nei vincoli sono accorpabili.

Il MacMahon's Master Theorem ci permette di calcolare la funzione generatrice di $A(m)$!!! $$A(x_1,x_2...x_k) = \sum_{m \in \mathbb{N}^k} A(m)x^m = \frac{1}{1-\sum_{i=1}^{k-1}ie_{i+1}(x_1,x_2...,x_k)}.$$ Dove gli $e_i$ sono i polinomi simmetrici elementari, mentre $x^m:= x_1^{m_1}...x_k^{m_k}$.
In realtà ci permette di fare di più e pure di trovare qualche formula in casi specifici.


Vediamo ora alcuni casi specifici: dismutazioni di $1^m2^m\cdots k^m$.

Io mi fermo a $k=4$, ma LUI no.

Comunque su OEIS intorno a 59070 ci sono molte serie correlate, ad esempio dismutazioni parziali con ripetizioni (cioè con esattamente k punti fissi).


Menage problem: Wikipedia.

Latin rectangle: Wikipedia.
Ogni problema del nostro tipo può essere visto così. Ad esempio le dismutazioni di $112233$, che come visto sopra sono $|D_6 \cap (1,2)(3,4)(5,6)D_6|$, le posso vedere come rettangoli latini $3 \times 6$ con prima riga ordinata $123456$, seconda riga $214365$ e terza riga da riempire.

Fissiamo la prima riga ordinata e vediamo alcuni casi specifici di k: Possibile approccio/soluzione per generico $k$: latin.pdf.
Nota: due permutazioni non hanno punti in comune se e solo se $\sigma \in \tau D$. Inoltre essere una dismutazione dipende dalla struttura in cicli, di conseguenza D è chiuso per inverso (e coniugio).

$\star$: Gioco di carte di cui non so il nome vero.
Regole: si divide il mazzo mischiato (52 carte) in maniera equa tra i giocatori, che riporranno il mazzetto coperto davanti a loro.
Il primo giocatore dice "Asso" e scopre rapidamente la prima carta mettendola rapidamente al centro del tavolo, se per caso è effettivamente un asso tutti i giocatori dovranno mettere la mano al centro del tavolo e l'ultimo che la mette dovrà prendere tutte le carte dal centro del tavolo.
Se non è un asso si procede in senso antiorario e il secondo giocatore girerà la prima carta del suo mazzetto dicendo "due" e così via finché non c'è una coincidenza.
Dopo la coincidenza, l'ultimo cha ha appoggiato la mano prenderà le carte dal tavolo e ricomincerà il gioco da primo.
Arrivati a dire "Dieci, Fante, Donna, Re" si riparte con l'asso.
Obiettivo: Vince chi finisce le carte.

Questo gioco è "noioso" se non vi sono mai coincidenze scorrendo l'intero mazzo, sopra ne abbiamo calcolato la probabilità.

Di solito prende tutte le carte dal cento del tavolo anche chi sbaglia a chiamare la carta (es. due al posto di tre, o anche uno al posto di asso) e chi sbaglia a mettere la carta (es. non è il suo turno o doveva mettere la mano o ne ha messe due etc.).
Si può giocare una variante con i Jolly in cui si mette sempre la mano se esce il Jolly.


Jack Boncompagni.