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]$](abs/img2.gif)
. 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$](abs/img3.gif)
,
![$ \beta = \beta' = 0$](abs/img4.gif)
, and
![$ \frac{\alpha}{\beta} = \frac{\alpha'}{\beta} +1$](abs/img5.gif)
, adding to the result
of Neuwirth on the case
![$ \alpha' = 0$](abs/img6.gif)
. 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$](abs/img7.gif)
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.
Received October 18 2010;
revised version received October 19 2011.
Published in Journal of Integer Sequences, November 21 2011.