DERANGEMENTS - DISMUTAZIONI

Definizione: Permutazioni senza punti fissi A000166.

Chiamerò $H_n$ il sottoinsieme delle dismutazioni del gruppo simmetrico $S_n$.
Quando non specificato il pedice è sottointeso $n$.
Reinterpreterò alcuni problemi nell'ottica di intersezioni tra $H$ e suoi traslati, o meglio $|H \cap \sigma H|$ con $\sigma\in S_n$ che agisce canonicamente sul sottoinsieme $H$.


Dismutazioni con ripetizione: Io mi fermo a 4, ma LUI no.

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


Ménage problem: Wikipedia.

Latin rectangle: Wikipedia.
Mi interessa il numero di rettangoli $k*n$ con la priga riga ordinata. Su questo problema ho un claim per $ n \rightarrow + \infty .$
Se qualcuno ne volesse mai parlare: j.boncompagni@studenti.unipi.it.

Scrivetemi anche per eventuali errori o ambiguità.
Ciao :)


$\star$: Non ricordo il nome del gioco e non l'ho trovato online.
Regole: si divide il mazzo mischiato (52 carte) in maniera equa tra i giocatori, che riporranno il mazzetto coperto davanti a loro.
Vince chi finisce le carte.
Il primo giocatore dice "Asso" e scopre 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 ricomincia da asso il giocare che ha preso.
Arrivati a dire "Dieci, Fante, Donna, Re" si riparte con l'asso.

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

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.


$\star \star$
Definizione: Date n permutazioni diremo che "dismutano" se applicate alla stessa stringa non hanno punti in comune.
Date $\sigma, \tau \in S_n$: $$ \sigma , \tau \ \text{dismutano} \Leftrightarrow \sigma \in \tau H_n.$$ Dim:
$\exists \alpha \in S_n \ t.c. \ \sigma = \alpha \tau$.
Chiamiamo "s" la stringa su cui agiscono entrambe.
$\tau s = s'$ non deve avere punti in comune con $\sigma s = \alpha (\tau s) = \alpha s' \Leftrightarrow \alpha \in H_n$ (per definizione).
$\alpha = \sigma \tau^{-1}$ allora:
$\sigma , \tau \ \text{dismutano} \Leftrightarrow \sigma \tau^{-1} \in H_n \Leftrightarrow \sigma \in H_n \tau = \tau H_n. \ \square$

Per l'ultima ugualiza vedi nota.

Possiamo vedere i rettangoli latini 3*n con la prima riga ordinata come coppie di dismutazioni che dismutano, nel senso che la seconda e la terza riga per non avere punti in comune con la prima saranno dimutazioni (applicate a 1...n) e per non averli tra loro dovranno dismutare (da definizione).
Quindi: $$ a_n = |\{(\sigma , \tau) \in H_n^2 \ | \ \sigma, \tau \ \text{dismutano} \}| = |\{(\sigma , \tau) \in H_n^2 \ | \ \sigma\tau^{-1} \in H_n \}| = |\{(\sigma , \tau) \in H_n^2 \ | \ \sigma\tau \in H_n \}|.$$ Nell'ultima ugualianza rinomino $\tau^{-1}$ in $\tau$, perchè continua a essere una generica dimutazione.
Nota: H è chiuso per inverso, perché l'inverso ha la stessa forma in cicli (che definisce H).

Inoltre il numero di coppie di dismutazioni che dismutano si può contare anche diversamente: sommo per ogni $\sigma \in H_n$ quante $\tau \in H_n$ dismutano con $\sigma$. $$ a_n = \sum_{\sigma \in H} |H \cap \sigma H |.$$


Jack Boncompagni.