1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability of shuffling properly

  1. Apr 11, 2012 #1

    Pzi

    User Avatar

    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.
     
  2. jcsd
  3. Apr 11, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    This is the classical "Matching Problem", first solved by Montmort in 1708. The answer is
    [tex]P\{ \text{no match}\} = 1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \cdots \pm \frac{1}{N!}.[/tex] Note that these are the first N+1 terms in the expansion of [itex]\exp(-1) =
    e^{-1},[/itex] 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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook