# Formula for $\sum_{k=0}^n S(n,k) k$, where $S(n,k)$ is a Stirling number of the second kind?

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!

-
This is not a convolution. The convolution would be $\sum_{k=0}^n kS(n,n-k)$. – joriki Mar 13 '11 at 19:33

$$\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).$$

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).$$
@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: 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