Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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 would like to compute $\sum_{k=0}^n S(n,k) k$, where $S(n,k)$ is a Stirling number of the second kind. Any ideas? It is like I am convolving the Stirling numbers of the second kind with the positive integers. Thank you very much!

share|cite|improve this question
This is not a convolution. The convolution would be $\sum_{k=0}^n kS(n,n-k)$. – joriki Mar 13 '11 at 19:33
up vote 15 down vote accepted

$$\sum_{k=0}^n \left\{ n \atop k\right\} k = \varpi(n+1) - \varpi(n),$$ where $\varpi(n)$ is the $n$th Bell number.

Using generating functions, I prove this and the generalizations $$\sum_{k=0}^n \left\{ n \atop k\right\} k^m = \sum_{i=0}^m \binom{m}{i} R(m-i) \varpi(n+i),$$ $$\sum_{k=0}^n \left\{ n \atop k\right\} (-1)^k k^m = \sum_{i=0}^m \binom{m}{i} \varpi(m-i) R(n+i),$$ where $R(n)$ is the $n$th Rao-Uppuluri-Carpenter number, in the paper "On Solutions to a General Combinatorial Recurrence" (Journal of Integer Sequences 14 (9), Article 11.9.7, 2011). See Identities 12 and 13, which are at the very end. This paper has been submitted for publication, and I am still waiting on referee reports.

I don't know whether these results are new, but I had not seen them before. (They are not the main point of the paper.)

Added: Here are some additional derivations for $\sum_{k=0}^n \left\{ n \atop k\right\} k = \varpi(n+1) - \varpi(n)$. They are shorter than the one needed in the paper for the more general result.

First: Use the recurrence for the Stirling numbers of the second kind. (Due to OP - see comments.)

$$\sum_{k=0}^n \left\{ n \atop k\right\} k = \sum_{k=0}^n \left\{ n+1 \atop k\right\} - \sum_{k=0}^n \left\{ n \atop k-1\right\} = \sum_{k=0}^{n+1} \left\{ n+1 \atop k\right\} - \sum_{k=0}^n \left\{ n \atop k\right\} =\varpi(n+1) - \varpi(n).$$

Second: Use Bell polynomials $B_n(x)$.

It is known that $\sum_{k=0}^n \left\{ n \atop k \right\} x^k = B_n(x)$ (Eq. 14 on the linked page), $\frac{d}{dx} B_n(x) = \frac{B_{n+1}(x)}{x} - B_n(x)$ (Eq. 16), and $B_n(1) = \varpi(n)$ (Eq. 1). Thus

$$\sum_{k=0}^n \left\{ n \atop k\right\} k = \frac{d}{dx} \left.\sum_{k=0}^n \left\{ n \atop k\right\} x^k \right|_{x=1} = \frac{d}{dx} \left. B_n(x) \right|_{x=1} = \frac{B_{n+1}(1)}{1} - B_n(1) = \varpi(n+1) - \varpi(n).$$

Third: Use the double generating function for the Stirling numbers of the second kind (see, for example, Concrete Mathematics, 2nd edition, p. 351) $$\sum_{n,k \geq 0} \left\{ n \atop k\right\} w^k \frac{z^n}{n!} = e^{w(e^z-1)}.$$ (The right-hand side is actually the exponential generating function for the Bell polynomials, so this derivation is a variation on the second one.) Differentiating both sides with respect to $w$ and then letting $w = 1$ yields the exponential generating function (egf) for the sum in question: $$\sum_{n \geq 0} \left(\sum_{k=0}^n \left\{ n \atop k\right\} k \right) \frac{z^n}{n!} = e^{e^z-1} e^z - e^{e^z-1}.$$

It is known that $e^{e^z-1}$ is the egf for the Bell numbers. Since $e^z$ is the egf of the infinite sequence of $1$'s, and multiplication of exponential generating functions corresponds to binomial convolutions of the sequences in question, this means

$$\sum_{k=0}^n \left\{ n \atop k\right\} k = \sum_{k=0}^n \binom{n}{k} \varpi(k) - \varpi(n).$$ Finally, $\sum_{k=0}^n \binom{n}{k} \varpi(k) = \varpi(n+1)$ is a well-known identity for the Bell numbers, so we have $$\sum_{k=0}^n \left\{ n \atop k\right\} k = \varpi(n+1) - \varpi(n).$$

Added much later:

Fourth: A combinatorial argument. The Stirling number $\left\{ n \atop k \right\}$ counts the number of ways to partition a set of $n$ elements into $k$ nonempty subsets, and the Bell number $\varpi(n)$ is the number of ways to partition a set of $n$ elements into any number of subsets. Thus $k \left\{ n \atop k \right\}$ is the number of ways to partition $n$ elements into $k$ nonempty subsets and then add an element $n+1$ to one of these $k$ subsets. Summing over all values of $k$ would then give the number of ways to partition a set of $n+1$ elements into any number of nonempty subsets, except for the partitions in which element $n+1$ is in a subset by itself. But this number is $\varpi(n+1) - \varpi(n)$, as the number of partitions of $n+1$ elements in which $n+1$ is in a subset by itself is the same as the number of partitions of $n$ elements. Putting all this together, we get $$\sum_{k=0}^n \left\{ n \atop k\right\} k = \varpi(n+1) - \varpi(n).$$

share|cite|improve this answer
Thank you @MikeSpivey ! hope you get good reviews from the referees. – pebox11 Mar 14 '11 at 9:17
@MikeSpivey I think there is an even simpler proof of the previous identity using the recurrence of the Stirling numbers of the second kind $\left\{{n+1\atop k}\right\} = \left\{{n\atop k-1}\right\} +k \left\{{ n \atop k }\right\}$ . And this is because the right part of the recurrence contains exactly what you want to prove (you have to sum also). But I think summation is not a problem... the steps are straight forward. I wonder if your formula in your paper could work for negative $m$ in the Rao-Uppuluri-Carpenter formula (unfortunately these numbers are not defined for negative integers). T – pebox11 Apr 3 '11 at 11:34
(oops, in the conversion process pebox11's query got chopped off. Here's the end of it after the letter T). This is because what if someone would like to find $\sum_{k=0}^n \frac{S(n,k)}{k}$ ?? where $S(n,k)$ is a Stirling number of the second kind? – Willie Wong Apr 3 '11 at 12:40
@pebox11: as you can see, I've merged your duplicate account into the one you originally used to ask this question. Please consider registering your account: it makes it more 'portable' so that such account duplication can be avoided in the future. I've also moved your query, which is properly a comment to Mike's answer, to here. – Willie Wong Apr 3 '11 at 12:42
@pebox11: You're absolutely right; that's a much simpler proof. I'm not sure about the $m = -1$ case; perhaps the RUC numbers could be generalized to negative values of $m$. – Mike Spivey Apr 4 '11 at 16:34

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.