4
$\begingroup$

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.

  • 0
    @par: $y$ou are better off posing this as a new question than as a comment on an existing one.2011-03-13

1 Answers 1

10

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.

  • 0
    Thanks you for the very nice anwser! I'll be sure to check out that book.2011-01-28