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

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.

$$\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?

• Oh, yes! Many thanks for closing this blind spot! :-) – Markus Scheuer Jun 3 '17 at 19:43
• @Markus No problem. – Matt Samuel Jun 3 '17 at 19:44

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.

• Please note that here I was explicitly asking for a recurrence relation of Stirling numbers of the second kind derived from generating functions. Currently this answer is of no help at all. Maybe you can (substantially) rewrite it and provide something appropriate similarly to the post from Matt Samuel. – Markus Scheuer May 18 '18 at 9:19
• It should provide you with a method to find a recurrence for the Stirling numbers of the second kind... These are denoted both in the bracket notation and by $S(n, k)$ above. It appears that you need to think harder about what I wrote. And the problem for the Stirling numbers of the first kind is relevant since they also share a very similar looking triangular recurrence relation. – mds May 18 '18 at 23:49
• In particular, using the homogeneous symmetric polynomial method, you can see that $S(n, k) = h_{n-k}(1,2,\ldots,k)$. Now by the OGF for the Stirling numbers of the second kind I have written above, we can see that there is a recursion: $$h_{n-k}(1,\ldots,k) = \sum_{m=0}^{n-k} k^m h_{n-k-m}(1,2,\ldots,k-1).$$ Now if you fiddle with the coefficients, we obtain that the right-hand-side sum can only have $m=0,1$ to make sense in this definition. This implies the recurrence relation. Does that make sense? – mds May 19 '18 at 0:41
• Additionally, the last identity I gave for the Stirling numbers of the second kind can be combined with a Norlund-Rice integral to give you the OGF for the Stirling numbers. This in turn provides the recurrence relation as above. – mds May 24 '18 at 21:39