Permutazione composta

[Hawk]

Trovare il numero di permutazione in un insieme di $ n $ elementi tali che: $ \sigma(\sigma(i))=i $.

[simone256]

Se $ n=1 $ allora banalmente l'unica permutazione è quella che porta l'elemento in se stesso, quindi ne abbiamo una.
Ragioniamo così:
$ \sigma(\sigma(i))=i $ solo se all'interno della permutazione il $ k $esimo termine verrà "messo" nel $ j $esimo, e il $ j $esimo verrà messo nel $ k $esimo. Altrimenti $ \sigma(k)=j $ e $ \sigma(j) \neq k $, ma per ipotesi sappiamo che $ \sigma(\sigma(k))=k $.
Quindi gli elementi di $ n $ saranno disposti a coppie nella permutazione, oppure un elemento non verrà permutato (cosa che si verifica sempre per almeno un elemento per esempio se $ n $ è dispari).
Cerchiamo di determinare in quanti modi possiamo scegliere $ k $ coppie in un gruppo di $ 2k $ elementi:
la prima coppia si sceglie in $ \binom{k}{2} $ modi, la seconda in $ \binom{k-2}{2} $ modi... la $ k $esima in in $ \binom{2}{2}=1 $ modo. Ora per ogni gruppo formato da $ k $ coppie abbiamo contato ogni possibile permutazione, quindi dovremo dividere per $ k! $.
Risolvendo e semplificando i binomiali (quanto amo quando si semplificano così ) otteniamo un risultato di $ \displaystyle\frac{(2k)!}{k!(2k)} $.
Tornando al nostro problema:
Per ogni $ n $ abbiamo la permutazione che non cambia l'ordine;
Abbiamo permutazioni che cambiano un numero $ k $ di coppie, ne abbiamo $ \binom{n}{2k} \frac{(2k)!}{k!(2k)} $ poiché dobbiamo scegliere quali elementi permutare e in che modo accoppiarli.
$ 2k $ può variare da $ 2 $ fino al più grande intero minore o uguale a $ n $.
Pertanto:
Per $ n=1 $ il numero delle permutazioni è $ 1 $
Per $ n\ge 2 $ abbiamo un numero di permutazioni uguale a $ \displaystyle 1+\sum_{k=1}^{2k\le n} \binom{n}{2k} \frac{(2k)!}{k!(2k)} $.
Spero funzioni... E in ogni caso mi piacerebbe poter semplificare la sommatoria...

[Hawk]

Non ho controllato i passaggi ma il risultato è: $ \displaystyle\sum_{k=0}^{\left\lfloor \dfrac{n}{2}\right\rfloor} \dbinom{n}{2k}\dfrac{(2k)!}{2^k\cdot k!} $

[simone256]

Risolvendo e semplificando i binomiali (quanto amo quando si semplificano così ) otteniamo un risultato di $ \displaystyle\frac{(2k)!}{k!(2k)} $.

Yeah ... Errore di calcolo
Diciamo che se moltiplichiamo $ 2 $ per se stesso $ k $ volte otteniamo $ 2k $
In ogni caso sostituendo $ 2^k $ a $ 2k $ alla mia soluzione diventa identica alla tua (scritta in modo meno compatto)...
Bene... L'ennesima vaccata di questo genere ormai!

[xXStephXx]

Parrebbe che manco su oeis.org si trova una formula chiusa.

[Gottinger95]

E quante ce ne sono tali che \(\sigma^p(i) = i \), con \(p\) primo?

[simone256]

Due semplici considerazioni:
Poichè p è primo dobbiamo formare "gruppetti" con un numero p di elementi... La dimostrazione è analoga a quella per il problema iniziale. Inoltre la prima parte è identica a quella postata sopra:

Cerchiamo di determinare in quanti modi possiamo scegliere $ k $ coppie in un gruppo di $ 2k $ elementi:
la prima coppia si sceglie in $ \binom{k}{2} $ modi, la seconda in $ \binom{k−2}{2} $ modi... la $ k $esima in in $ \binom{2}{2}=1 $ modo. Ora per ogni gruppo formato da $ k $ coppie abbiamo contato ogni possibile permutazione, quindi dovremo dividere per $ k! $.
Risolvendo e semplificando i binomiali (quanto amo quando si semplificano così ) otteniamo un risultato di $ \frac{(2k)!}{k!2^k} $.

e...

Abbiamo permutazioni che cambiano un numero $ k $ di coppie, ne abbiamo $ \binom{n}{2k} \frac{(2k)!}{k!(2k)} $ poiché dobbiamo scegliere quali elementi permutare e in che modo accoppiarli.

I ragionamenti sono assolutamente analoghi sostituendo ogni $ 2 $ con $ p $ e accorgendoci che svolgendo i calcoli al denominatore avremo un $ \displaystyle p!^k $...
PERO'... (abbiamo sempre un però )
con l'esempio di tre elementi non abbiamo solo la permutazione che manda l'elemento di posto uno al posto due, l'elemento di posto due nel posto tre e l'elemento di posto tre nel posto uno... In questi caso ne abbiamo "ben" $ 2 $!
dobbiamo moltiplicare quindi OGNI GRUPPETTO per $ p! $ ma dividere successivamente per $ p $ per escludere le possibili "rotazioni" (il classico problema delle persone sedute ad una tavola rotonda). Quindi moltiplicare per $ (p-1)!^k $.
Scrivendo per benino:

$ \displaystyle \sum_{k=0}^{\left\lfloor \dfrac{n}{p}\right\rfloor} \dbinom{n}{pk}\dfrac{(pk)!(p-1)!^k}{p!^k\cdot k!} $

Ma svolgendo ci rendiamo conto che otteniamo proprio:

$ \displaystyle \sum_{k=0}^{\left\lfloor \dfrac{n}{p}\right\rfloor} \dbinom{n}{pk}\dfrac{(pk)!}{p^k\cdot k!} $

Che ci ricorda tanto il caso per $ p=2 $

[simone256]

Spero di non aver scritto vaccate...

[<enigma>]

Qui c'è un altro fatto ancora più interessante. Con metodi standard, si trova che il numero $I_n$ di involuzioni di un insieme di $n$ elementi soddisfa
\[ \frac {I_n}{n!} = \frac {e^{-1/4}}{2 \sqrt{\pi n}} n^{-n/2} e^{n/2+\sqrt n} \left ( 1+O (n^{-1/5}) \right ) .\]

[Triarii]

"O" sarebbe? (metodi "standard" ; ok magari saranno standard , ma credo non siano proprio elementari xD)