Results 1 to 3 of 3

Math Help - Mathematical thinking proof question about derangements

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    3

    Question Mathematical thinking proof question about derangements

    .
    Last edited by zukias; December 10th 2010 at 01:49 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,811
    Thanks
    701
    Hello, zukias!

    \text{]Given }n\text{ distinct objects how many ways is it possible to arrange them}
    \text{so that none is in its original position?}

    \text{Such a rearrangement is called a }derangement.

    \text{It's easy to see that the number of rearrangements of }n\text{ objects is }n!,
    . . \text{but what about the number of derangements?}

    \text{Show that }d(n)\text{ satisfies the recurrence relation:}

    . . d(n) \;=\; (n - 1) \bigg[d(n - 1) + d(n - 2)\bigg],\;\;\text{ for }n \ge 3.

    This is the way it was explained to me . . .


    We have this set of objects: . a\,b\,c\,\hdots\,n . in their original positions.


    For the first position, there are \,n-1 choices for the replacement for \,a.

    Suppose it is \,b. .We have: . b\,\_\,\_\,\hdots\,n

    What is placed in the second space?
    There are two basic choices:
    . . [1] \,a is not placed in the second space.
    . . [2] \,a is placed in the second space.

    [1] Suppose \,a is not in the second space.
    . . .Then we have \,n-1 objects \{a,\,c,\,d,\,\hdots n\} to derange.
    . . .There are: . d(n-1) ways.

    [2] If \,a is in the second space, we have: . b\,a\,\hdots\,n
    . . . \,a and \,b has swapped places; they are already deranged.
    . . .We must derange the other n-2 objects: . d(n-2) ways.

    Hence, if \,b is in the first space,
    . . there are: . d(n-1) + d(n-2) possible derangements.


    Since there are \,n-1 choices for \,b, the number of derangements is:

    . . d(n) \;=\;(n-1)\bigg[d(n-1) + d(n-2)\bigg]


    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Also...

    With Inclusion method you can prove the following:

    \displaystyle d(n)=n![1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...(-1)^n\frac{1}{n!}]=n!\Sigma^{n}_{k=0}\frac{(-1)^k}{k!} \approx \frac{n!}{e} \approx 0.37n!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Thinking: 2 Derangements/proof questions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 11th 2010, 04:48 AM
  2. Thinking question for trig + combining functions
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: January 5th 2010, 12:47 AM
  3. Proof Question: Using Mathematical Induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 19th 2009, 01:47 AM
  4. Best way to develop your mathematical thinking.
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: October 30th 2008, 04:53 PM
  5. Replies: 2
    Last Post: October 2nd 2008, 03:08 AM

Search Tags


/mathhelpforum @mathhelpforum