Stirling numbers of the second kind: How to obtain a recurrence relation from a generating function?

Question

The Stirling numbers of the second kind ${n\brace k}$ are the number of distributions of $n$ distinct balls into $k$ non-empty, indistinguishible boxes.

These numbers have besides some other interesting representations via generating functions the `vertical' GF \begin{align*} \sum_{n=k}^\infty {n\brace k}\frac{t^n}{n!}=\frac{1}{k!}(e^t-1)^k\qquad\qquad k\geq 0 \end{align*} A corresponding bivariate GF is \begin{align*} \sum_{k=0}^\infty\sum_{n=k}^\infty {n\brace k}\frac{t^n}{n!}u^k=\exp(u(e^t-1))\qquad\qquad \end{align*}

On the other hand there is the well known recurrence relation \begin{align*} {n\brace k}&=k{n-1\brace k}+{n-1\brace k-1}\qquad\qquad n,k\geq 1\tag{1}\\ {n\brace 0}&={0\brace k}=0\qquad\text{except }{0\brace 0}=1 \end{align*}

Note: A thorough treatment of Stirling numbers can be found e.g. in chapter 5 of Advanced Combinatorics by L. Comtet which also provides two proofs of the recurrence relation, a combinatorial one and an algebraic one based upon another generating function.

Since the information of the recurrence relation (1) is also encoded in the generating functions stated above, I've tried to derive it from them. Yet, I was not successful up to now.

So, any help to derive the recurrence relation from one of the generating functions above is highly appreciated.

Answer 1

$$\frac d{dt}\frac1{k!}(e^t-1)^k=\frac1{(k-1)!}(e^t-1)^{k-1}e^t=k(\frac1{k!}(e^t-1)^k)+\frac1{(k-1)!}(e^t-1)^{k-1}$$ Can you derive it from this?

Answer 2

I realize that this is a little late to help the original author, but for someone else who finds this post and doesn't like to work with seemingly adhoc derivative formulas on the sequence generating function, I think there are a couple of better approaches you could try.

RE: References I'd also like to point out that the treatment of the Stirling numbers of both kinds found in Concrete Mathematics is better and a little more modern that Comtet's book (which is still good). There's also another good publication that you can get access to if you have a university subscription by Mansour called Commutation Relations, Normal Ordering, and Stirling Numbers. It's too pricey for me to recommend if you can't get free access to it, but it does nonetheless have a pretty thorough treatment of Stirling number identities.

Approaches via symmetric polynomials This especially applies to the Stirling numbers of the first kind which can be generated exactly by elementary symmetric polynomials of the form $$|s(n,k)| = [x^k] x \cdot \prod_{i=1}^{n} (1+x/i).$$ These coefficients then inherit a plethora of immediate identities from this structure as given in Macdonald's book on symmetric functions. This form should also make finding a triangular recurrence relation for this Stirling number variant very, very easy. You can read more about generalizations in this recent article for reference.

Now onto the Stirling numbers of the second kind. An ordinary generating function for this triangle is given (for example, in Section 7.4 of Concrete Mathematica) as $$\sum_{n \geq 0} S(n, k) z^n = \frac{z^k}{(1-z)(1-2z)\cdots(1-kz)}.$$ Notice here that in this case the sequence is enumerated exactly in terms of expansions of the incomplete homeogeneous symmetric polynomials (see Wikipedia's reference on these). I would have to imagine that this should help you to get a more combinatorially motivated proof of the triangular recurrence relation you stated above.

Other summation identities In either case, you should get exact summation formulas for these triangles in one of the two following forms: $$\sum_{m=1}^{n} \binom{n}{m} (-1)^{n-m} / m^{k},$$ or in the second kind case as, $$\left\{ {n \atop k}\right\} = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n.$$ These sums should also suggest recurrence relations directly without needing to perform operations on their corresponding generating functions.

Hope that helps someone.