Question

An interesting probability problem:

If there are n different object marked \( 1,2,3⋯n \) are distributed in random in places marked \( 1,2,3⋯n \) then, what is the probability that there is exactly \( r \) matches?

PS:This question was earlier posted in Mathematics group, but I think this better suited here.

Answer 1

I'm bookmarking this to see how James would solve it.

Answer 2

It's the tricky problem of Derangements. Sounds like something from J.J. Rawlings. Almost.

http://math.ucr.edu/home/baez/qg-winter2004/derangement.pdf

Answer 3

For example. With n = 3,

P(all three in place) = P(r=3) = 1/3! = 1/6
This is the arrangement 1-2-3

P(r=2) = 0

P(r=1) = 3/3! = 1/2
1-3-2, 3-2-1, 2-1-3

P(r=0) = 2/3! = 1/3
3-1-2, 2-3-1

Now for the general statement of this ....

Answer 4

First a lemma. A derangement of p items is a permutation where none of the items is fixed. It can be shown that the number of derangements of p elements is
\[ p! \sum_{i=1}^p (-1)^i/i! \]
See the pdf I linked to earlier to figure out the proof yourself, or see the wikipedia article for a proof of this:
http://en.wikipedia.org/wiki/Derangement

Answer 5

This is indeed tricky and derangement is definitely the way to get to the right answer but we need to go a bit farther.

Answer 6

Suppose a permutation \( \pi \in S_n \) that has exactly r fixed points, then we can consider this as a permutation in \( S_{n-r} \) with no fixed points. That is, a derangement. Hence the number of such permutations is the number of fixed points, (n r) = n choose r, and multiply by the number of derangements of n-r elements (from the lemma above), and then divide that by the total number of permutations, n! :
\[ \frac{1}{r!} \sum_{i=0}^{n-r} \frac{(-1)^i}{i!} \]

For example, with n = 3,
P(r=3) = 1/3! . 1 = 1/6
P(r=2) = 1/2! . (1 - 1) = 0
P(r=1) = 1/1! . (1 - 1 + 1/2!) = 1/2
P(r=0) = 1/0! . (1 - 1 + 1/2! - 1/3!) = 1/3

Answer 7

Just to add the problem could be simply solved by the application and knowledge of Rencontres numbers ( http://en.wikipedia.org/wiki/Rencontres_numbers) which is essentially the same concept of counting as described above.

Answer 8

correction: in the lemma above for the number of derangements, the sum should be
i=0 to p, not i=1 to p

Answer 9

Rencontres numbers: \( D(n,k) = \large\frac{n!}{k!} \sum \limits_{i=0}^{n-k} \frac{(-1)^i}{i!} \)

To find the probability just divide the whole thing by \( n! \) the reason for this is a priori, giving the final answer as:

\[ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\large \frac{1}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}\]