The following identity involving Eulerian numbers is well-known: \begin{equation} A(n,m)=\sum_{k=0}^{m}(-1)^k \binom{n+1}{k} (m+1-k)^n. \end{equation} where $A(n,m)$ is the number of permutations $(\pi_1~\pi_2~\cdots~\pi_n)$ of $\{1,2,\ldots,n\}$ having $k$ ascents, namely, $k$ places where $\pi_j < \pi_{j+1}$.

Does anyone know how to prove the above identity?

  • $\begingroup$ Did you look at the references in sources from which this identity is well-known? $\endgroup$ – Sasha Jan 20 '14 at 13:58
  • $\begingroup$ @Sasha: I found this identity on a research paper which contains no proof. $\endgroup$ – Kuai Jan 20 '14 at 17:15

Start from the bivariate generating function of the Eulerian numbers: $$G(z, u) = \frac{u-1}{u-\exp((u-1)z)} = \left(1-\frac{1}{u}\right)\frac{1}{1-\exp((u-1)z)/u}.$$

This is $$\left(1-\frac{1}{u}\right) \sum_{q\ge 0} \frac{\exp(q(u-1)z)}{u^q}.$$

This implies that $$\left\langle {n\atop k}\right\rangle = n! [u^k] \left(1-\frac{1}{u}\right) \sum_{q\ge 0} \frac{q^n(u-1)^n}{n!\times u^q}$$ which is $$[u^k] \frac{(u-1)^{n+1}}{u} \sum_{q\ge 0} \frac{q^n}{u^q} = [u^{k+1}] (u-1)^{n+1} \sum_{q\ge 0} \frac{q^n}{u^q}.$$

Extracting coefficients from this we obtain $$\sum_{p=k+1}^{n+1} {n+1\choose p} (-1)^{n+1-p} (p-(k+1))^n = \sum_{p=k+1}^{n+1} {n+1\choose n+1-p} (-1)^{n+1-p} (p-(k+1))^n.$$

Re-index the sum putting $n+1-p = q$ to get $$\sum_{q=0}^{n-k} {n+1\choose q} (-1)^q (n+1-q-(k+1))^n \\ = \sum_{q=0}^{n-k} {n+1\choose q} (-1)^q (n-k-q)^n$$

We digress for a moment to evaluate $$\sum_{q=0}^{n+1} {n+1\choose q} (-1)^q (n-k-q)^n$$ using the integral $$(n-k-q)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n-k-q)z) \; dz.$$ We get for the sum $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{q=0}^{n+1} {n+1\choose q} (-1)^q \exp((n-k-q)z) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp((n-k)z)}{z^{n+1}} \sum_{q=0}^{n+1} {n+1\choose q} (-1)^q \exp(-qz) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp((n-k)z)}{z^{n+1}} \left(1-\exp(-z)\right)^{n+1} \; dz.$$

Now note that $1-\exp(-z)$ starts at $z$ and therefore $(1-\exp(-z))^{n+1}$ starts at $z^{n+1}$ which means that the integrand is entire, making the integral evaluate to zero, so the sum is zero.

Ending the digression we now observe that the sum from the generating function is in fact $$-\sum_{q=n-k+1}^{n+1} {n+1\choose q} (-1)^q (n-k-q)^n.$$ Re-index one more time to get $$-\sum_{q=0}^k {n+1\choose n+1-q} (-1)^{n+1-q} (n-k-(n+1-q))^n \\ = \sum_{q=0}^k {n+1\choose q} (-1)^{n-q} (q-1-k)^n = \sum_{q=0}^k {n+1\choose q} (-1)^q (k+1-q)^n.$$

This is what was required. QED.


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.