Suppose there are "$n$" people and there are "$n$" seats...

Question

Suppose there are "$n$" people and there are "$n$" seats, how many ways can those $n$ people seat such that person $i$ can´t seat in the the $i$ seat?. For example: person $2$ can´t seat in the second place. I don´t know if this changes the solution, but suposse that $n$ is and odd number. Thanks.

Answer 1

Let's start with the opposite. How many different ways can person $i$ end up in seat $i$? Well, allowing everyone else to sit where they like gives $(n-1)!$ possibilities.

We can add up the number of ways the first person can be in the first seat, the second person can be in the second seat, and so on to get $$\overbrace{(n-1)!+(n-1)!+ \cdots +(n-1)!}^{n \ times}.$$ This gives us $n \times (n-1)! = n!$ possibilities. Now that can't be right because that is the same as the total number of all permutation. Where did we go wrong? Well, we counted some configurations twice. If person one and person two were both in their own seats, then we counted that possibility when we did the computation for person one and for person two. Thus we can now subtract every possibility where any two people are in the same seats. There are $n \choose 2$ ways we can pick two seats, and $(n-2)!$ ways to permute the rest of the people, which brings us to $$n \times (n-1)! - {n \choose 2} \times (n-2)!$$ configurations. But now we have to account for the possibility that say the first three people were in their seats. We would have subtracted those cases when we calulated the possibilities for 1 and 2, 2 and 3, and 1 and 3. Thus we have to add again.

This process is called inclusion-exclusion, and there are many places to read more about it. For a small example, you can start with a three circle venn diagram and think about how you can calculate the total number of objects in a union of three sets using just full sets, intersections and the picture.

When you continue the process in the case of $n$ people we get a sum of the form

$${n \choose 1} \times (n-1)! - {n \choose 2} \times (n-2)! + {n \choose 3} \times (n-3)! - \cdots \pm {n \choose n} \times 0!.$$ Since $${n \choose k}(n-k)! = \frac{n!}{k!(n-k)!}(n-k)! = \frac{n!}{k!},$$ this equals
$$\frac{n!}{1!} - \frac{n!}{2!} + \frac{n!}{3!} \cdots \pm \frac{n!}{n!}$$ or $$n!\left(\frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} \cdots \pm \frac{1}{n!}\right).$$