Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Tricky counting problem(n distinct balls in n distinct boxes)

  1. Sep 26, 2011 #1
    1. The problem statement, all variables and given/known data
    There are n distinct balls, and n distinct boxes, and one right order for the boxes to be in. What is the chance that none of the balls are in the correct box.
    And each ball can go into only one box.

    2. Relevant equations
    The chance that none of the boxes are in the correct, is P(none)=1-P(at least one)

    The chance that at least one is in the right box, is A(1)+A(2)+...A(n)-((A(1)and A(2))...+(A(n-1)+A(n))+.....


    3. The attempt at a solution

    The amount of times A(k) is correct is the number of ways to arrange the balls that are not in position k, which is (n-1)!. The amount of times A(1) and A(2) are correct is the amount of times you can arrange all but them, which is (n-2)!

    The number of A(k) is n. The number of A(k) and A(r)(both k and r are in the right box) is the number of ways you can choose 2 out of n

    Continue that line of reasoning. So, the total number of ways at least one ball is in the right box is C(n,1)-C(n,2)(n-2)!+C(n,3)(n-3)!-c(n,4)(n-4)!.... and the chance that happens is that number divided by the total number of arrangements, which is n!

    that cancels out to 1-1/2!+1/3!-1/4!..... one minus that is the number of times that none are in the right box.

    This really breaks my intuition. Is this line of reasoning correct?
    Last edited: Sep 26, 2011
  2. jcsd
  3. Sep 26, 2011 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Your reasoning is OK. For more on this, Google "derangements".

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook