The successive difference of powers of integers leads to factorial of that power. Here's the formula:


Can anyone give a proof of this result?

Note: The original question was to prove the more general


for an integer $l$, which some of the answers address.


6 Answers 6


Let $A:=\{ x_1,..,x_n \}$ and $B=\{y_1,..,y_m \}$.

Lets count the number of onto functions $f:A \to B$. There are $m^n$ functions from $A$ to $B$. Lets count now the ones which are not onto:


$$P_i= \{ f : A \to B |y_i \notin f(A) \}$$

Then we need to figure out the cardinality of $\cup_i P_i$.

By the inclusion exclusion principle

$$|P_1 \cup P_2 ..\cup P_m |=\sum |P_i|-\sum |P_i \cap P_j|+\sum |P_i \cap P_j \cap P_k| -... \\=\binom{m}{1}(m-1)^n-\binom{m}{2}(m-2)^n+\binom{m}{3}(m-3)^n-... $$

Thus in total there are

$$m^n-\binom{m}{1}(m-1)^n+\binom{m}{2}(m-2)^n-\binom{m}{3}(m-3)^n-...=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n$$

When $n=m$ the number of onto functions is

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

But any function $f: \{ x_1,..,x_n \} \to\{y_1,..,y_n \}$ is onto if and only if it is a bijection. Thus the number of onto functions is equal to the number of bijections, which is $n!$.


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

  • $\begingroup$ Thanku . How to extend it for all numbers ? ... $\endgroup$
    – hanugm
    Dec 3, 2013 at 19:22
  • $\begingroup$ I mean for $(l-k)^n$ inside sigma ...... $\endgroup$
    – hanugm
    Dec 3, 2013 at 19:25
  • $\begingroup$ @hanu I think it is true only when $l=n$. $\endgroup$
    – N. S.
    Dec 3, 2013 at 20:11
  • $\begingroup$ @N.S. It is true for any $l$. I show it algebraically in my answer, but I haven't tried to think of a combinatorial argument. It would most likely involve the Inclusion-Exclusion Principle, however. $\endgroup$
    – robjohn
    Dec 4, 2013 at 16:19
  • $\begingroup$ I might be wrong but shouldn't the expression for PIE be $=\binom{m}{1}(m-1)^n-\binom{m}{2}(m-2)^n+\binom{m}{3}(m-3)^n-...$ ? $\endgroup$
    – r9m
    Nov 17, 2014 at 9:34

This identity also has an algebraic proof. Suppose the sum we are trying to evaluate is given by $$\sum_{k=0}^n {n\choose k} (-1)^k (n-k)^{n}.$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that \begin{align} A(z) B(z) &= \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ &= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!} \end{align} i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Now in the present case we clearly have $$A(z) = \sum_{q\ge 0} (-1)^q \frac{z^q}{q!} = \exp(-z).$$ Furthermore we have $$B_n(z) = \sum_{q\ge 1} q^{n} \frac{z^q}{q!} = \exp(z) \sum_{k=1}^{n} {n\brace k} z^k,$$ as can be seen by induction. For $n=1$ we have $$B_1(z) = \sum_{q\ge 1} q \frac{z^q}{q!} = z \sum_{q\ge 1} \frac{z^{q-1}}{(q-1)!} = \exp(z)\times z.$$ Now using the induction hypothesis we have $$B_{n+1}(z) = z \frac{d}{dz} B_n(z) = z \exp(z) \sum_{k=1}^{n} {n\brace k} k z^{k-1} + z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k.$$ This is \begin{align} & z \exp(z) \sum_{k=0}^{n-1} {n\brace k+1} (k+1) z^k + z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k \\ &= z \exp(z) \left({n\brace 1} + \sum_{k=1}^{n-1} \left({n\brace k+1} (k+1)+{n\brace k}\right)z^k+ {n\brace n} z^{n}\right) \\ &= z \exp(z) \left({n+1\brace 1} + \sum_{k=1}^{n-1} {n+1\brace k+1} z^k + {n+1\brace n+1} z^{n}\right) \\ &= \exp(z) \left({n+1\brace 1} z + \sum_{k=1}^{n-1} {n+1\brace k+1} z^{k+1} + {n+1\brace n+1} z^{n+1}\right) = \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k. \end{align}

Returning to the original problem we find that the sum has the value $$n! [z^n] A(z) B_n(z) = n! [z^n] \sum_{k=1}^{n} {n\brace k} z^k = n! {n\brace n} = n!$$ which was to be shown.

A useful exercise in the algebra of Stirling numbers and binomial coefficients. Here is a MSE link that points to another calculation of the same type.

Addendum. In response to the comment we can actually show that $$\sum_{k=0}^n {n\choose k} (-1)^k (l-k)^{n}$$ for $l$ an integer.

Observe that $$l-k = (n-k)+(l-n)$$ and put $p=l-n.$ Using the same setup as before we now have \begin{align} B(z) &= \sum_{q\ge 0} (q+p)^n \frac{z^q}{q!} = \sum_{q\ge 0} \sum_{m=0}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!} \\ &= \sum_{q\ge 0} p^n \frac{z^q}{q!} + \sum_{q\ge 0} \sum_{m=1}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!} = \exp(z) p^n +\sum_{m=1}^n {n\choose m} p^{n-m} \sum_{q\ge 0} q^m \frac{z^q}{q!} \\ &= \exp(z) p^n + \exp(z) \sum_{m=1}^n {n\choose m} p^{n-m} \sum_{k=1}^m {m\brace k} z^k. \end{align} This formula also holds for $p=0$ if we assume that $0^0=1$, in which case it produces the first formula we derived above. It follows that $$n! [z^n] A(z) B_n(z) = n! [z^n] \left(p^n+\sum_{m=1}^n {n\choose m} p^{n-m} \sum_{k=1}^m {m\brace k} z^k\right) = n! {n\choose n} {n\brace n} = n!$$ thereby showing the result for all $l.$

Addendum Oct 10 2016. There is really nothing to prove here as the formula $$\frac{1}{n!} \sum_{k=0}^n {n\choose k} (-1)^{n-k} k^m$$ by definition gives the Stirling number of the second kind $${m\brace n}.$$

  • $\begingroup$ .. So the formula $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$ is valid for any value of $l$ or valid only if $l=n$ $\endgroup$
    – hanugm
    Dec 3, 2013 at 21:22

In this answer are three different proofs of this cancellation lemma: $$ \sum_{j=k}^n(-1)^{n-j}\binom{n}{j}\binom{j}{k} =\left\{\begin{array}{} 1&\text{if }n=k\\ 0&\text{otherwise} \end{array}\right.\tag{1} $$ Inductively, we can see that any polynomial in $j$ of degree $m$ can be written uniquely as $$ \sum_{k=0}^mc_k\binom{j}{k}\tag{2} $$ where the coefficient of $j^m$ is $\dfrac{c_m}{m!}$.

Putting $(1)$ and $(2)$ together, for $m\le n$, we have $$ \begin{align} \sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}\sum_{k=0}^mc_k\binom{j}{k} &=\sum_{k=0}^m\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}\binom{j}{k}\\ &=c_n\tag{3} \end{align} $$ If $m\lt n$, then $c_n=0$. If $m=n$, then $c_n$ is $n!$ times the coefficient of $j^n$.

Applying $(3)$ $$ \begin{align} \sum_{r=0}^n\binom{n}{r}(-1)^r(l-r)^n &=\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}(r-l)^n\\ &=n!\tag{4} \end{align} $$ because, for any $l$, $(r-l)^n$ is a degree $n$ polynomial in $r$ in which the coefficient of $r^n$ is $1$.

  • $\begingroup$ Very nice. Upvoted. You might have mentioned that in the sums being treated in eq. $(3)$ the coefficient on $j^n$ is actually $(-1)^n$ which cancels the $(-1)^n$ in the outer sum to produce the desired result. Very useful the fact that when writing a polynomial as a sum of binomial coefficients only the highest degree term contributes to the leading coefficient and we know what that contribution is. $\endgroup$ Dec 4, 2013 at 0:57
  • $\begingroup$ @MarkoRiedel: thanks! To be explicit, I added equation $(4)$. $\endgroup$
    – robjohn
    Dec 4, 2013 at 1:36

