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 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(n-1,r-1) + w(n-1,r)*(n-1-r) + w(n-1,r+1)*(r+1).

The first term comes from adding a correct label to a set of n-1 labels with r-1 matched. The second term is from swapping the new label with one of the non-matches from n-1. The last term comes from swapping the new label with one of the previously (in step n-1) matched labels.

Posted by Charlie on 2003-03-24 10:20:32