## Solving Two-Term Combinatorial Recurrence Relations

Many named combinatorial numbers satisfy the following general two-term combinatorial recurrence relation:

$\displaystyle \left| n \atop k \right| = (\alpha n + \beta k + \gamma) \left| n-1 \atop k \right| + (\alpha' n + \beta' k + \gamma') \left| n-1 \atop k-1 \right| + [n=k=0].$

For example:

• Binomial coefficients: $(\alpha, \beta, \gamma; \alpha', \beta', \gamma') = (0,0,1;0,0,1)$
• Stirling cycle numbers: $(1,0,-1;0,0,1)$
• Stirling subset numbers: $(0,1,0;0,0,1)$
• Lah numbers: $(1,1,-1;0,0,1)$
• Eulerian numbers: $(0,1,1;1,-1,0)$
• Second-order Eulerian numbers: $(0,1,1;2,-1,-1)$

It is not known how to solve the recurrence in general.  In fact, research problem 6.94 in Concrete Mathematics [1] 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 [3].  In this post I’ll summarize the main results from that paper.

Theorem 1 (the case $\alpha' = 0$):

If $\displaystyle \left| n \atop k \right| = (\alpha (n-1) + \beta k + \gamma) \left| n-1 \atop k \right| + (\beta' k + \gamma') \left| n-1 \atop k-1 \right| + [n=k=0]$

then

$\displaystyle \left| n \atop k \right| = \prod_{i=1}^k (\beta' i + \gamma') \sum_{i=0}^n \sum_{j=0}^n \left[ n \atop i \right] \binom{i}{j} \left\{ j \atop k \right\} \alpha^{n-i} \beta^{j-k} \gamma^{i-j}$

where

$\displaystyle \left[ n \atop i \right], \left\{ n \atop k \right\}$

are the Stirling cycle and subset numbers, respectively.  (This theorem was first proved by Neuwirth [2].)

Theorem 2 (the case $\beta = - \alpha$):

If $\displaystyle \left| n \atop k \right| = (\alpha n - \alpha k + \gamma) \left| n-1 \atop k \right| +(\alpha'(n-1) + \beta'(k-1) + \gamma') \left| n-1 \atop k-1 \right| + [n=k=0]$

then

$\displaystyle \left| n \atop k \right| = \prod_{i=1}^{n-k} (\alpha i + \gamma) \sum_{i=0}^n \sum_{j=0}^n \left[ n \atop i \right] \binom{i}{j} \left\{ j \atop n-k \right\} (\alpha' + \beta')^{n-i} (-\beta)^{j+k-n} (\gamma')^{i-j}.$

Theorem 3 (the case $\beta = \beta' = 0$):

If $\alpha' \neq 0$ and $\displaystyle \left| n \atop k \right| = (\alpha (n-1) + \gamma) \left| n-1 \atop k \right| +(\alpha'(n-1) + \gamma') \left| n-1 \atop k-1 \right| + [n=k=0]$

then

$\displaystyle \left|n \atop k \right| = \sum_{i=0}^n \sum_{j=0}^n \left[ n \atop i \right] \binom{i}{n-j} \binom{j}{k} \alpha^{j-k} (\gamma \alpha' - \alpha \gamma')^{n-j} (\alpha')^{k-i} (\gamma')^{i+j-n}.$

Theorem 4:

If $\frac{\alpha}{\beta} = \frac{\alpha'}{\beta'} + 1$, then the solution to

$\displaystyle \left| n \atop k \right| = (\alpha (n-1) + \beta k + \gamma) \left| n-1 \atop k \right| +(\alpha'(n-1) + \beta'(k-1) + \gamma') \left| n-1 \atop k-1 \right| + [n=k=0]$

is

$\displaystyle \left| n \atop k \right| = \sum_{l=0}^n \left(\prod_{i=1}^{n-l} \left(-i+1 - \frac{\gamma}{\beta} + \frac{\gamma'}{\beta'} \right) \right) \binom{l}{k} \left( \sum_{i=0}^n \sum_{j=0}^n \left[ n \atop i \right] \binom{i}{j} \left\{ j \atop n-l \right\} (-1)^j \alpha^{n-i} \beta^{i-k} \left(\beta' \right)^{j+k-i} \left(\gamma' \right)^{i-j} \right).$

References

1. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
2. Erich Neuwirth, “Recursively defined combinatorial functions: extending Galton’s board,” Discrete Mathematics 239, pp. 33-51, 2001.
3. Michael Z. Spivey, “On solutions to a general combinatorial recurrence,” Journal of Integer Sequences 14 (9): Article 11.9.7, 2011.