Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

Question

If $l$ and $n$ are any positive integers, is there a proof of the identity

$$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$

which uses the Inclusion-Exclusion Principle?

(If necessary, restrict to the case where $l\ge n$.)

---

This question is closely related to Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

and also Proof of the summation $n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$?

Answer 1

Assume that $\ell\ge n$. We want to count the injections from $[n]$ to $[\ell]$ whose range is $[n]$. For each $k\in[n]$ let $A_k$ be the set of functions from $[n]$ to $[\ell]\setminus\{k\}$. It’s not hard to see that for any non-empty $I\subseteq[n]$ we have

$$\left|\,\bigcap_{k\in I}A_k\,\right|=(\ell-|I|)^n\;,$$

so by the inclusion-exclusion principle we have

$$\begin{align*}\left|\,\bigcup_{k=1}^nA_k\,\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}(\ell-|I|)^n\\ &=\sum_{k=1}^n\binom{n}k(-1)^{k-1}(\ell-k)^n\;. \end{align*}$$

This is the number of functions from $[n]$ to $[\ell]$ that miss at least one element of $[n]$, so we want the size of the complementary set, which is

$$\begin{align*} \ell^n-\sum_{k=1}^n\binom{n}k(-1)^{k-1}(\ell-k)^n&=(-1)^0\binom{n}0(\ell-0)^n+\sum_{k=1}^n(-1)^k\binom{n}k(\ell-k)^n\\ &=\sum_{k=0}^n(-1)^k\binom{n}k(\ell-k)^n\;. \end{align*}$$

Of course there are $n!$ injections from $[n]$ to $[\ell]$ with range $[n]$, so

$$\sum_{k=0}^n(-1)^k\binom{n}k(\ell-k)^n=n!\tag{1}$$

for $\ell\ge n$.

Let

$$p(x)=n!-\sum_{k=0}^n(-1)^k\binom{n}k(x-k)^n\;;$$

$p(x)$ is a polynomial in $x$ of degree $n$, and every integer $\ell\ge n$ is a zero of $p(x)$, so $p(x)$ must be constant, and therefore

$$\sum_{k=0}^n(-1)^k\binom{n}k(x-k)^n=n!$$

for all $x$: $x$ need not even be an integer.

Answer 2

Let $A=\{1,\cdots,n\}$ and $B=\{1,\cdots,l\}$ where $l\ge n$, and let $S$ be the set of functions from $A$ to $B$.

If $E_i$ is the set of functions in $S$ which do not have the value $i$ for $1\le i\le n$,

then $\overline{E_1}\cap\cdots\cap\overline{E_n}$ is the set of functions from $A$ to $B$ which have $A$ as their range.

Using Inclusion-Exclusion,

$\displaystyle|\overline{E_1}\cap\cdots\cap\overline{E_n}|=|S|-\sum_{i}|E_i|+\sum_{i<j}|E_i\cap E_j|-\sum_{i<j<k}|E_i\cap E_j\cap E_k|+\cdots$

so $\;\displaystyle n!=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^{n}$.