Tricky counting problem(n distinct balls in n distinct boxes)

[chrisandmiss]

Homework Statement

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.

Homework 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))+...

n!/(k!(n-k)!)=C(n,k)

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?

 

[Ray Vickson]

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

RGV