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

Thanks in advance.

Printable View

- Apr 14th 2009, 03:17 PMBiscaimabout permutation
How many $\displaystyle \alpha\in S_{n}$ are there with $\displaystyle \alpha^{2}=1$?

Thanks in advance. - Apr 14th 2009, 09:16 PMThePerfectHacker
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 ...

Add them up to get your answer. - Apr 14th 2009, 10:11 PMNonCommAlg
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)!}.$