Results 1 to 3 of 3

Thread: about permutation

  1. #1
    Newbie
    Joined
    Mar 2009
    From
    São Paulo- Brazil
    Posts
    22

    about permutation

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

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Biscaim View Post
    How many $\displaystyle \alpha\in S_{n}$ are there with $\displaystyle \alpha^{2}=1$?

    Thanks in advance.
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    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)!}.$
    Last edited by NonCommAlg; Apr 14th 2009 at 11:11 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Why permutation ?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 11th 2010, 11:27 AM
  2. permutation help
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: Jul 9th 2010, 02:37 PM
  3. Permutation
    Posted in the Statistics Forum
    Replies: 5
    Last Post: Oct 13th 2008, 05:17 PM
  4. Permutation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Aug 7th 2008, 11:01 AM
  5. Permutation.......
    Posted in the Statistics Forum
    Replies: 5
    Last Post: Mar 24th 2008, 03:41 AM

Search Tags


/mathhelpforum @mathhelpforum