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

Question

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!

Answer 1

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