Derangements with extra chairs This was a question on my combinatorics final.

Suppose $m$ people are sitting in a room with $n$ chairs. If everyone leaves and comes back, how many ways can they sit down such that no one gets their original chair?

If $m=n$, we simply get the derangement numbers. As another example, if person $A$ is in chair $1$, $B$ is in $2$, and no one is in $3$, then there are $3$ possible arrangements. Obviously $m\le n$ in general.
The question seems pretty simple, but I had a hard time getting a simple answer (I ended up with a pretty complicated recursion which I'm pretty sure was either wrong or not the best answer).
You are allowed to use derangement numbers, $d_i$, in the answer. Also a hint provided said that the answer would be a sum.
I'm looking for some thoughts on this. I guess I should add that the final is over; I'm asking out of curiosity since I probably won't get the exam back, at least for several weeks.
 A: You can use the inclusion-exclusion principle. Let $A_k$ be the set of arrangements in which person $k$ is in his original chair. For any $S\subseteq[m]$, we have
$$\left|\bigcap_{k\in S}A_k\right|=(n-|S|)^{\underline{m-|S|}}=\frac{(n-|S|)!}{(n-m)!}=\binom{n-|S|}{m-|S|}(m-|S|)!\;,$$
and for $1\le\ell\le m$ there are $\binom{m}\ell$ subsets of $[m]$ of cardinality $\ell$, so
$$\left|\bigcup_{k\in[m]}A_k\right|=\sum_{\ell=1}^m(-1)^{\ell-1}\binom{m}\ell\binom{n-\ell}{m-\ell}(m-\ell)!\;.\tag{1}$$
$(1)$ counts the arrangements in which at least one person does return to his original chair, so we want
$$\begin{align*}
n^{\underline m}-\sum_{\ell=1}^m(-1)^{\ell-1}\binom{m}\ell\binom{n-\ell}{m-\ell}(m-\ell)!&=\frac{n!}{(n-m)!}-\sum_{\ell=1}^m(-1)^{\ell-1}\binom{m}\ell\binom{n-\ell}{m-\ell}(m-\ell)!\\
&=\binom{n}mm!-\sum_{\ell=1}^m(-1)^{\ell-1}\binom{m}\ell\binom{n-\ell}{m-\ell}(m-\ell)!\\
&=\binom{n}mm!+\sum_{\ell=1}^m(-1)^\ell\binom{m}\ell\binom{n-\ell}{m-\ell}(m-\ell)!\\
&=\sum_{\ell=0}^m(-1)^\ell\binom{m}\ell\binom{n-\ell}{m-\ell}(m-\ell)!\;,
\end{align*}$$
which can also be written
$$\sum_{\ell=0}^m(-1)^\ell\binom{m}\ell\frac{(n-\ell)!}{(n-m)!}=\frac1{(n-m)!}\sum_{\ell=0}^m(-1)^\ell\binom{m}\ell(n-\ell)!\;.$$
Here $x^{\underline k}$ is the falling factorial, $x(x-1)\ldots(x-k+1)$.
A: The number of ways to seat a particular $k$ people in their original seats is
$$
\overbrace{\ \ \ \binom{m}{k}\ \ \ }^{\substack{\text{ways to pick}\\\text{$k$ people}\\\text{from $m$}}}\overbrace{\binom{n-k}{m-k}}^{\substack{\text{ways to pick}\\\text{$m-k$ chairs}\\\text{from $n-k$}}}\overbrace{(m-k)!\vphantom{\binom{k}{k}}}^{\substack{\text{arrangements}\\\text{of $m-k$ people}}}
$$
Inclusion-Exclusion says that the number of ways for no people to be in their original seats is
$$
\begin{align}
\sum_{k=0}^m(-1)^k\binom{m}{k}\binom{n-k}{m-k}(m-k)!
&=m!\sum_{k=0}^m\frac{(-1)^k}{k!}\binom{n-k}{m-k}\\
&=m!\binom{n}{m}\sum_{k=0}^m\frac{(-1)^k}{k!}\frac{\binom{m}{k}}{\binom{n}{k}}\\
&\sim m!\binom{n}{m}\sum_{k=0}^m\frac{(-1)^k}{k!}\frac{m^k}{n^k}\\
&\sim m!\binom{n}{m}\,e^{-m/n}\quad\text{(better when $m$ is larger)}
\end{align}
$$
Since the total number of ways to arrange $m$ people into $n$ chairs is $m!\binom{n}{m}$, the probability that no one gets their old chair back approaches $e^{-m/n}$.

This is similar to the case for Derangements, when $m=n$ and
$$
\mathcal{D}(n)\sim\frac{n!}e
$$
and the probability that no one gets their old chair back approaches $\frac1e$.
