Results 1 to 4 of 4

Math Help - Proof

  1. #1
    Junior Member
    Joined
    Dec 2006
    Posts
    43

    Proof

    I'm confused about how to approach this problem. If someone could give me a start, I would really appreciate it!

    Suppose n men throw their coats into a closet and later pick them up blindly - one coat per man, uniform probability that any particular coat will go to any particular man.

    Let B_n be the number of ways of permuting n coats so that every coat gets moved (i.e. B_2 = 1 because there is 1 way of switching 2 coats so that each coat gets moved).

    Let C_n be the number of permutations (i.e. C_2 = 2 because there are 2 ways of arranging 2 objects. In general, C_n = n!).

    B_n divided by C_n equals D_n.

    Prove that D_n - D_{n-1} = -1/n (D_{n-1} - D_{n-2}).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1582
    Awards
    1
    Can you possibly clarify the terms such as ‘moves’.
    Are you saying that man gets his own coat?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2006
    Posts
    43
    This is what I mean by "moved." Sorry, I should have stated it more clearly:

    Each man puts his coat in a certain position in the closet. B_n means the number of ways such that each coat gets switched to a different position in the closet (so that when each man returns to the closet to pick up his coat, he winds up with a different one than before because since he is unaware that the coats were moved, he is picking his coat based on where he initially placed it in the closet).

    For example, B_2 = 1 because there is only one way of switching the coats so that each of two men winds up with a different coat than the one he started with. Using the same logic, B_3 = 2.
    Last edited by buckaroobill; December 9th 2007 at 11:47 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1582
    Awards
    1
    I am not sure that I can give you help with the proof of the recursion formula.
    However, I can give you the exact formula for:
    B_n  = \frac{1}{{n!}}\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}

    Those are called derangements or totally active permutations; rearrangements in which no element remains in the original position.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum