# derangement problem

• May 28th 2013, 03:03 PM
Yuuki
derangement problem
At a party, n people are seated in a room with n+1 chairs. They go to another room for supper; when they return and sit down again, it is found that no one occupies the same chair as before. Show that this can occur in precisely Dn + Dn+1 ways.

When I tried to solve this, I got (n+1)*Dn + Dn+1 instead, and I'd like to know what I got wrong.

Here's my strategy: add a new "invisible person" to the n people, and consider the seating for the n+1 people & n+1 chairs.

Case 1) the invisible person sits in the same chair
Then the remaining n seats should make a derangement, so there are Dn possibilities.

Case 2) the invisible person also gets a new chair the second time
All n+1 chairs should make up a derangement, so there are Dn+1 possibilities.

But for Case 1, there are n+1 seats where the invisible person can occupy, so in total there are (n+1)*Dn + Dn+1 ways.

Why is the (n+1) factor unnecessary?
• May 28th 2013, 03:36 PM
Plato
Re: derangement problem
Quote:

Originally Posted by Yuuki
At a party, n people are seated in a room with n+1 chairs. They go to another room for supper; when they return and sit down again, it is found that no one occupies the same chair as before. Show that this can occur in precisely Dn + Dn+1 ways.
When I tried to solve this, I got (n+1)*Dn + Dn+1 instead, and I'd like to know what I got wrong.

Here's my strategy: add a new "invisible person" to the n people, and consider the seating for the n+1 people & n+1 chairs.

The $\mathcal{D}_{n+1}$ is the number of ways for all, including your "invisible person", are not in the original seat.

BUT, $\mathcal{D}_{n}$ is the number of ways for everyone other than your "invisible person" is not in the original seat.

There are just two cases: the original unoccupied seat is now occupied or it is not,
• May 28th 2013, 04:15 PM
Yuuki
Re: derangement problem

So for a given starting condition, there would be only be one Dn instead of n+1.

For example, if I denote the people A, B, C, X (X being the invisible person), and assign chairs 1, 2, 3, 4 to them respectively,
either 1) X sits in #4 the second time 2) X doesn't sit in #4 the second time, so in fact there are only Dn + Dn+1 possibilities, since the problem is only asking me to count the ways for one initial condition.

If I took in account all the initial conditions, would there be n!(Dn + Dn+1) possibilities?
• May 28th 2013, 04:38 PM
Plato
Re: derangement problem
Quote:

Originally Posted by Yuuki
So for a given starting condition, there would be only be one Dn instead of n+1.
For example, if I denote the people A, B, C, X (X being the invisible person), and assign chairs 1, 2, 3, 4 to them respectively,
either 1) X sits in #4 the second time 2) X doesn't sit in #4 the second time, so in fact there are only Dn + Dn+1 possibilities, since the problem is only asking me to count the ways for one initial condition.
If I took in account all the initial conditions, would there be n!(Dn + Dn+1) possibilities?

As I said, this is binary. Two cases.
The original unoccupied seat now occupied or not.
Those are disjoint events, so their countings are additive.
• May 28th 2013, 04:51 PM
Yuuki
Re: derangement problem
I think I see.

What you're saying is that there are Dn + Dn+1 ordered pairs (1234, x1x2x3x4),
and there are only two situations: x4=4 or x4≠4, right?

What I said about the n! is that there are n! possibilities for the first element of the ordered pair.
I was considering situations such as (2314, x1x2x3x4).
But the chairs are not actually labeled, so any starting position whether it be 1234, 2314, or 3421, are all identical.

Hence, like you said there are only Dn + Dn+1 ways.