# De Montmort's Problem of Coincidence

• Nov 2nd 2007, 03:24 AM
chopet
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:
$\displaystyle 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 $\displaystyle {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 $\displaystyle {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?

$\displaystyle C_{n,m} = \frac{1}{{m!}}\sum\limits_{k = 2}^{n - m} {\frac{{\left( { - 1} \right)^k }}{{k!}}}$.
I know this one: $\displaystyle 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 $\displaystyle C_{n,m}$ will give an incorrect answer if $\displaystyle n - m < 2$.
But if you change the index to begin at 0: $\displaystyle C_{n,m} = \frac{1}{{m!}}\sum\limits_{k = 0}^{n - m} {\frac{{\left( { - 1} \right)^k }}{{k!}}}$ then $\displaystyle C_{4,3} =0$.