7
$\begingroup$

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

Could anyone give the proof of the above equation? Thanks in advance!

$\endgroup$
  • $\begingroup$ Use induction for proof $\endgroup$ – Mayank Deora Jul 16 '16 at 16:32
  • 1
    $\begingroup$ Almost-duplicate (special case) of 1 and 2 $\endgroup$ – 6005 Jul 18 '16 at 18:27
11
$\begingroup$

Let $A=\{1,2,\ldots, n\}$. The number of bijective functions $f:A\to A$ is clearly $n!$.
On the other hand, the number of functions from $A$ to a set with $n-k+1$ elements is $(n-k+1)^n$ and there are $\binom{n}{k}$ ways for choosing a subset of $A$ with $n-k$ elements.
So the given formula directly follows from the inclusion-exclusion principle.

Another chance is to use the forward difference operator $\delta$ bringing a polynomial $p(x)$ to $p(x+1)-p(x)$. If $p$ is not a constant we have that the degree of $\delta p$ is the degree of $p$ minus one, and the leading term of $\delta p$ equals the leading term of $p'$. It follows that $\delta^n$ applied to $p(x)=x^n$ gives the constant $n!$ for any $x$, with $(\delta^{n}p)(1)$ being the given sum.

$\endgroup$
  • 2
    $\begingroup$ In the first paragraph, essentially you are saying to consider functions from $A$ into a subset of $A \cup \{0\}$ with $n - k$ elements other than zero, is that correct? $\endgroup$ – 6005 Jul 16 '16 at 19:07
8
$\begingroup$

Note that, by commutativity, $$\sum_{k=0}^{n}\dbinom{n}{k}\left(n-k+1\right)^{n}\left(-1\right)^{k}=\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}\left(-1\right)^{n-k} $$ so let us consider $$\sum_{k=0}^{n}\dbinom{n}{k}x^{k+1}\left(-1\right)^{n-k}=x\left(x-1\right)^{n} $$ then if we differentiate and we multiply by $x$ we get $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)x^{k+1}\left(-1\right)^{n-k}=nx^{2}\left(x-1\right)^{n-1}+x\left(x-1\right)^{n} $$ and if we repeat the process $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{2}x^{k+1}\left(-1\right)^{n-k}=n\left(n-1\right)x^{3}\left(x-1\right)^{n-2}+2x^{2}n\left(x-1\right)^{n-1}+nx^{2}\left(x-1\right)^{n-1}+x\left(x-1\right)^{n} $$ and so if we repeat the process $n$ times we get $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}x^{k+1}\left(-1\right)^{n-k}=n!x^{n}+\textrm{addends with a positive power of }\left(x-1\right) $$ so if we evaluate the sum at $x=1$ we get

$$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}\left(-1\right)^{n-k}=\color{red}{n!} $$

as wanted.

$\endgroup$
5
$\begingroup$

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

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

Comment:

  • In (1) we exchange the order of summation $k\rightarrow n-k$

  • In (2) we extend the limit to infty without changing anything since we are adding zeros only. We apply the coefficient of operator to $\binom{n}{k}$ and to $(k+1)^n$ using $e^{(k+1)x}$.

  • In (3) we do a simple rearrangement

  • In (4) we use the substitution rule of the coefficient of operator \begin{align*} A(x)=\sum_{k=0}^\infty a_k x^k=\sum_{k=0}^\infty x^k [z^k]A(z) \end{align*}

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

$\endgroup$
  • $\begingroup$ The exponential is an entire function, there is no reason not to use the coefficient extractor on it, it is the same formal power series as in the binomial, except now it is infinite i.e. $k^n = n! [z^n] \exp(kz)$ (and of course the values of the coefficients are different). $\endgroup$ – Marko Riedel Jul 16 '16 at 21:32
  • $\begingroup$ @MarkoRiedel: Thanks and (+1) Marko! You're right of course. It's definitely simpler and fits better to the type of presentation. $\endgroup$ – Markus Scheuer Jul 16 '16 at 21:52
  • 1
    $\begingroup$ Verified and upvoted. (+1). The next step is to use this technique to prove Stirling number identities (of the second kind, with the first kind the logarithm sometimes complicates matters). $\endgroup$ – Marko Riedel Jul 16 '16 at 21:57
  • $\begingroup$ The detour through $[z^k](1 + z)^n$ isn't needed, you go back to binomial coefficients anyway. And it is cleaner to just go $\sum_k \binom{n}{k} (-1)^k e^{k x} = (1 - e^x)^n$ directly. $\endgroup$ – vonbrand Sep 4 '16 at 0:28
  • $\begingroup$ @vonbrand: Many thanks for the hint and also for the upvotes, professor! In fact I do not fully agree, since the motivation is to also present this technique in a methodologically coherent way for those who are not familiar with it. So, I do not necessarily focussing on the shortest possible road. This technique is based upon P.G. Egorychev's classic. $\endgroup$ – Markus Scheuer Sep 4 '16 at 12:23
2
$\begingroup$

Suppose we seek to evaluate

$$\sum_{k=0}^n {n\choose k} (-1)^k (n-k+1)^n.$$

Introduce

$$(n-k+1)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n-k+1)z) \; dz.$$

We get for the sum

$$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n+1)z) \sum_{k=0}^n {n\choose k} (-1)^k \exp(-kz) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n+1)z) (1-\exp(-z))^n \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z) (\exp(z)-1)^n \; dz.$$

This is $$n! [z^n] \exp(z) (\exp(z)-1)^n.$$

Now $$\exp(z)-1 = z + \frac{z^2}{2} + \frac{z^3}{6} +\cdots$$ and hence

$$(\exp(z)-1)^n = z^n + \cdots.$$

Therefore the result is

$$n! [z^0] \exp(z) = n!.$$

$\endgroup$

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.