Probability of shuffling properly

[Pzi]

Hello.

I don't know whether I'm tired or stupid, but today I cannot comprehend this:

There are N paintings in the house (and exactly N spots to place them). All paintings are then taken and randomly placed again. What is the probability that no painting is in its original location?

There are N! different ways to rearrange them when no restrictions are applied (it's very obvious). I don't know how to proceed.

 

[Ray Vickson]

Hello.

I don't know whether I'm tired or stupid, but today I cannot comprehend this:

There are N paintings in the house (and exactly N spots to place them). All paintings are then taken and randomly placed again. What is the probability that no painting is in its original location?

There are N! different ways to rearrange them when no restrictions are applied (it's very obvious). I don't know how to proceed.

This is the classical "Matching Problem", first solved by Montmort in 1708. The answer is
P\{ \text{no match}\} = 1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \cdots \pm \frac{1}{N!}. Note that these are the first N+1 terms in the expansion of \exp(-1) =<br /> e^{-1}, where e is the base of the natural logarithms: e ≈ 2.71828... . Thus, for moderate to large N, P{no match} ≈ 0.36788. Note that there is about a 37% chance of no match, whether N is 10 or 10 million. (Furthermore, one can show that the exact expected number of matches is 1 for all N, so the expected number of matches is 1 whether N is 10 or 10 million.)

Google 'matching problem+probability' for more details.

RGV