Journal of Integer Sequences, Vol. 14 (2011), Article 11.9.7

On Solutions to a General Combinatorial Recurrence

Michael Z. Spivey
Department of Mathematics and Computer Science
University of Puget Sound
Tacoma, Washington 98416-1043


We develop techniques that can be applied to find solutions to the recurrence $ \genfrac{\vert}{\vert}{0pt}{}{n}{k} = (\alpha n + \beta k + \gamma) \genfrac{\...
...lpha' n + \beta' k + \gamma') \genfrac{\vert}{\vert}{0pt}{}{n-1}{k-1} + [n=k=0]$. Many interesting combinatorial numbers, such as binomial coefficients, both kinds of Stirling and associated Stirling numbers, Lah numbers, Eulerian numbers, and second-order Eulerian numbers, satisfy special cases of this recurrence. Our techniques yield explicit expressions in the instances $ \alpha = -\beta$, $ \beta = \beta' = 0$, and $ \frac{\alpha}{\beta} = \frac{\alpha'}{\beta} +1$, adding to the result of Neuwirth on the case $ \alpha' = 0$. Our approach employs finite differences, continuing work of the author on using finite differences to study combinatorial numbers satisfying simple recurrences. We also find expressions for the power sum $ \sum_{j=0}^n \genfrac{\vert}{\vert}{0pt}{}{n}{j} j^m$ for some special cases of the recurrence, and we prove some apparently new identities involving Stirling numbers of the second kind, Bell numbers, Rao-Uppuluri-Carpenter numbers, second-order Eulerian numbers, and both kinds of associated Stirling numbers.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000110 A000587 A007318 A008275 A008277 A008292 A008297 A008299 A008306 A008517 A021009 A094587 A094638 A131689.)

Received October 18 2010; revised version received October 19 2011. Published in Journal of Integer Sequences, November 21 2011.

Return to Journal of Integer Sequences home page