Many named combinatorial numbers satisfy the following general two-term combinatorial recurrence relation:
- Binomial coefficients:
- Stirling cycle numbers:
- Stirling subset numbers:
- Lah numbers:
- Eulerian numbers:
- Second-order Eulerian numbers:
It is not known how to solve the recurrence in general. In fact, research problem 6.94 in Concrete Mathematics  is to develop a general theory of solutions to the recurrence. (Update: See my May 13, 2014, post on Barbero, Salas, and Villaseñor’s paper, in which they find a complete solution to the recurrence in terms of exponential generating functions.)
Partial results are known, however – some of which I recently published . In this post I’ll summarize the main results from that paper.
Theorem 1 (the case ):
are the Stirling cycle and subset numbers, respectively. (This theorem was first proved by Neuwirth .)
Theorem 2 (the case ):
Theorem 3 (the case ):
If , then the solution to
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
- Erich Neuwirth, “Recursively defined combinatorial functions: extending Galton’s board,” Discrete Mathematics 239, pp. 33-51, 2001.
- Michael Z. Spivey, “On solutions to a general combinatorial recurrence,” Journal of Integer Sequences 14 (9): Article 11.9.7, 2011.