Results 1 to 3 of 3

Math Help - Probability of Derangement

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    10

    Probability of Derangement

    Derangement is a permutation without a fixed point.
    Derangement - Wikipedia, the free encyclopedia
    The probability that n elements are deranged is given by \sum_{k=2}^n \frac{(-1)^k}{k!}. So the probability exhibits the following properties:

    (1) When n increases from an odd number to an even number (say, from 3 to 4), the probability increases. That is, when elements are shuffled, they get more likely to be deranged.
    (2) When n increases from an even number to an odd number (say, from 4 to 5), the probability decreases. That is, when elements are shuffled, they get more unlikely to be deranged.
    (3) When n is restricted to odd numbers, the probability is an increasing function of n.
    (4) When n is restricted to even numbers, the probability is a decreasing function of n.

    I want, if any, "intuitive" explanations of these properties. Whether an explanation is "intuitive" is very subjective, so any ideas are welcome.
    Thank you for viewing this question, and I'm looking forward to your posts.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1

    Re: Probability of Derangement

    Quote Originally Posted by k-misako View Post
    Derangement is a permutation without a fixed point.
    Derangement - Wikipedia, the free encyclopedia
    The probability that n elements are deranged is given by \sum_{k=2}^n \frac{(-1)^k}{k!}. So the probability exhibits the following properties:
    (1) When n increases from an odd number to an even number (say, from 3 to 4), the probability increases. That is, when elements are shuffled, they get more likely to be deranged.
    (2) When n increases from an even number to an odd number (say, from 4 to 5), the probability decreases. That is, when elements are shuffled, they get more unlikely to be deranged.
    (3) When n is restricted to odd numbers, the probability is an increasing function of n.
    (4) When n is restricted to even numbers, the probability is a decreasing function of n.

    I want, if any, "intuitive" explanations of these properties.
    I don't think that there is an "intuitive" explanation. What you have noticed is a result of the sum of an alternating series.
    When n=7 we have six terms of which three are negative and three are positive.
    When n=8 we have seven terms of which three are negative and four are positive.
    So the probability increases.

    It occurs me that a line of an odd number of distinct objects has a middle point. Whereas, an even number does not.

    If you look at the inclusion/exclusion principle of counting from which the derangement sum is derived then I think you will have a better understanding of the sum.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    10

    Re: Probability of Derangement

    > I don't think that there is an "intuitive" explanation.

    I see. Maybe it's a bad habit for me to ask for intuitive explanations so often.

    > It occurs me that a line of an odd number of distinct objects has a middle point. Whereas, an even number does not.

    This might be relevant to that dividing the objects into pairs and then swapping each in the pairs leads automatically to derangement when n is even, but it doesn't when n is odd.

    Thank you very much for your post.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. derangement problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 28th 2013, 05:51 PM
  2. Replies: 5
    Last Post: January 13th 2013, 11:48 AM
  3. Derivation of Derangement formula
    Posted in the Advanced Statistics Forum
    Replies: 9
    Last Post: June 6th 2010, 02:42 PM
  4. derangement question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 8th 2009, 03:18 PM
  5. Derangement Question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 22nd 2009, 10:47 PM

Search Tags


/mathhelpforum @mathhelpforum