Results 1 to 10 of 10

Math Help - Permutation and fix points

  1. #1
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374

    Permutation and fix points

    A Challenge Problem:
    Let S_n be all the permutations of {1,2,...,n}.
    for any given permutation \sigma, if \sigma(i)=i, we say i is a fix point of \sigma.
    A permutation may have several fix points, let FP(\sigma) be the set of fix points of the permutation \sigma.

    Problem: How many permutations are there whose fix-points set has exactly k elements(points)? k=0,1,...,n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Drexel28, This is a new problem derived from another thread.
    So, enjoy this problem!
    Last edited by Shanks; January 7th 2010 at 05:55 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Shanks View Post
    A Challenge Problem:
    Let S_n be all the permutations of {1,2,...,n}.
    for any given permutation \sigma, if \sigma(i)=i, we say i is a fix point of \sigma.
    A permutation may have several fix points, let FP(\sigma) be the set of fix points of the permutation \sigma.

    Problem: How many permutations are there whose fix-points set has exactly k elements(points)? k=0,1,...,n.
    Solution: Fix the \ell elements of \{1,\cdots,n\} that you want to fix. Then, the number of permutations with those fixed points are precisely the amount of bijective maps one can form from n-\ell points onto itself with f(x)\ne x,\text{ }\forall x. These are the derangements of \left\{1,\cdots,n-\ell\right\}. So, for the fixed \ell elements there are \text{Derange}\left(n-\ell\right) permutations. Thus, the total number of permutations is the number of ways you can pick the \ell elements. Thus, the answer is {n\choose \ell}\text{Derange}\left(n-\ell\right).


    Remark: It can be proven that \text{Derange}\left(k\right) =\text{floor}\left( \frac{k!}{e}+\frac{1}{2}\right)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Where can I get more information about the Derange function?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    You could Google it. Or, I mean there is usually, or at least in a couple of my books, an adequate introduction to the concept of derangements mixed in with S_n in group theory books.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1
    Quote Originally Posted by Shanks View Post
    Where can I get more information about the Derange function?
    Here is the standard way to count derangements.
    \text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}} .

    That is gotten by use of the inclusion/exclusion rule.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Oh, I see.
    There is a problem called " Euler envelope&box problem" in the Set theory.
    They are very similar or exactly the same problem stated in a different way.
    Thank you!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Quote Originally Posted by Plato View Post
    Here is the standard way to count derangements.
    \text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}} .

    That is gotten by use of the inclusion/exclusion rule.
    Another question:
    How to manipulate \text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}
    to

    \text{Derange}(n)=\text{floor}\left( \frac{n!}{e}+\frac{1}{2}\right)?
    Can we prove that they are equal by induction?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Shanks View Post
    Another question:
    How to manipulate \text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}
    to

    \text{Derange}(n)=\text{floor}\left( \frac{n!}{e}+\frac{1}{2}\right)?
    Can we prove that they are equal by induction?
    n!\sum_{k=1}^{n}\frac{(-1)^k}{k!}=n!\left(\sum_{k=1}^{\infty}\frac{(-1)^k}{k!}-\sum_{k=n+1}^{\infty}\frac{(-1)^k}{k!}\right)=\frac{n!}{e}-n!\sum_{k=n+1}^{\infty}\frac{(-1)^k}{k!}. You can take it from there.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Oh, I see. Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: August 24th 2011, 11:35 AM
  2. Replies: 1
    Last Post: February 9th 2011, 10:52 AM
  3. Fixed points in a permutation, mean and variance
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 1st 2010, 07:30 AM
  4. Replies: 5
    Last Post: February 27th 2009, 07:48 PM
  5. Replies: 3
    Last Post: January 11th 2009, 11:49 AM

Search Tags


/mathhelpforum @mathhelpforum