# Derangement Question

Printable View

• Sep 21st 2009, 08:59 PM
coldfire
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!
• Sep 21st 2009, 10:48 PM
Grandad
Derangements
Hello coldfire
Quote:

Originally Posted by coldfire
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 $\displaystyle d_n$ is the number of derangements of $\displaystyle n$ items, then, we get:

$\displaystyle n$ $\displaystyle 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 $\displaystyle \frac{d_6}{6!}$, since there are $\displaystyle d_6$ possible derangements, and $\displaystyle 6!$ possible arrangements of $\displaystyle 6$ items. So that's $\displaystyle \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 $\displaystyle {^6C_2}=15$. The remaining 4 rows are then deranged. This can be done in $\displaystyle d_4=9$ ways. So the probability of this is $\displaystyle \frac{15\times 9}{720}=\frac{3}{16}$.

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

4. There are $\displaystyle d_6$ derangements of the 6 rows, and, within each row, there are $\displaystyle 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 $\displaystyle d_6\times(d_9)^6$, which is a very large number.

Set against this, however, is the fact that there are $\displaystyle 6!$ possible arrangements of the rows, and, within each row, $\displaystyle 9!$ possible arrangements of the columns. So that's $\displaystyle 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 $\displaystyle 0.000912$.)

Grandad
• Sep 22nd 2009, 12:22 AM
coldfire
Thanks for the reply.

Is there a way to do these by the Principle of Inclusion-Exclusion?
• Sep 22nd 2009, 04:31 AM
Grandad
More on calculating derangements
Hello coldfire
Quote:

Originally Posted by coldfire
Thanks for the reply.

Is there a way to do these by the Principle of Inclusion-Exclusion?

You can certainly calculate $\displaystyle d_n$ using the Inclusion-Exclusion Principle, which results in an explicit formula for $\displaystyle d_n$:

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

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

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

$\displaystyle = 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 $\displaystyle d_n = (n-1)(d_{n-1}+d_{n-2})$, given that $\displaystyle 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
• Sep 22nd 2009, 02:47 PM
buddyguy19
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.
• Sep 22nd 2009, 03:28 PM
Plato
Quote:

Originally Posted by buddyguy19
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 $\displaystyle 123456789$.
There are $\displaystyle 9!$ ways to rearrange that string.
Of those there are $\displaystyle 8!$ ways to rearrange that string having 1 in the first place.
Let $\displaystyle \#(X_k)$ be the number of ways that $\displaystyle k$ is in the $\displaystyle k^{th}$ place.
Thus $\displaystyle \#(X_kX_jX_n)$ is the number of ways that leave $\displaystyle k,~j,~\&~,n$ fixed in their places. That is $\displaystyle 6!$.

Now we want to find the number of ways that have at least one is fixed.
That number is $\displaystyle \# \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: $\displaystyle \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.
• Sep 22nd 2009, 09:47 PM
Grandad
Hello buddyguy19

Welcome to Math Help Forum!
Quote:

Originally Posted by buddyguy19
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