Results 1 to 2 of 2

Thread: De Montmort's Problem of Coincidence

  1. #1
    Oct 2007

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Aug 2006
    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$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Coincidence... I think not?!
    Posted in the Calculus Forum
    Replies: 5
    Last Post: Feb 13th 2010, 05:15 AM
  2. Birthday Coincidence Probability (w/ leap years)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Aug 8th 2008, 03:16 AM
  3. Coincidence or not?
    Posted in the Statistics Forum
    Replies: 5
    Last Post: Jun 11th 2008, 04:05 AM

Search Tags

/mathhelpforum @mathhelpforum