You need to know about derangements. Scroll down to the counting formula.
Let be the number of derangements on objects.
The answer to your question is .
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?
You need to know about derangements. Scroll down to the counting formula.
Let be the number of derangements on objects.
The answer to your question is .
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 where 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:
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.