[Math] Stirling numbers of the second kind $S (r,k)$ – does one ever sum over $r$

combinatoricsstirling-numbers

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.

Best Answer

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

A good reference is Chapter 8 of Charalambides' Enumerative Combinatorics.

Related Question