How many $\displaystyle \alpha\in S_{n}$ are there with $\displaystyle \alpha^{2}=1$?

2. Originally Posted by Biscaim
How many $\displaystyle \alpha\in S_{n}$ are there with $\displaystyle \alpha^{2}=1$?

First this is true for $\displaystyle \alpha = \text{id}$ so let us forget about this one.
Next, write $\displaystyle \alpha = \sigma_1 ... \sigma_k$ where $\displaystyle \sigma_j$ are disjoint cycles.
We have that the order of $\displaystyle \alpha$ is the lowest common multiple of the lengths of each $\displaystyle \sigma_1,...,\sigma_k$.
Therefore, we require for $\displaystyle \alpha$ to be a product of disjoint 2-cycles.

The # of transpositions is: $\displaystyle {n\choose 2}$
The # of double disjoint transpositions is: $\displaystyle \frac{1}{2!}{n\choose 2}{{n-2}\choose 2}$
The # of triple disjoint transpositiong is: $\displaystyle \frac{1}{3!}{n\choose 2}{{n-2}\choose 2}{{n-4}\choose 2}$.
And so on ...

3. there's a combinatorial way of looking at this problem: let $\displaystyle I_n=\{\alpha \in S_n: \ \alpha^2=1 \}$ and $\displaystyle a_n=|I_n|.$ now let $\displaystyle \beta \in I_{n+1}$ and $\displaystyle \beta(n+1)=k.$ if $\displaystyle k=n+1,$ then there are $\displaystyle a_n$ possibilities for $\displaystyle \beta.$
if $\displaystyle 1 \leq k \leq n,$ then we must have $\displaystyle \beta(k)=n+1,$ because $\displaystyle \beta^2=1.$ so there will be $\displaystyle a_{n-1}$ possibilities for $\displaystyle \beta$ in this case. thus we have this recurrence relation: $\displaystyle a_{n+1}=a_n + na_{n-1}, \ n \geq 2,$
with initial conditions $\displaystyle a_1=1, \ a_2=2.$ there are only non-closed form expressions for $\displaystyle a_n$ and one of them was given by ThePerfectHacker: $\displaystyle a_n=1+\sum_{k \geq 0}\frac{1}{(k+1)!} \prod_{j = 0}^k \binom{n-2j}{2}.$
for more insight about the mysterious sequence $\displaystyle \{a_n \}$ see here.
Edit: simplifying ThePerfectHacker's formula gives you this better looking one: $\displaystyle a_n=n! \sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \frac{1}{2^k k! (n-2k)!}.$