Results 1 to 2 of 2

Math Help - De Montmort's Problem of Coincidence

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    145

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

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    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.
    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: February 13th 2010, 05:15 AM
  2. Birthday Coincidence Probability (w/ leap years)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 8th 2008, 03:16 AM
  3. Coincidence or not?
    Posted in the Statistics Forum
    Replies: 5
    Last Post: June 11th 2008, 04:05 AM

Search Tags


/mathhelpforum @mathhelpforum