Rearranging people so that no one is in the same spot 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.
 A: 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*}