Using the definition of the Exponential Series,

$$e^x=\sum_{0\le r<\infty}\frac{x^r}{r!} \implies e^x-1=x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots$$

Taking $n$th power, $$ (e^x-1)^n=\left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n$$

$$\text{Now, }(e^x-1)^n=e^{nx}-\binom n1e^{(n-1)x}+\binom n2e^{(n-2)x}-\cdots$$

$$=\sum_{0\le r<\infty}\frac{(nx)^r}{r!}-\binom n1\sum_{0\le r<\infty}\frac{\{(n-1)x\}^r}{r!}+\binom n2\sum_{0\le r<\infty}\frac{\{(n-2)x\}^r}{r!}-\cdots$$

So, the coefficient of $x^r$ in $(e^x-1)^n$

$$\frac{n^r}{r!}-\binom n1\frac{(n-1)^r}{r!}+\binom n2\frac{(n-2)^r}{r!}-\cdots$$

$$\text{ Again, } \left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n=x^n+\text{ the higher powers of } x$$

Equating we get

$$\frac{n^r}{r!}-\binom n1\frac{(n-1)^r}{r!}+\binom n2\frac{(n-2)^r}{r!}-\cdots=\begin{cases} 0 &\mbox{if } 0\le r< n \\ 1 & \mbox{if } r=n \end{cases} $$


Suppose we are trying to evaluate $$\sum_{q=0}^n {n\choose q} (-1)^q (k-q)^n.$$ Observe that $$(k-q)^n = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((k-q)z) \; dz.$$

This gives for the sum the integral $$\frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{q=0}^n {n\choose q} (-1)^q \exp((k-q)z) \; dz \\ = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{\exp(kz)}{z^{n+1}} \sum_{q=0}^n {n\choose q} (-1)^q \exp(-qz) \; dz \\ = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{\exp(kz)}{z^{n+1}} (1-\exp(-z))^n \; dz.$$

Observe that $$1-\exp(-z) = z-\frac{1}{2}z^2+\frac{1}{6}z^3-\cdots$$ so $(1-\exp(-z))^n$ starts at $z^n$, which means that the residue is one ($\exp(kz)$ starts at $z^0$), giving $$n!$$ as the end result.


In the following we use the coefficient of operator $[z^r]$ to denote the coefficient of $z^r$ in a series. This way we can write e.g. \begin{align*} \binom{n}{r}=[z^r](1+z)^n\qquad\text{and}\qquad r^n=n![z^n]e^{rz} \end{align*}

We obtain for $n\geq 0$ and $l\in\mathbb{C}$ \begin{align*} \sum_{r=0}^n&\binom{n}{r}(-1)^r(l-r)^n\\ &=\sum_{r=0}^\infty[z^r](1+z)^n(-1)^rn![u^n]e^{(l-r)u}\tag{1}\\ &=n![u^n]e^{lu}\sum_{r=0}^\infty\left(-e^{-u}\right)^r[z^r](1+z)^n\tag{2}\\ &=n![u^n]e^{lu}\left(1-e^{-u}\right)^n\tag{3}\\ &=n![u^n]u^n\tag{4}\\ &=n!\\ \end{align*} and the claim follows.

Please note the formula is valid for any $l$.


  • In (1) we apply the coefficient of operator to $\binom{n}{r}$ and to $(l-r)^n$ using $e^{(l-r)u}$. We also extend the limit to infty without changing anything since we are adding zeros only.

  • In (2) we do some rearrangements using the linearity of the coefficient of operator.

  • In (3) we apply the substitution rule \begin{align*} A(u)=\sum_{r=0}^\infty a_r u^r=\sum_{r=0}^\infty u^r [z^r]A(z) \end{align*}

  • In (4) we consider the series expansion \begin{align*} e^{lu}(1-e^{-u})^n&=(1+lu+\cdots)\left(u-\frac{u^2}{2}+\cdots\right)^n\\ &=1\cdot\left(u^n\mp\text{powers of }u\text{ greater than }n\cdots\right) \end{align*} and need only to respect the $u$-term with power equal to $n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.