# Combinatorics Question

• Nov 15th 2013, 02:23 PM
Urbandude23
Combinatorics Question
6 people each own a desk each. The company owner wants to swap them round, so at most one of them stays where they were before. How many arrangements are possible?

I've tried 264, which was the apparent sum of the arrangements where everybody changes position plus the arrangements with one in the same place.

Can anyone help?
• Nov 15th 2013, 02:52 PM
Plato
Re: Combinatorics Question
Quote:

Originally Posted by Urbandude23
6 people each own a desk each. The company owner wants to swap them round, so at most one of them stays where they were before. How many arrangements are possible?

You need to know about derangements. Scroll down to the counting formula.
Let $D(n)$ be the number of derangements on $n$ objects.

The answer to your question is $D(6)+\binom{6}{1}D(5)$.
• Nov 15th 2013, 03:09 PM
Urbandude23
Re: Combinatorics Question
Does this factor in the part of the question that states there can still be one person in the same place as before?
• Nov 15th 2013, 03:12 PM
Plato
Re: Combinatorics Question
Quote:

Originally Posted by Urbandude23
Does this factor in the part of the question that states there can still be one person in the same place as before?

Please see my edit to that post. I miss-read it. I thought it said two people stayed put.
• Nov 15th 2013, 03:40 PM
Urbandude23
Re: Combinatorics Question
I get 283, is that correct?
• Nov 15th 2013, 04:06 PM
Plato
Re: Combinatorics Question
Quote:

Originally Posted by Urbandude23
I get 283, is that correct?

Did you take note of my edit?
$D(6)+\binom{6}{1}D(5)$.

Look at this. Then at this

Now apply the above formula.
• Nov 16th 2013, 01:00 AM
Urbandude23
Re: Combinatorics Question
So, it's 6*44+265!
• Nov 16th 2013, 06:42 AM
SlipEternal
Re: Combinatorics Question
Quote:

Originally Posted by Urbandude23
So, it's 6*44+265!

I believe that overcounts. I think this gives the correct solution:

Start with all permutations: 6!. Subtract from it the number of permutations where at least two people remain in their original positions: to count this, choose two people to remain in their original position, then permute the remaining four. However, this overcounts. If the permutation of the remaining four people fixes any other person, then I can I am counting that permutation an additional time. So, the correct number is $\binom{6}{2}4!-k$ where $k$ is the number of permutations that fixes at least three people. To count that, choose three people and permute the remaining three. Again, this overcounts by the number of permutations that fix at least four people. In other words, we need to apply inclusion/exclusion:

$6!-\binom{6}{2}4!+\binom{6}{3}3!-\binom{6}{4}2!+\binom{6}{5}1! = 720 - 360 + 60 - 30 + 6 =396$
• Nov 16th 2013, 07:43 AM
Plato
Re: Combinatorics Question
Quote:

Originally Posted by SlipEternal
I believe that overcounts.

Not is does not over count.
In the OP it wants at most one to stay put.

$D(6)$ counts the number of ways that none stay put.

$\binom{6}{1}D(5)$ counts number of the ways that exactly one stays put.

Now I did not check the poster's calculations. But the idea is correct.
• Nov 16th 2013, 10:41 AM
SlipEternal
Re: Combinatorics Question
Quote:

Originally Posted by Plato
Not is does not over count.
In the OP it wants at most one to stay put.

$D(6)$ counts the number of ways that none stay put.

$\binom{6}{1}D(5)$ counts number of the ways that exactly one stays put.

Now I did not check the poster's calculations. But the idea is correct.

My mistake. I haven't worked with derangements since I was an undergrad, and the inclusion/exclusion argument I set up was not quite right. You are correct. I was trying to give the idea of how to count it if they had not yet learned how to count derangements. But, that wikipedia entry gives a good explanation of how to arrive at the recursive formula.
• Nov 16th 2013, 10:51 AM
Plato
Re: Combinatorics Question
Quote:

Originally Posted by SlipEternal
I was trying to give the idea of how to count it if they had not yet learned how to count derangements. But, that wikipedia entry gives a good explanation of how to arrive at the recursive formula.

The actual closed formula is interesting. Using inclusion/'exclusion:
$D(N) = \sum\limits_{k = 0}^N {{{\left( { - 1} \right)}^k}\binom{N}{k} \left( {N - k} \right)!} = N!\sum\limits_{k = 0}^N {\frac{{{{( - 1)}^k}}}{{k!}}} \approx \frac{{N!}}{e}$