Solving Two-Term Combinatorial Recurrence Relations, Part II

A few years ago I published a paper [2] giving a partial answer to the following question in Graham, Knuth, and Patashnik’s Concrete Mathematics (Problem 6.92):

Develop a general theory of the solutions to the two-parameter recurrence

\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].

A post from a few years ago discusses the results in my paper.  I also asked a question on Math Overflow (my first MO question!) asking for other known results.

Well, a recent paper by Barbero, Salas, and Villaseñor, “Bivariate Generating Functions for a Class of Linear Recurrences: General Structure” [1], gives a complete solution to this recurrence in the form of exponential generating functions.  I’m not going to try to summarize their paper here, as it’s too technical, although I will mention that they do have to break the recurrence into cases to obtain their results.  (Given my earlier work on the problem this does not surprise me.)  If you’re interested, take a look.  They do some very nice work to get their results.


References

1.  Barbero, Salas, and Villaseñor, “Bivariate Generating Functions for a Class of Linear Recurrences: General Structure,” Journal of Combinatorial Theory, Series A, 125 (2014) 146-165.

2.  Spivey, Michael Z.,  “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, Part II

  1. Pingback: Solving Two-Term Combinatorial Recurrence Relations | 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