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

• How about mathematical induction? Jun 21, 2018 at 14:12
• Using the Binomial Theorem, you have: $$\sum_{r=0}^n(-1)^r\dbinom{n}{r}(n-r)^n = \sum_{r=0}^n(-1)^r\dbinom{n}{r}\left(\sum_{k=0}^n\dbinom{n}{k}n^k(-r)^{n-k}\right)$$ This might help. I haven't checked, though. Jun 21, 2018 at 14:23
• If you don't like to use MI, you may try to expand the RHS: $n!=n(n-1)(n-2)....(2)(1)$ Jun 21, 2018 at 14:24
• @Jerry how to use mathematical induction here? I tried but couldn't get it. Jun 21, 2018 at 14:33
• @ATHARVA I used the Binomial Theorem: en.wikipedia.org/wiki/Binomial_theorem Jun 21, 2018 at 14:37

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![z^n](e^{z}-1)^n\tag{4}\\ &=n![z^n](z+\frac{z^2}{2!}+\cdots)^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.

• Cool solution, but I think you should flesh out the passage from (2) to(3) a bit more. Jun 21, 2018 at 15:47
• @goblin: Thanks. :-) I've added some information which might be helpful. Jun 21, 2018 at 17:20
• @FelixMarin: Many thanks. Typo corrected. Sep 19, 2018 at 6:21

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.

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.

• yes, this is an interesting recasting of the answer I gave in terms of "backward" instead of "forward" difference . Jun 21, 2018 at 18:56