Results 1 to 3 of 3

Math Help - about permutation

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

    about permutation

    How many \alpha\in S_{n} are there with \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 \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.
    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 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)!}.
    Last edited by NonCommAlg; April 15th 2009 at 12:11 AM.
    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: July 11th 2010, 12:27 PM
  2. permutation help
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: July 9th 2010, 03:37 PM
  3. Permutation
    Posted in the Statistics Forum
    Replies: 5
    Last Post: October 13th 2008, 06:17 PM
  4. Permutation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 7th 2008, 12:01 PM
  5. Permutation.......
    Posted in the Statistics Forum
    Replies: 5
    Last Post: March 24th 2008, 04:41 AM

Search Tags


/mathhelpforum @mathhelpforum