Involuzioni

[TomSawyer]

Una permutazione $\sigma$ dell'insieme ${1,...,n}$ è chiamata involuzione se $\sigma \circ \sigma ="l'identità"$. Trovare una forma chiusa, anche sotto forma di somma, per il numero $t_n$ di involuzioni di ${1,...,n}$.

[vl4d]

Ho trovato questa formula:
$\sum_{i=0}^{[n/2]} n_{2i}/(2^i\cdot i!)$

dove indico con $n_k$ le $k$-permutazioni di $n$ elementi.

[TomSawyer]

Se $n_k=((n),(k))*k!$, allora posta pure il procedimento.

[vl4d]

Si consideri una generica $sigma$ come composizione
di trasposizioni. Se le trasposizioni sono disgiunte,
ovvero tutti i cicli di $sigma$ sono dei $2$-cicli,
allora le trasp. commutano, allora $sigma$ e' una involuzione.
Se le trasposizioni non sono tutte disgiunte, ovvero ci sono cicli
con cardinalita' superiore a $2$, allora le trasposizioni non disgiunte
non commutano, segue che $sigma$ non puo' essere una involuzione.
Dunque e' sufficiente contare il numero di permutazioni esprimibili
come trasposizioni disgiunte, ovvero il numero di permutazioni
composte solo da $2$-cicli.

Il numero di $2$-cicli puo' variare da $0$, quando abbiamo solo
punti fissi, a $[n/2]$, quando abbiamo al piu' un punto fisso.
Con $i$ $2$-cicli, permutiamo $2i$ elementi di ${1,\cdots, n}$
in $n_{2i}$ modi. A questo punto, causa commutativita',
non ci interessa ne l'ordine all'interno dei $2$-cicli,
ne l'ordine dei $2$-cicli stessi. Dunque
dividamo per il fattore $2^i\cdot i!$ e abbiamo la sommatoria sopra.

[TomSawyer]

Ok, bella soluzione.