There are 9 jars each with unique labels.
Someone has come and removed all the labels and mixed them up.
If you put the labels back on the jars (without knowing the contents), what is the expected number of labels which would match the contents?
(In reply to
re(2): SOLUTION IS WRONG by Cory Taylor)
In fact, it's about 37% likely that there will be one correctly matched label. Out of the 9!=362880 permutations of the nine labels, the following are the number of ways of getting 0 through 9 correct, respectively:
133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0, 1.
When divided by 9! they give respective probabilities of:
.367879, .367882, .183929, .061343, .015278, .003125, .000463, .000099, .000000, .000003. Using these probabilities to weight the numbers from 0 through 9 does indeed give an average of 1. Note that as the number of labels increases, this distribution gets closer to the Poisson distr with mean 1.
The derivation of the number of ways of getting r correct out of n labels, is to start with n=1, r=1 and w(1,1) = 1 and w(1,x)=0 for all x other than 1.
From there, w(n,r)= w(n1,r1) + w(n1,r)*(n1r) + w(n1,r+1)*(r+1).
The first term comes from adding a correct label to a set of n1 labels with r1 matched. The second term is from swapping the new label with one of the nonmatches from n1. The last term comes from swapping the new label with one of the previously (in step n1) matched labels.

Posted by Charlie
on 20030324 10:20:32 