about permutation

**Biscaim** · April 14th 2009, 03:17 PM

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

Thanks in advance.

**ThePerfectHacker** · April 14th 2009, 09:16 PM

Originally Posted by Biscaim

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

Thanks in advance.

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

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

Add them up to get your answer.

**NonCommAlg** · April 14th 2009, 10:11 PM

there's a combinatorial way of looking at this problem: let $I_n=\{\alpha \in S_n: \ \alpha^2=1 \}$ and $a_n=|I_n|.$ now let $\beta \in I_{n+1}$ and $\beta(n+1)=k.$ if $k=n+1,$ then there are $a_n$ possibilities for $\beta.$

if $1 \leq k \leq n,$ then we must have $\beta(k)=n+1,$ because $\beta^2=1.$ so there will be $a_{n-1}$ possibilities for $\beta$ in this case. thus we have this recurrence relation: $a_{n+1}=a_n + na_{n-1}, \ n \geq 2,$

with initial conditions $a_1=1, \ a_2=2.$ there are only non-closed form expressions for $a_n$ and one of them was given by ThePerfectHacker: $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 $\{a_n \}$ see here.

Edit: simplifying ThePerfectHacker's formula gives you this better looking one: $a_n=n! \sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \frac{1}{2^k k! (n-2k)!}.$

Thread: about permutation

LinkBack

Thread Tools

Display

about permutation

Similar Math Help Forum Discussions

Why permutation ?

permutation help

Permutation

Permutation

Permutation.......

Search Tags