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:

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.
Advertisements
This entry was posted in combinatorics, recurrence relations. Bookmark the permalink.

One Response to Solving Two-Term Combinatorial Recurrence Relations

  1. Pingback: Solving Two-Term Combinatorial Recurrence Relations, Part II | A Narrow Margin

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s