# 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.

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