Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm aware of the identity \begin{align} \sum_{i = 0}^{k} i! \binom{n+1}{i + 1} S(k,i) = H_{n,-k}, \end{align} where $H_{n,-k}$ is a generalized Harmonic number defined by $H_{n,m} = \sum_{r = 1}^{n} r^{-m}$. I believe the following sum is related to the generalized Harmonic numbers as well, \begin{align} \sum_{i = 0}^{k} (-1)^{i} i! \binom{n-i}{k-i} S(j,i) \end{align} and should be a nice function of $n, k$ and $j$, where $0 \leq j, k \leq n$. Any hints are certainly welcome!

share|cite|improve this question

I'm not sure that you're going to be able to get a nice expression in general (although I would be happy to be proved wrong!).

The special case $j = n$ has a very simple expression in terms of the Eulerian numbers, though. We have $$\sum_{i=0}^k (-1)^i i! \binom{n-i}{k-i} \left\{ n \atop i\right\} = \sum_{i=0}^k (-1)^i i! \binom{n-i}{n-k} \left\{ n \atop i\right\} = (-1)^k \left\langle n \atop n-k\right\rangle,$$ where the first step follows from $\binom{n}{k} = \binom{n}{n-k}$ and the second step from a known expression for the Eulerian numbers (see Eq. 6.40, Concrete Mathematics, 2nd edition, p. 269). The Eulerian number $\left\langle n \atop k\right\rangle$ counts the number of permutations on $n$ elements in which exactly $k$ are larger than the immediately preceding element.

Maybe the case $j = 2$ is of interest as well. Here we have $$\sum_{i=0}^k (-1)^i i! \binom{n-i}{k-i} \left\{ 2 \atop i\right\} = 2\binom{n-2}{k-2} -\binom{n-1}{k-1} = 2\binom{n-2}{k-2} -\left[\binom{n-2}{k-1} + \binom{n-2}{k-2}\right] $$ $$= \binom{n-2}{k-2} -\binom{n-2}{k-1},$$ which is the just the triangle you get when you take differences of neighboring entries in Pascal's triangle. This triangle can also be thought of as two copies of Catalan's triangle, one positive and one negative, although the numbers are shifted and rotated.

share|cite|improve this answer

By way of enrichment of this discussion we give a purely algebraic proof that does not use Eulerian numbers.

Suppose we seek to prove that $$\sum_{q=0}^n q! {m+1\choose q+1} {n\brace q} = H_{m,-n}$$ with $m\ge n.$

Recall the bivariate generating function $G(z, u)$ of the Stirling numbers of the second kind which is $$G(z, u) = \exp(u(\exp(z)-1)).$$

This yields for the sum that $$\sum_{q=0}^n q! {m+1\choose q+1} n! [z^n] [u^q] \exp(u(\exp(z)-1)) \\= n! [z^n] \sum_{q=0}^n q! {m+1\choose q+1} \frac{(\exp(z)-1)^q}{q!} = n! [z^n] \sum_{q=0}^n {m+1\choose q+1} (\exp(z)-1)^q.$$

An important observation at this point is that $\exp(z)-1$ starts at $z$, so we may extend the summation to $m$ without affecting the coefficient of $z^n,$ getting $$n! [z^n] \sum_{q=0}^m {m+1\choose q+1} (\exp(z)-1)^q.$$ Rewrite this as $$(m+1) \times n! [z^n] \sum_{q=0}^m {m\choose q} \frac{(\exp(z)-1)^q}{q+1} \\= (m+1) \times n! [z^n] \frac{1}{\exp(z)-1} \sum_{q=0}^m {m\choose q} \frac{(\exp(z)-1)^{q+1}}{q+1}.$$

Stop for a moment to perform a formal power series integration. We have $$(1+x)^m = \sum_{q=0}^m {m\choose q} x^q$$ so that $$\frac{1}{m+1}(1+x)^{m+1} - \frac{1}{m+1} =\frac{1}{m+1}\left((1+x)^{m+1} - 1\right) \\= \sum_{q=0}^m {m\choose q} \frac{x^{q+1}}{q+1}.$$

Apply this to the sum to obtain $$(m+1) \times n! [z^n] \frac{1}{\exp(z)-1} \frac{1}{m+1}\left(\exp(z(m+1)) - 1\right)$$ which is $$n! [z^n] \frac{\exp(z(m+1)) - 1}{\exp(z)-1} = n! [z^n] \sum_{k=0}^m \exp(zk) \\= n! \sum_{k=0}^m \frac{k^n}{n!} = \sum_{k=0}^m k^n = H_{m, -n}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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