4
$\begingroup$

I am not sure how to approach this problem:

$n$ people are seated in numbered chairs $1$ to $n$. Let $N$ be the number of ways the people can be reseated so that no one is in the same chair as before. Show that $N=n! \sum_{k=0}^n \frac {(-1)^k}{k!}$.

I feel like the way to do this is to come up with a way to count all the seating arrangements, yet I am not sure how to take into account the seat where the person already sat into account when counting them. Because it would seem that there is $n-1$ possible places to sit at, yet placing the first person does not eliminate one possibility for everyone...

Any help is appreciated. Thank you in advance.

$\endgroup$
2
$\begingroup$

This is an application of Inclusion-Exclusion.

Let $A_k$ denote the set of arrangements such that person $k$ is in the original chair that he/she was sitting in. Then, $\cup_{i=1}^n A_i$ denotes the set of arrangements where at least one person is sitting in his/her original chair. We are interested in $\lvert \left( \cup_{i=1}^n A_i \right)^c \rvert$. Note that $$\sum_{i_1,i_2,\dots,i_j} \lvert A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j} \rvert = \binom{n}{j} (n-j)!,$$ since we're picking $j$ people out of $n$ to fix in their original chairs and permute the remaining $(n-j)$ people. Now, by inclusion-exclusion, we have

\begin{align*} \left\lvert \bigcup_{i=1}^n A_i \right\rvert &= \sum_i \lvert A_i \rvert - \sum_{i,j} \lvert A_i \cap A_j \rvert + \sum_{i,j,k} \lvert A_i \cap A_j \cap A_k \rvert - \cdots \pm \sum_{i_1,i_2,\dots,i_n} \lvert A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_n} \rvert \\ &= \binom{n}{1} (n-1)! - \binom{n}{2}(n-2)! + \binom{n}{3}(n-3)! - \cdots \pm \binom{n}{n}0! \\ &= \frac{n!}{1!} - \frac{n!}{2!} + \frac{n!}{3!} - \cdots \pm \frac{n!}{n!} \end{align*} Hence, our desired answer is \begin{align*} N &= \left\lvert \left(\bigcup_{i=1}^n A_i\right)^c \right\rvert \\ &= n! - \left\lvert \bigcup_{i=1}^n A_i \right\rvert \\ &= n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + \cdots \pm \frac{n!}{n!} \\ &= n! \sum_{k=0}^n \frac{(-1)^k}{k!} \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.