# Thread: De Montmort's Problem of Coincidence

1. ## De Montmort's Problem of Coincidence

If n objects labelled 1 to n are randomly placed in a row, what is the probability that exactly m of the objects will be correctly placed?

The equation is given below:
$c_{m,n} = {1 \over {m!}}[ {1 \over{2!}} - {1 \over{3!}} + {1 \over{4!}} .... +{ (-1)^{n-m} \over {n-m!}}]$

First, let's look at the case n=4 and m=4.
The equation correctly gives ${1 \over {4!}}$
Having all of the objects in their correct place is only 1 way out of 4! ways to arrange the 4 objects.

Can anyone explain to me the case when m=3 and n=4?
By right, it should return also ${1 \over {4!}}$, as if 3 out of 4 objects werein their correct place, then surely the last object must be in its place too.
But how does the formula make me see this?

$C_{n,m} = \frac{1}{{m!}}\sum\limits_{k = 2}^{n - m} {\frac{{\left( { - 1} \right)^k }}{{k!}}}$.
I know this one: $E(n,m) = \frac{{D(n - m)}}{{\left( {n - m} \right)!(m!)}},\mbox{ where } D(n) = n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}$
Now your given $C_{n,m}$ will give an incorrect answer if $n - m < 2$.
But if you change the index to begin at 0: $C_{n,m} = \frac{1}{{m!}}\sum\limits_{k = 0}^{n - m} {\frac{{\left( { - 1} \right)^k }}{{k!}}}$ then $C_{4,3} =0$.