Results 1 to 10 of 10

Math Help - Derivation of Derangement formula

  1. #1
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28

    Derivation of Derangement formula

    This question comes from my unsuccessful attempt to solve
    http://www.mathhelpforum.com/math-he...-problems.html

    (Reason im posting a new thread: dont want to hijack the other one with my own questions).


    The question was:
    "there are n letters and n addressed envelopes. Letters are placed randomly in envelopes. find the probability that at least 1 letter goes in the correct envelope"



    The correct answer is

    Quote Originally Posted by Plato View Post
    The number of derangements on n items is D_n  = n!  \cdot \sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}   \approx \frac{{n!}}{e}.
    The probability that at least one term of a permutation remained fixed is 1 - \frac{{D_n }}{{n!}} \approx \frac{{e - 1}}{e} =  {0.63212}.

    But i thought it was

    Quote Originally Posted by SpringFan25 View Post
    you can do this with a tree diagram, where each branch has 2 possible outcome (correct, not correct).
    I wouldn't try and draw the whole thing, but its good to ahve in the back of your head.

    Step 1:
    Find the probability that no paycheck is in the correct envelope:

    P(0) =  \frac{n-1}{n} \times \frac{n-2}{n-3} \times ....  \frac{1}{2}

    = \frac{(n-1)(n-2)....2}{n (n-1) (n-2)....2 \times 1}

    =\frac{1}{n}

    Step 2:
    P(at least 1) = 1-P(0)
    =\frac{n-1}{n}


    Check for n=3:
    \frac{3-1}{3} = \frac{2}{3}, which you said was correct


    So, i have 2 questions:
    1) What's the conceptual mistake in my approach

    2) Is there a derivation of the subfactorial function somewhere?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    I'll try to explain with an example.

    Your reasoning was that you first calculate the probability that the first letter doesn't go in its proper envelope (probability of (n-1)/n)).
    Then, same probability for the second, etc...

    But now consider this situation : you put the first letter in the envelope that is supposed to contain the second letter. Then the probability of putting the second letter in a wrong envelope is 1, because its 'correct' envelope is already taken !

    And you have this situation every time you have to put a letter in an envelope... this is why you have to use derangements
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,643
    Thanks
    1594
    Awards
    1
    Quote Originally Posted by SpringFan25 View Post
    1) What's the conceptual mistake in my approach

    2) Is there a derivation of the subfactorial function somewhere?
    Did you read the webpage that I posted?

    Do you understand the inclusion/exclusion rule?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by SpringFan25 View Post
    This question comes from my unsuccessful attempt to solve
    http://www.mathhelpforum.com/math-he...-problems.html

    (Reason im posting a new thread: dont want to hijack the other one with my own questions).


    The question was:
    "there are n letters and n addressed envelopes. Letters are placed randomly in envelopes. find the probability that at least 1 letter goes in the correct envelope"



    The correct answer is




    But i thought it was





    So, i have 2 questions:
    1) What's the conceptual mistake in my approach ?
    Hi SpringFan25,

    also consider that....
    at the beginning, there are n-1 ways to put a wrong paycheck in envelope number 1.
    However, there will not always be n-2 choices for the 2nd, n-3 for the 3rd etc.

    In the case of 4 envelopes,
    if we place P3 in E1 followed by P1 in E2, then we only can place P4 in E3 and P2 in E4 to have all paychecks in incorrect envelopes.

    However, if we place P3 in E1 and P4 in E2, then we can have P2 in E3 and P1 in E4 or P1 in E3 and P2 in E4.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    Moo/AM,

    thanks, that takes care of question 1


    Plato
    i did read the page and i dont understand that rule
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    ok, now i understand the inclusion/exclusion rule (barely).

    I'll see if i can apply it to this problem


    cya in 15 years
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    This is going to get messy because they dont actually teach set theory to economists ^^.


    I proved the inclusion/exclusion rule but i haven't been able to apply it to this problem.

    I started thinking on these lines:

    Problem: n tokens, n boxes, find number of combinations where no token is in the right box

    Define S_i as the set of combinations where token i is not in the correct box

    Define T_i as the set of combinations where i tokens are not in the correct box. (this is just a shorthand, any set T can be constructed from operations with S).

    I tried to apply the inclusion/exclusion rule as follows:

    D(n) = |T_n| = |S_1 \cap S_2 \cap S_3 ..... \cap S_n|

    = |S_1| +  |S_2| + |S_3| + ...
    -1 * |T_2|
    +1 *|T_3|

    ..etc


    However, i was not able to find
     |S_1| +  |S_2| + |S_3| .....


    edit incorrect reasoning fixed
    Trying to find |S_1| i thought:
    "token 1 in the wrong place, all other tokens in the right place"

    |S_1| = (ways of having n-1 tokens in the right place) * (ways of having token 1 in the wrong place if the others are correct)
    =0
    !!




    Am i going in the wrong direction?
    Last edited by SpringFan25; June 6th 2010 at 01:30 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,643
    Thanks
    1594
    Awards
    1
    S_1 token 1 is in the right place no matter where the others are.

    \left| {S_1  \cup S_2  \cup S_3 } \right| = \left| {S_1 } \right| + \left| {S_2 } \right| + \left| {S_3 } \right| - \left| {S_1  \cap S_2 } \right| - \left| {S_1  \cap S_3 } \right| - \left| {S_3  \cap S_2 } \right| + \left| {S_1  \cap S_2  \cap S_3 } \right|
    \begin{gathered}<br />
   +  \hfill \\<br />
  \left| {S_k } \right| = 2,\;\left| {S_k  \cap S_j } \right| = 1,\;\& \;\left| {S_1  \cap S_2  \cap S_3 } \right| = 1 \end{gathered}

    \left| {S_1  \cup S_2  \cup S_3 } \right| = 3 \cdot 2 - 3 \cdot 1 + 1 = 4
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    sorry, i changed the notiation just before i posted and confused myself.


    S_1 was the set of combinations where token 1 is in the wrong place

    So i try to find |S_1| as

    "token 1 in the wrong place, all other tokens in the right place"

    |S_1| = (ways of having n-1 tokens in the right place) * (ways of having token 1 in the wrong place if the others are correct)
    =0

    which i figure means i am probably going in completely the wrong direction as the problem will start to look like:

     0 + 0 + 0 + ...
     -1  * |T_2|
     +1  * |T_3|


    And when i come to find |T_2| i would say
    |T_2| = " combis where 2 tokens are correct, n-2 wrong"

    = ^nC_2 * D(n-2)

    which is again going heading towards a recursive answer, if any at all.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,643
    Thanks
    1594
    Awards
    1
    None is in the correct place is the opposite of at least one in the right place.
    So a derangement is the opposite if at least one in the right place.
    |A\cup B \cup C \cup D| counts the number of ways that at least one of A,~B,~C,\text{ or }D is in the correct place.
    That number 4\cdot 3!-6\cdot2!+4\cdot 1!-1\cdot 0!=15.
    Take that from 4! and you have the derangement of four items.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. derivation of the Quadratic Formula
    Posted in the Algebra Forum
    Replies: 4
    Last Post: October 26th 2010, 05:20 PM
  2. axisymmetric jet formula derivation
    Posted in the Advanced Applied Math Forum
    Replies: 11
    Last Post: June 19th 2010, 10:53 AM
  3. axisymmetric jet formula derivation
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: June 2nd 2010, 07:00 AM
  4. Replies: 5
    Last Post: February 21st 2009, 05:29 AM
  5. [SOLVED] Derivation of formula using calculus?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: July 1st 2008, 05:52 AM

Search Tags


/mathhelpforum @mathhelpforum