# Stirling numbers of the second kind $S (r,k)$ - does one ever sum over $r$?

A Stirling number of the second kind, $S (r,k)$, is defined to be the number of ways one can partition an $r$-element set into $k$ subsets.

Consider the following problem:

You have $r$ distinguishable balls and $n$ undistinguishable boxes. If you are allowed to place balls into these boxes with no restrictions, how many different ways of doing so are there?

The anwser is $\sum_{k=1}^{n} S (r,k)$.

You can nicely use this model for many combinatorial problems.

I would like to ask if anyone has seen, or knows of a problem where one would sum over $r$ instead, i.e. where something like $\sum_{k=i}^{j} S (k,n)$ would appear.

This just a general interest question; it came up in a combinatorial methods class. Many thanks for any anwsers/comments.

-
Sure: it's the number of ways to place an unspecified number of distinguishable balls from i to j into n non-empty indistinguishable boxes. (You need this constraint in your definition.) –  Qiaochu Yuan Jan 27 '11 at 20:36
not a combinatorical relation; but since the Stirlingnumbers can be described by a finite composition of powers (or binomials?) one can define divergent sums and assign (hopefully) meaningfully values. (But don't know whether this matters here at your question, so I keep this just a short comment so far). –  Gottfried Helms Jan 27 '11 at 20:39
@Qiaochu Oh very nice! Thanks a lot. –  milcak Jan 27 '11 at 20:42
Any idea on what is the sum of k*S(n,k) over k from k=0 to k=n? it is the convolution of the stirling numbers of the second kind with the integers. thank you! –  pebox11 Mar 13 '11 at 18:50
@par: you are better off posing this as a new question than as a comment on an existing one. –  Willie Wong Mar 13 '11 at 19:15

There are actually lots of interesting uses of the column sums of the Stirling numbers of the second kind $\left\{ n \atop k\right\}$. The ordinary and exponential generating functions both have nice forms (nicer than those for the row sums): $$\sum_{n=k}^{\infty} \left\{ n \atop k\right\} x^n = x^k \prod_{j=1}^k \frac{1}{1-jx},$$ $$\sum_{n=k}^{\infty} \left\{ n \atop k\right\} \frac{x^n}{n!} = \frac{(e^x-1)^k}{k!}.$$ These can be used to prove various identities involving $\left\{ n \atop k\right\}$.
Multiplying $\left\{ n \atop k\right\}$ by certain other interesting numbers before summing also yields some nice identities, such as these: $$\sum_{r=k}^n \binom{n}{r} \left\{ r \atop k\right\} = \left\{ n+1 \atop k+1\right\},$$ $$\sum_{r=k}^n k^{n-r} \left\{ r-1 \atop k-1\right\} = \left\{ n \atop k\right\},$$ $$\sum_{r=k}^n \left[ n \atop r\right] \left\{ r \atop k\right\} = \binom{n}{k} \frac{(n-1)!}{(k-1)!} = L(n,k),$$ where $L(n,k)$ is a Lah number. (Lah numbers also show up in the answer to this recent question: $n$th derivative of $e^{1/x}$).
Column $k$ is also used to convert reciprocal falling factorial powers $x^{\underline{-k}}$ to ordinary reciprocal powers $x^{-n}$ via $$x^{\underline{-k}} = \sum_{n=k}^{\infty} (-1)^{n-k} \left\{ n \atop k\right\} \frac{1}{x^n},$$ in a sort of inverse to the fact that row $k$ is used to convert ordinary powers $x^n$ to falling powers $x^{\underline{k}}$.