Results 1 to 5 of 5

Math Help - Combinatorial proof of derangement identity

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    Combinatorial proof of derangement identity

    Could someone check out this combinatorial proof? Thanks.

    Let D_{n} be the number of derangements of an n-set. Define D_{0}=1 and note  D_{1}=0.

    a) Give a combinatorial proof: D_{n}=(n-1)(D_{n-1}+D_{n-2}) for n\geq2.

    How many derangements of an n-set are there?

    One way to count would be D_{n}=n!\sum_{j=0}^{n}\frac{(-1)^{j}}{j!}.

    Another way is to consider the n-set by separating out the n-1 numbers greater than 1, one at a time.

    Start with 2. There are D_{n-1} derangements of the n-1 numbers in the n-set excluding the number 2. If we pre-pend the number 2 to the beginning of these derangements, we will still get D_{n-1} derangements because the 2 in the first position will not cause any of the numbers to be “fixed”. Now consider the next number in the n-set, 3. We can proceed the same as we did with the number 2 and there will again be D_{n-1} derangements with the number 3 pre-pended to the derangement. In fact, there will be n-1 such derangements. But notice that none of these derangements will have 1 in the second position of the sequence after the numbers have been pre-pended. That is because after we remove the number from the n-set and take the derangement of the n-1 numbers left, 1 can never be in the first position of that derangement. So, if we now go through the same steps again by removing 1 along with n-1 numbers, we can then take the derangements of the n-2 numbers left. Start with 21 and pre-pend 21 to the derangements of the n-2 numbers left just as we did with the single numbers. Each of these derangements will have D_{n-2} derangements and there will be n-1 of these derangements. When we add the second group of derangements to the first group of derangements it is clear that we now have all the derangements of [n]. Therefore we have proved that D_{n}=(n-1)(D_{n-1}+D_{n-2}) for n\geq2.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Another way to approach could be

    Ignore the last (nth) element.
    The remaining (n-1) elements can be de-arranged in D(n-1) ways, once you do that the nth element can interchange place with any of the (n-1) element to give you a de-arrangement of n elements.
    Also, out of the (n-1) element we can have an element which holds its poisition, say element 'i'. Other element (remaining (n-2) elements) can be de-arranged in D(n-2) ways. Once this is done to get de-arrangement of 'n' elements you just interchange positions of ith and nth element. Now, i can take values from 1 to (n-1).



    You can see immdiately that no more than 1 of the (n-1) elementss can hold its position. So above two exhaust all the cases for D(n). Hence

    D(n) = (n-1).D(n-1) + (n-1)D(n-2)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Thank you so much for your advice. I really just learned combinatorial proofs in the last month, so I am very encouraged that my proof is not wrong. I have a long way to go to make them concise and totally solid, but this is very encouraging.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    I actually haven't checked your proof please. Actually couldn't really follow you line of argument but it seems wrong to me.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by oldguynewstudent View Post
    Could someone check out this combinatorial proof? Thanks.

    Let D_{n} be the number of derangements of an n-set. Define D_{0}=1 and note  D_{1}=0.

    a) Give a combinatorial proof: D_{n}=(n-1)(D_{n-1}+D_{n-2}) for n\geq2.

    How many derangements of an n-set are there?

    One way to count would be D_{n}=n!\sum_{j=0}^{n}\frac{(-1)^{j}}{j!}.

    Another way is to consider the n-set by separating out the n-1 numbers greater than 1, one at a time.

    Start with 2. There are D_{n-1} derangements of the n-1 numbers in the n-set excluding the number 2. If we pre-pend the number 2 to the beginning of these derangements, we will still get D_{n-1} derangements because the 2 in the first position will not cause any of the numbers to be “fixed”. Now consider the next number in the n-set, 3. We can proceed the same as we did with the number 2 and there will again be D_{n-1} derangements with the number 3 pre-pended to the derangement. In fact, there will be n-1 such derangements. But notice that none of these derangements will have 1 in the second position of the sequence after the numbers have been pre-pended. That is because after we remove the number from the n-set and take the derangement of the n-1 numbers left, 1 can never be in the first position of that derangement. So, if we now go through the same steps again by removing 1 along with n-1 numbers, we can then take the derangements of the n-2 numbers left. Start with 21 and pre-pend 21 to the derangements of the n-2 numbers left just as we did with the single numbers. Each of these derangements will have D_{n-2} derangements and there will be n-1 of these derangements. When we add the second group of derangements to the first group of derangements it is clear that we now have all the derangements of [n]. Therefore we have proved that D_{n}=(n-1)(D_{n-1}+D_{n-2}) for n\geq2.
    Looks fine to me!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove the identity using a combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2011, 07:51 PM
  2. Combinatorial proof for an identity
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: April 23rd 2011, 05:12 PM
  3. combinatorial identity problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 23rd 2010, 11:46 PM
  4. interesting combinatorial identity proof
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: November 29th 2009, 05:34 PM
  5. Combinatorial proof of a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 12th 2008, 03:42 PM

Search Tags


/mathhelpforum @mathhelpforum