De Montmort's Problem of Coincidence

Printable View

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

Please can anyone help.
• Nov 2nd 2007, 08:01 AM
Plato
Frankly, it took me a bit of time to reconcile this formula with the one I know.
$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!}}}$
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 $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$.