Results 1 to 3 of 3

Math Help - Matching Problem

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    9

    Matching Problem

    The Problem " Suppose that each man at a party throws his hat into the center of the room. The hats are first mixed up and then randomly selected. Whats the probability that exactly k of men select their own hats?"

    The final Solution is (1-1+1/2!-1/3!+...+(-1)^n-k/(N-k)!)/k!
    I know that the solution can be found by computing the complement of the probability of none of the men getting the matching hat, but it is not working. Why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Anonymous1's Avatar
    Joined
    Nov 2009
    From
    Big Red, NY
    Posts
    517
    Thanks
    1
    E = event that no matches occurs. Denote P_n = P(E).
    M = event that the first man selects his own hat.

    P_n = P(E) = P(E|M)P(M) + P(E|M^c)P(M^c)

    P(E|M) = 0,
    P(M^{c}) = \frac{n-1}{n},
    P_n = \frac{n-1}{n} P(E|M^c)

    P(E|M^{c}) = \frac{1}{n-1}P_{n-2} + P_{n-1},
    P_n = \frac{n-1}{n} P_{n-1}+\frac{1}{n} P_{n-2}.

    Identify the boundary conditions.
    P_1 = 0, P_2 = 1/2.

    Prove P_n by induction.
    P_n = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - ... + \frac{(-1)^n}{n!}

    Now what is the compliment?
    Last edited by Anonymous1; March 29th 2010 at 12:52 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    The number of ways that none of the n gets his own hat is n!\sum\limits_{j = 0}^n {\frac{{( - 1)^j }}{{j!}}} .
    For exactly k to get his hat, chose k: \binom{n}{k}=\frac{n!}{(k!)(n-k)!}.
    Multiply that by  (n-k)!\sum\limits_{j = 0}^{n-k} {\frac{{( - 1)^j }}{{j!}}}
    To get the probability divide by n!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: August 27th 2011, 08:26 AM
  2. Stable Matching
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2010, 04:26 PM
  3. Local max/ min matching definition? problem
    Posted in the Calculus Forum
    Replies: 0
    Last Post: August 2nd 2010, 04:52 PM
  4. Pattern matching?
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: June 22nd 2008, 10:02 PM
  5. Matching problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 11th 2006, 07:35 AM

Search Tags


/mathhelpforum @mathhelpforum