To prove: $n!=\sum\limits_{r=0}^n (-1)^r \binom{n}{r} (n-r)^n$ [duplicate]

How to algebraically prove that $$n!=\sum\limits_{r=0}^n (-1)^r \binom{n}{r} (n-r)^n$$

I was trying to find number of onto functions from $A$ to $A$ containing $n$ elements.

Using the inclusion-exclusion principle I am getting $$\sum\limits_{r=0}^n (-1)^r \binom{n}{r} (n-r)^n.$$

We can also do it by simple combinatorics, as every element has to have a pre-image and number of elements in the domain equal to the number of elements in the codomain, the number of functions is $n!.$

Is there an algebraic way to prove these two are equal?

Solution 1:

It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance

$$n![z^n]e^{rz}=r^n$$

We obtain \begin{align*} \color{blue}{\sum_{r=0}^n}&\color{blue}{(-1)^r\binom{n}{r}(n-r)^n}\\ &=\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}r^n\tag{1}\\ &=\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}n![z^n]e^{rz}\tag{2}\\ &=n![z^n]\sum_{r=0}^n\binom{n}{r}\left(e^{z}\right)^r(-1)^{n-r}\tag{3}\\ &=n^n\tag{4}\\ &=n^n\tag{5}\\ &\color{blue}{=n!} \end{align*} and the claim follows.

Comment:

• In (1) we change the order of summation by setting $r \rightarrow n-r$ and use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (2) we apply the coefficient of operator.

• In (3) we use the linearity of the coefficient of operator and do a little rearrangement as preparation for the next step.

• In (4) we apply the binomial theorem.

• In (5) we do the series expansion of $e^{z}$ and see the smallest exponent of $z$ in $(e^{z}-1)^n$ is $\color{blue}{n}$. So, we will only use the constant $\color{blue}{1}$ in the series expansion.

Solution 2:

Actually, we have that $$ n! = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ n \hfill \cr k \hfill \cr} \right)\left( {n - k} \right)^{\,n} } = \left. {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ n \hfill \cr k \hfill \cr} \right)\left( {x - k} \right)^{\,n} \;} } \right|_{\,x\, = \,n} = \left. {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ n \hfill \cr k \hfill \cr} \right)p_{\,n} (x - k)\;} } \right|_{\,x\, = \,n} $$ for any $x \in \mathbb R$ or even $x \in \mathbb C$, and for any polynomial in $x$ of degree $n$, with leading coefficient $1$.

That's because the Backward Difference, defined as $$ \nabla _x f(x) = f(x) - f(x - 1) $$ and which reiterates as $$ \nabla _x ^{\,n} f(x) = \nabla _x ^{\,n - 1} f(x) - \nabla _x ^{\,n - 1} f(x - 1) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ n \hfill \cr k \hfill \cr} \right)f\left( {x - k} \right)} $$ when applied to a polynomial of degree $n$ $$ p_{\,n} (x) = \sum\limits_{0\, \le \,m\, \le \,n} {a_{\,n} x^{\,n} } $$ gives $$ \nabla _n ^{\,n} p_{\,n} (n) = \left. {\nabla _x ^{\,n} p_{\,n} (x)\,} \right|_{\,x\, = \,n} = a_{\,n} \,n! $$ as it is easy to verify, if you know Stirling Numbers and Falling factorials.

Solution 3:

Let $$\Delta f(x)=f(x+1)-f(x),$$ $$Df(x)=f'(x).$$ Since $$f(x+1)-f(x)=f'(x)+\frac{f''(x)}{2!}+\frac{f'''(x)}{3!}+\cdots,$$ we have $$\Delta=D+\frac{D^2}{2!}+\frac{D^3}{3!}+\cdots.$$

Hence $$\Delta^nf(x)=\left(D+\frac{D^2}{2!}+\frac{D^3}{3!}+\cdots\right)^nf(x).\label{1}\tag{1}$$

Applying successively the finite difference operator, we obtain $$\Delta^nf(x)=\sum_{r=0}^{n}(-1)^r {n\choose r}f(x+n-r)\label{2}\tag{2}.$$

If $f(x)=x^n$ then $D^nf(x)=n!$, and $D^mf(x)=0$ if $m>n$. Thus combining \eqref{1} and \eqref{2} we get $$n!=\sum_{r=0}^{n}(-1)^r {n\choose r}(x+n-r)^n.$$ The desired result follows by setting $x=0$. Note that this works in greater generality.