DERANGEMENT - 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:
- Ogni elemento 2 volte: A000459.
$$ \frac{|H_{2n} \cap (1,2)(3,4)...(2n-1,2n)H_{2n}|}{2^n}.$$
(Riscrivibile spezzando tutto in bicicli o cambiando i bicicli).
- Ogni elemento 3 volte: A059073.
$$\frac{|H_{3n} \cap (1,2,3)H_{3n} \cap (1,3,2)H_{3n} \cap (4,5,6)H_{3n} ... \cap (3n-2,3n-1,3n)H_{3n} \cap (3n-2,3n,3n-1)H_{3n}|}{3!^n} =$$
$$ = \frac{|H_{3n} \cap (1,2,3)(4,5,6)...(n-2,n-1,n)H_{3n} \cap (1,3,2)(4,6,5)...(3n-2,3n,3n-1)H_{3n}|}{3!^n}.$$
Notazione generalizzabile a dismutazioni con ripetizione generiche*.
Riscribile in altri modi, ad esempio spezzando in molti più bicicli: $ |H \cap (123)H \cap (132)H | = |H \cap (12)H \cap (13)H \cap (23)H|. $
- Ogni elemento 4 volte:
A059074.
È come un mazzo di carte in cui identifico i semi, quindi la probabilità che giocare* a "Merda" sia noioso è:
$$ \frac {a_{13}}{(52!/(4!)^{13})} \approx 1.6 \%.$$
Conto esatto: WolframAlpha.
Pdf correlato - Molto altro sulle reference di OEIS.
Io mi fermo a 4, ma LUI no.
Comunque intorno a 59070 ci sono molte serie correlate, ad esempio dismutazioni parziali con ripetizioni (esattamente k punti fissi).
Ménage problem: Wikipedia.
- Mia interpretazione: $2*n!*|H \cap (1,2,3...n)H|$.
- Interessante soluzione: NON SESSISTA.
Bella l'interpretazione coi grafi.
Latin rectangle: Wikipedia.
Mi interessa il numero di rettangoli $k*n$ con la priga riga ordinata.
- K=3: A000186
-
K=3 può essere visto come numero coppie di dismutazioni che "dismutano" tra loro: $\sum_{\sigma \in H} |H \cap \sigma H |.$
In generale è il numero di $k$-uple e si può vedere similarmente*.
-
Possibile soluzione per generico $k$: Spiegazione.
Purtroppo poco esplicita e poco utile computazionalmente.
Su questo problema ho un claim per $ n \rightarrow + \infty .$
Se qualcuno ne volesse mai parlare: j.boncompagni@studenti.unipi.it.
Sarei anche contento mi faceste notare errori o ambiguità.
Ciao :)
Jack Boncompagni.