Results 1 to 7 of 7

Math Help - Derangement Question

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    48

    Derangement Question

    Hi, I was wondering if anyone could help me get started with this question:

    6 groups of students each consisting of 9 students are in a theatre and sit in rows 1 to 6 and columns A to I, with all students in the same group sitting in the same row. All the students leave and come back, again sitting in rows 1 to 6 and columns A to I, all students in the same group are still sitting in the same row.

    What is the probability that:

    1. No group of students sits in its original row?
    2. Exactly 2 groups of students sit in their original row?
    3. At least 3 groups of students sit in their original row?
    4. No students sit in their original row and no student sits in their original column?

    Can anyone help me get started with this question? I am completely lost.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Derangements

    Hello coldfire
    Quote Originally Posted by coldfire View Post
    Hi, I was wondering if anyone could help me get started with this question:

    6 groups of students each consisting of 9 students are in a theatre and sit in rows 1 to 6 and columns A to I, with all students in the same group sitting in the same row. All the students leave and come back, again sitting in rows 1 to 6 and columns A to I, all students in the same group are still sitting in the same row.

    What is the probability that:

    1. No group of students sits in its original row?
    2. Exactly 2 groups of students sit in their original row?
    3. At least 3 groups of students sit in their original row?
    4. No students sit in their original row and no student sits in their original column?

    Can anyone help me get started with this question? I am completely lost.

    Thanks!
    Since you've used the word 'derangement' in your title, you clearly know what one is. Here's the Wikipedia entry.

    If d_n is the number of derangements of n items, then, we get:

    n d_n
    1 0
    2 1
    3 2
    4 9
    5 44
    6 265
    7 1854
    8 14833
    9 133496

    1. No student sits in their original row. This implies that a derangement of the six rows has occurred, and the probability of this is \frac{d_6}{6!}, since there are d_6 possible derangements, and 6! possible arrangements of 6 items. So that's \frac{265}{720}=\frac{53}{144}.

    2. Exactly 2 groups sit in their original row. The number of ways of choosing which 2 rows are left unchanged is {^6C_2}=15. The remaining 4 rows are then deranged. This can be done in d_4=9 ways. So the probability of this is \frac{15\times 9}{720}=\frac{3}{16}.

    3. The number of ways in which exactly 3 groups sit in their original rows is {^6C_3} \times d_3; the number of ways in which exactly 4 groups sit in their original rows is {^6C_4} \times d_2, ... Can you complete it from here?

    4. There are d_6 derangements of the 6 rows, and, within each row, there are d_9 derangements of the 9 columns. Each of the six rows is deranged (I love the thought of deranged students!) so the total number of possibilities is d_6\times(d_9)^6, which is a very large number.

    Set against this, however, is the fact that there are 6! possible arrangements of the rows, and, within each row, 9! possible arrangements of the columns. So that's 6!\times(9!)^6 altogether.

    The probability of this, then, is ...? (If I and my spreadsheet have done the arithmetic correctly, this comes out at about 0.000912.)

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    48
    Thanks for the reply.

    Is there a way to do these by the Principle of Inclusion-Exclusion?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    More on calculating derangements

    Hello coldfire
    Quote Originally Posted by coldfire View Post
    Thanks for the reply.

    Is there a way to do these by the Principle of Inclusion-Exclusion?
    You can certainly calculate d_n using the Inclusion-Exclusion Principle, which results in an explicit formula for d_n:

    d_n = n!\Big(1 -\sum_{p=1}^n\frac{(-1)^{p-1}}{p!}\Big)

    This will enable you to calculate any value of d_n directly. For example, for n = 6 this gives:

    d_6=6!\Big(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}\Big)

    = 720 - 720 + 360 - 120 +30-6+1=265

    However, if (like me) you're using a spreadsheet to do the calculations, it's probably easier to use the recursive formula d_n = (n-1)(d_{n-1}+d_{n-2}), given that d_1 = 0,\, d_2 =1. This formula can be set up in a matter of seconds in a spreadsheet - which is what I did to get the numbers in my first posting.

    Pay your money and take your choice, as the saying goes!

    Grandad
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2009
    Posts
    1
    Hello, I am also having trouble with this problem.

    Can you go into further detail as to how to solve the questions using the principle of inclusion-exclusion? Thankyou.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by buddyguy19 View Post
    Can you go into further detail as to how to solve the questions using the principle of inclusion-exclusion? Thankyou.
    I’ve got some time to kill. Consider the string 123456789.
    There are 9! ways to rearrange that string.
    Of those there are 8! ways to rearrange that string having 1 in the first place.
    Let \#(X_k) be the number of ways that k is in the k^{th} place.
    Thus \#(X_kX_jX_n) is the number of ways that leave k,~j,~\&~,n fixed in their places. That is 6!.

    Now we want to find the number of ways that have at least one is fixed.
    That number is \# \left( {X_1  \cup X_2  \cup  \cdots  \cup X_9 } \right) = \sum\limits_{k = 1}^9 {\left( { - 1} \right)^{k + 1}  \binom{9}{k} \left( {9 - k} \right)!}

    But that leaves at least one fixed, we want a derangement, none fixed.
    So subtract that from the total: \sum\limits_{k = 0}^9 {\left( { - 1} \right)^k \binom{9}{k}\left( {9 - k} \right)!}

    If you follow this, then for a general case replace n for 9.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello buddyguy19

    Welcome to Math Help Forum!
    Quote Originally Posted by buddyguy19 View Post
    Hello, I am also having trouble with this problem.

    Can you go into further detail as to how to solve the questions using the principle of inclusion-exclusion? Thankyou.
    You'll find some more detail here. Best of luck!

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial proof of derangement identity
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 29th 2010, 03:40 PM
  2. Derivation of Derangement formula
    Posted in the Advanced Statistics Forum
    Replies: 9
    Last Post: June 6th 2010, 02:42 PM
  3. derangement question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 8th 2009, 03:18 PM

Search Tags


/mathhelpforum @mathhelpforum