# Derangement Question

• 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
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 $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$.)

• Sep 22nd 2009, 12:22 AM
coldfire

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

Originally Posted by coldfire

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.

• 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 $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.
• Sep 22nd 2009, 09:47 PM