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.

  • 1
    $\begingroup$ 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.) $\endgroup$ – Qiaochu Yuan Jan 27 '11 at 20:36
  • $\begingroup$ 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). $\endgroup$ – Gottfried Helms Jan 27 '11 at 20:39
  • $\begingroup$ 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! $\endgroup$ – pebox11 Mar 13 '11 at 18:50
  • $\begingroup$ @par: you are better off posing this as a new question than as a comment on an existing one. $\endgroup$ – 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}}$.

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

  • $\begingroup$ Thanks you for the very nice anwser! I'll be sure to check out that book. $\endgroup$ – milcak Jan 28 '11 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.