Take the 2-minute tour ×
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.

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|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
add comment

1 Answer

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

share|improve this answer
    
Thank you @MikeSpivey ! hope you get good reviews from the referees. –  pebox11 Mar 14 '11 at 9:17
1  
@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
show 1 more comment

Your Answer

 
discard

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.