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:
$\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?

Please can anyone help.

2. Frankly, it took me a bit of time to reconcile this formula with the one I know.
$\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!}}}$
D(n) is the number of derangements of a string of n objects.
That is, a rearrangement in which none of the n is in its correct place.

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$.