How to prove Eulerian Identity?

Question

This is a question in the book Concrete Mathematics of Graham and Knuth about Eulerian numbers, Stirling Numbers of the second kind and binomial coefficients. I have been thinking about it for a lot of time and failed to find out a way to solve it.

Answer 1

By way of enrichment and not necessarily following the text we start from the bivariate generating function of the Eulerian numbers, which seems like a reasonable starting point and which is

$$\frac{u-1}{u-\exp((u-1)z)}.$$

We seek to show that for $n\ge m$

$$m! {n\brace m} = \sum_{k=0}^{n-1} \left\langle {n \atop k} \right\rangle {k\choose n-m}.$$

The RHS is

$$[v^{n-m}] \sum_{k=0}^{n-1} \left\langle {n \atop k} \right\rangle (1+v)^k \\ = n! [z^n] [v^{n-m}] \frac{v}{1+v-\exp(vz)} = n! [z^n] [v^{n-m}] \frac{v}{v-(\exp(vz)-1)} \\ = n! [z^n] [v^{n-m}] \frac{1}{1-(\exp(vz)-1)/v}.$$

Now $\exp(vz)-1$ as a formal power series in $z$ starts with $z$ and hence we may write

$$n! [z^n] [v^{n-m}] \sum_{q=0}^n \frac{(\exp(vz)-1)^q}{v^q} = [v^{n-m}] n! [z^n] \sum_{q=0}^n \frac{(\exp(vz)-1)^q}{q!} \frac{q!}{v^q} \\ = [v^{n-m}] \sum_{q=0}^n {n\brace q} v^n \frac{q!}{v^q} = [v^{n-m}] \sum_{q=0}^n q! {n\brace q} v^{n-q}.$$

This is a polynomial in $v$ and only the term with $q=m$ contributes, namely

$$\bbox[5px,border:2px solid #00A000]{ m! {n\brace m}.}$$

Answer 2

Recall the well known formula for the Stirling numbers of the second kind \begin{eqnarray*} m! {n \brace m} = \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} i^n \end{eqnarray*} the RHS is clearly the $m^{th}$ difference of the function $f(x)=x^n$. So using $(6.37)$ and inverting the order of the plums, we have \begin{eqnarray*} m! {n \brace m} &=& \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} i^n \\ &=& \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} \sum_{k} \left\langle {n \atop k} \right\rangle \binom{i+k}{n} \\ &=& \sum_{k} \left\langle {n \atop k} \right\rangle \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} \binom{i+k}{n}. \\ \end{eqnarray*} Now a quick binomial identity using the old coefficient trick \begin{eqnarray*} \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} \binom{i+k}{n} &=& [x^n]: \sum_{i=0}^{m} (-1)^{m-i} \binom{m}{i} (1+x)^{i+k} \\ &=& [x^n]: x^{m} (1+x)^{k} = \binom{k}{n-m}\\ \end{eqnarray*} & we are dumb. $\ddot \smile$