On Solutions to a

General Combinatorial Recurrence

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

                mspivey@pugetsound.edu

Abstract

We develop techniques that can be applied to find solutions to the recurrence |_{k}^{n}| = (αn + βk + γ)|_{k}^{n−1}| + (α′n + β′k + γ′)|_{k−1}^{n−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 α = −β, β = β′ = 0, and \frac{α}{β} = \frac{α′}{β} + 1, adding to the result of Neuwirth on the case α′ = 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 ∑_{j=0}^{n} |_{j}^{n}|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.

1 Introduction

Graham, Knuth, and Patashnik give the following open problem in Concrete Mathematics [5, p. 319, Problem 6.94]:

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

|{n \atop k}| = (αn+βk+γ)|{n − 1 \atop k}|+(α′n+β′k+γ′)|{n − 1 \atop k − 1}|+[n = k = 0], for n, k ≥ 0, (1)

assuming that |_{k}^{n}| = 0 when n < 0 or k < 0. What special values (α, β, γ, α′, β′, γ′) yield “fundamental solutions” in terms of which the general solution can be expressed?

Many numbers of combinatorial interest satisfy recurrences of the form (1). These include binomial coefficients (\underline{A007318}), both kinds of Stirling numbers (\underline{A008275}, \underline{A008277}), Lah numbers (\underline{A008297}), Eulerian numbers (\underline{A008292}), second-order Eulerian numbers (\underline{A008517}), and even the two kinds of associated Stirling numbers (\underline{A008306}, \underline{A008299}).

Perhaps the most general result thus far on solutions to (1) is due to Neuwirth [7]. He proves that if α′ = 0 then

|{n \atop k}| = ∏_{i=1}^{k}(β′i + γ′) ∑_{i=0}^{n} ∑_{j=0}^{n} \left[{n \atop i}\right]\binom{i}{j}\left\{{j \atop k}\right\}α^{n−i}(γ − α)^{i−j}β^{j−k},  (2)

so that the solution to (1) can be expressed as a double sum involving binomial coefficients, both kinds of Stirling numbers, and generalized factorials. Moreover, for several special cases, such as γ = 2α or γ −α = β, this expression simplifies to a single sum or even a closed form. Neuwirth uses what he calls Galton arrays, infinite triangular matrices whose entries are the |_{k}^{n}| values for recurrences of type (1). This matrix form leads to some new insights, particularly with representing solutions to (1) in terms of solutions to simpler recurrences of the same type (1). This, in fact, is Neuwirth’s approach for deriving Equation (2).

Regev and Roichman [9] also obtain Neuwirth’s result (2) in the presence of the additional restriction β′ = 0, and they show how special cases of the resulting solutions are related to certain statistics on colored permutations. Other expressions for the solution to (1) are obtained in the case β = γ′ = 1, γ = α′ = β′ = 0 by Mijajlović and Marković [6] and by Cakić [1]. Generating functions can also, of course, be used to solve many recurrences of type (1). In fact, Graham, Knuth, and Patashnik themselves suggest an investigation of the generating function ∑_{m,n≥0} |_{m}^{m+n}|w^{m}z^{n} [5, p. 564]. Thus far, though, the work on finding general solutions to the recurrence (1) has not primarily involved generating functions.

The main purpose of this paper is to extend the results of Neuwirth on recurrences of type (1). We prove some basic results that can be used to solve simple instances of (1). We then find expressions for the solution to (1) for the cases α = −β, β = β′ = 0, and \frac{α}{β} = \frac{α′}{β′} +1. The formulas we develop can be used in other cases as well, but we get explicit answers in these instances. All of the expressions involve, as with Neuwirth’s result (2), nothing more than binomial coefficients, the two kinds of Stirling numbers, and generalized factorials. For the cases we consider, then, these numbers are the “fundamental solutions” requested by Graham, Knuth, and Patashnik. We also use our formulas to give short derivations of some known combinatorial identities and to prove some apparently new ones involving Stirling numbers of the second kind (\underline{A008277}), Bell numbers (\underline{A000110}), Rao-Uppuluri-Carpenter numbers (\underline{A000587}), second-order Eulerian numbers (\underline{A008517}), and both kinds of associated Stirling numbers (\underline{A008306}, \underline{A008299}).

Our method entails deriving an expression relating the sum ∑_{j=0}^{n} |_{j}^{n}|f(j, m) to the sum ∑_{j=0}^{n} |_{j}^{n}|Δ_{j}f(j, m), where |_{k}^{n}| satisfies a recurrence of type (1) and Δ_{j}f(j, m) = f(j +1, m)− f(j, m), the partial finite difference of f with respect to j. This formula is most useful when f(n, k) = ∥_{k}^{n}∥, another solution to the recurrence (1). In particular, by a judicious choice of the parameters involved, the sum ∑_{j=0}^{n} |_{j}^{n}|∥_{k}^{j}∥ can itself be a solution to a recurrence of type (1). In these cases, then, we can “factor” a recurrence of type (1) into two simpler recurrences that are easier to solve, as does Neuwirth [7]. The choice of ∥_{k}^{n}∥ = \binom{n}{k} is particularly helpful because it allows nearly any |_{k}^{n}| satisfying (1) to be so factored. Working with finite differences is not as clean as the matrix approach of Neuwirth, but the additional level of detail enables us to find explicit expressions for some classes of recurrences of type (1) that Neuwirth does not. (We note, however, that our paper does not completely avoid matrices or generating functions. There is an implicit matrix inversion in the inverse relation (8), which is used in Theorem 18 and in several examples in Section 4. We also use generating functions in the proofs of Identities 24 and 25.)

This approach relating ∑_{j=0}^{n} |_{j}^{n}|f(j) and ∑_{j=0}^{n} |_{j}^{n}|Δ_{j}f(j) was also used extensively in previous work [11] of the author, usually to find an expression for the power sum ∑_{j=0}^{n} |_{j}^{n}|j^{m}, where |_{k}^{n}| generally satisfied certain special cases of recurrence (1). However, the formulas presented there can only handle some cases in which β = β′ = 0. A secondary purpose of this paper, then, is to develop methods for finding the power sum in which β and β′ are not both zero. Our result for ∑_{j=0}^{n} |_{j}^{n}|\binom{j}{m} turns out to be key. As examples, we obtain expressions for the power sums ∑_{j=0}^{n} \left⟨{n \atop j}\right⟩j^{m}, ∑_{j=0}^{n}⟨⟨{n \atop j}⟩⟩j^{m}, ∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m}, and ∑_{j=0}^{n} \left\{{n \atop j}\right\}(−1)^{j}j^{m}, where \left⟨{n \atop k}\right⟩ is an Eulerian number (\underline{A008292}), \begin{aligned}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{aligned} is a second-order Eulerian number (\underline{A008517}), and \left\{{n \atop k}\right\} is a Stirling number of the second kind (\underline{A008277}). The first of these four expressions is easily derivable from a known identity involving Eulerian numbers, but the other three appear to be new.

In Section 2 we present some basic results on recurrences of type (1). In Section 3 we give our formula relating ∑_{j=0}^{n} |_{j}^{n}|f(j, m) and ∑_{j=0}^{n} |_{j}^{n}|Δ_{j}f(j, m), and we use this formula to derive expressions for the solution to (1) in the cases α = −β and β = β′ = 0. Section 4 contains our formula for the important special case f(j, m) = \binom{j}{m}. We use this formula to

1. give a short derivation of a known identity involving Eulerian numbers (\underline{A008292}),

2. find apparently new expressions containing second-order Eulerian numbers (\underline{A008517}) and both kinds of associated Stirling numbers (\underline{A008306}, \underline{A008299}), and

3. derive an expression for the solution to (1) in the case \frac{α}{β} = \frac{α′}{β′} + 1.

Finally, in Section 5 we apply our formula for the case f(j, m) = \binom{j}{m} to find expressions for the power sums for \left⟨{n \atop k}\right⟩, \begin{aligned}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{aligned}, \left\{{n \atop k}\right\}, and \left\{{n \atop k}\right\}(−1)^{k}.

In most instances we find it easier to work with slight variations of the recurrence (1) rather than the form in which we first stated it. In particular, the formulas are often cleaner if the coefficients α, α′, and β′ are applied to factors n − 1, n − 1, and k − 1, respectively, instead of n, n, and k. For notational simplicity we also assume that |_{k}^{n}| = 0 when n < 0 or k < 0 and that recurrence relations hold only for n, k ≥ 0. In addition, we take 0^{0} to be 1.

2 Basic results

In this section we present a handful of results on recurrences of the form (1). These results can be used to solve some simpler recurrences of this type.

First, we have the following. Theorem 1. Suppose ∥_{k}^{n}∥ = f_{1}(n, k)∥_{k}^{n−1}∥+f_{2}(n, k)∥_{k−1}^{n−1}∥+[n = k = 0] and |_{k}^{n}| = h(n)g_{1}(n− k)f_{1}(n, k)|_{k}^{n−1}| + h(n)g_{2}(k)f_{2}(n, k)|_{k−1}^{n−1}| + [n = k = 0]. Then

|{n \atop k}| = (∏_{j=1}^{n} h(j)) (∏_{j=1}^{n−k} g_{1}(j)) (∏_{j=1}^{k} g_{2}(j)) ∥{n \atop k}∥.  (3)

Proof. Equation (3) is clearly true in the case n = k = 0. Otherwise,

h(n)g_{1}(n − k)f_{1}(n, k) (∏_{j=1}^{n−1} h(j)) ( ∏_{j=1}^{n−1−k} g_{1}(j)) (∏_{j=1}^{k} g_{2}(j)) ∥{n − 1 \atop k}∥

+ h(n)g_{2}(k)f_{2}(n, k) (∏_{j=1}^{n−1} h(j)) (∏_{j=1}^{n−k} g_{1}(j)) (∏_{j=1}^{k−1} g_{2}(j)) ∥{n − 1 \atop k − 1}∥

= (∏_{j=1}^{n} h(j)) (∏_{j=1}^{n−k} g_{1}(j)) (∏_{j=1}^{k} g_{2}(j)) f_{1}(n, k)∥{n − 1 \atop k}∥

+ (∏_{j=1}^{n} h(j)) (∏_{j=1}^{n−k} g_{1}(j)) (∏_{j=1}^{k} g_{2}(j)) f_{2}(n, k)∥{n − 1 \atop k − 1}∥

= (∏_{j=1}^{n} h(j)) (∏_{j=1}^{n−k} g_{1}(j)) (∏_{j=1}^{k} g_{2}(j)) ∥{n \atop k}∥.

Since the right-hand side of Equation (3) satisfies the recurrence for |_{k}^{n}|, the theorem holds.

The following corollary contains the most commonly-used special cases of Theorem 1. Corollary 2. Let c be a constant. Suppose ∥_{k}^{n}∥ = f_{1}(n, k)∥_{k}^{n−1}∥+f_{2}(n, k)∥_{k−1}^{n−1}∥+[n = k = 0].

1. If |_{k}^{n}| = cf_{1}(n, k)|_{k}^{n−1}| + f_{2}(n, k)|_{k−1}^{n−1}| + [n = k = 0] then |_{k}^{n}| = ∥_{k}^{n}∥c^{n−k}.

2. If |_{k}^{n}| = f_{1}(n, k)|_{k}^{n−1}| + cf_{2}(n, k)|_{k−1}^{n−1}| + [n = k = 0] then |_{k}^{n}| = ∥_{k}^{n}∥c^{k}.

3. If |_{k}^{n}| = (n − k)f_{1}(n, k)|_{k}^{n−1}| + f_{2}(n, k)|_{k−1}^{n−1}| + [n = k = 0] then |_{k}^{n}| = ∥_{k}^{n}∥(n − k)!.

4. If |_{k}^{n}| = f_{1}(n, k)|_{k}^{n−1}| + kf_{2}(n, k)|_{k−1}^{n−1}| + [n = k = 0] then |_{k}^{n}| = ∥_{k}^{n}∥k!.

5. If |_{k}^{n}| = nf_{1}(n, k)|_{k}^{n−1}| + nf_{2}(n, k)|_{k−1}^{n−1}| + [n = k = 0] then |_{k}^{n}| = ∥_{k}^{n}∥n!.

The following theorem shows how to swap the coefficient functions of |_{k}^{n−1}| and |_{k−1}^{n−1}|. It is easy to prove but quite important, as we use it in all of our major theorems that give solutions to (1).

Theorem 3. Suppose ∥_{k}^{n}∥ = f_{1}(n, k)∥_{k}^{n−1}∥ + f_{2}(n, k)∥_{k−1}^{n−1}∥ + [n = k = 0] and |_{k}^{n}| = f_{2}(n, n − k)|_{k}^{n−1}| + f_{1}(n, n − k)|_{k−1}^{n−1}| + [n = k = 0]. Then |_{k}^{n}| = ∥_{n−k}^{n}∥.

Proof. The theorem is clearly true in the case n = k = 0. Otherwise, we have f_{2}(n, n − k)∥_{n−1−k}^{n−1}∥ + f_{1}(n, n − k)∥_{n−k}^{n−1}∥ = ∥_{n−k}^{n}∥, completing the proof.

Since \binom{n}{k}, \left[{n \atop k}\right], and \left\{{n \atop k}\right\}, respectively, are solutions to the recurrences

|{n \atop k}| = |{n − 1 \atop k}| + |{n − 1 \atop k − 1}| + [n = k = 0],

|{n \atop k}| = (n − 1)|{n − 1 \atop k}| + |{n − 1 \atop k − 1}| + [n = k = 0],

|{n \atop k}| = k|{n − 1 \atop k}| + |{n − 1 \atop k − 1}| + [n = k = 0],

Theorems 1 and 3 allow us to solve a large number of recurrences of the form (1) almost immediately. For example, Exercise 6.17 in Concrete Mathematics [5, p. 311] asks to find the solutions to the following recurrences:

|{n \atop k}| = |{n − 1 \atop k}| + n|{n − 1 \atop k − 1}| + [n = k = 0],  (4)
|{n \atop k}| = (n − k)|{n − 1 \atop k}| + |{n − 1 \atop k − 1}| + [n = k = 0],  (5)
|{n \atop k}| = k|{n − 1 \atop k}| + k|{n − 1 \atop k − 1}| + [n = k = 0].  (6)

Corollary 2 immediately implies that the solution to (5) is |_{k}^{n}| = \binom{n}{k}(n − k)! (\underline{A094587}) and the solution to (6) is |_{k}^{n}| = \left\{{n \atop k}\right\}k! (\underline{A131689}). The solution to (4) is only slightly more difficult. Applying Theorem 3 changes the problem to finding the solution to ∥_{k}^{n}∥ = n∥_{k}^{n−1}∥ + ∥_{k−1}^{n−1}∥ + [n = k = 0]. This is almost the recurrence for \left[{n \atop k}\right], and, in fact, since \left[{n \atop 0}\right] = [n = 0], it can be easily shown that \left[{n+1 \atop k+1}\right] solves ∥_{k}^{n}∥ = n∥_{k}^{n−1}∥ + ∥_{k−1}^{n−1}∥ + [n = k = 0] (see also Theorem 6). Thus the solution to (4) is |_{k}^{n}| = \left[{n+1 \atop n+1−k}\right] (\underline{A094638}).

A somewhat more complicated example involves the recursion

|{n \atop k}| = (n + k)|{n − 1 \atop k}| + |{n − 1 \atop k − 1}| + [n = k = 0].  (7)

By Theorem 1, we can solve the recurrence (7) if we can solve

∥{n \atop k}∥ = (n − k)(n + k)∥{n − 1 \atop k}∥ + k^{2}∥{n − 1 \atop k − 1}∥ + [n = k = 0]

= (n^{2} − k^{2})∥{n − 1 \atop k}∥ + k^{2}∥{n − 1 \atop k − 1}∥ + [n = k = 0].

But, since n^{2} − k^{2} + k^{2} = n^{2}, ∥_{0}^{n}∥ = n^{2}∥_{0}^{n−1}∥ + [n = 0], and ∥_{n}^{n}∥ = n^{2}∥_{n−1}^{n−1}∥ + [n = 0], it must be the case that ∥_{k}^{n}∥ = (n!)^{2}[n ≥ k]. Thus the solution to (7) is |_{k}^{n}| = \frac{(n!)^{2}}{(n−k)!(k!)^{2}} [n ≥ k] =

\binom{n}{k}^{2}(n − k)! (\underline{A021009}).

3 Factoring with finite differences

We now develop a few results that greatly expand our ability to solve recurrences of the form (1).

Let Δ_{j}f(j, m) denote the finite difference of f(j, m) with respect to j; i.e., Δ_{j}f(j, m) = f(j + 1, m) − f(j, m). We have the following.

Theorem 4. Suppose |_{k}^{n}| = (α(n − 1) + βk + γ)|_{k}^{n−1}| + (α′(n − 1) + β′(k − 1) + γ′)|_{k−1}^{n−1}| + [n = k = 0]. Then, for n ≥ 1,

∑_{j=0}^{n} |{n \atop j}|f(j, m) = ∑_{j=0}^{n−1} |{n − 1 \atop j}| ((α + α′)(n − 1) + (β + β′)j + γ + γ′) f(j, m)

+ ∑_{j=0}^{n−1} |{n − 1 \atop j}|(α′(n − 1) + β′j + γ′)Δ_{j}f(j, m).

Proof. By definition,

∑_{j=0}^{n−1} |{n − 1 \atop j}|Δ_{j}g(n, j, m) = ∑_{j=0}^{n−1} |{n − 1 \atop j}|g(n, j + 1, m) − ∑_{j=0}^{n−1} |{n − 1 \atop j}|g(n, j, m).

Let g(n, j, m) = (α′(n − 1) + β′(j − 1) + γ′)f(j, m). Then Δ_{j}g(n, j, m) = (α′(n − 1) + β′j + γ′)Δ_{j}f(j, m) + β′f(j, m) (see, for instance, [5, p. 55]). We then have

∑_{j=0}^{n−1} |{n − 1 \atop j}|((α′(n − 1) + β′j + γ′)Δ_{j}f(j, m) + β′f(j, m))

= ∑_{j=0}^{n−1} |{n − 1 \atop j}|(α′(n − 1) + β′j + γ′)f(j + 1, m) − ∑_{j=0}^{n−1} |{n − 1 \atop j}|(α′(n − 1) + β′(j − 1) + γ′)f(j, m)

= ∑_{j=0}^{n−1} |{n \atop j + 1}|f(j + 1, m) − ∑_{j=0}^{n−1} |{n − 1 \atop j + 1}|(α(n − 1) + β(j + 1) + γ)f(j + 1, m)

− ∑_{j=0}^{n−1} |{n − 1 \atop j}|(α′(n − 1) + β′(j − 1) + γ′)f(j, m)

= ∑_{j=0}^{n} |{n \atop j}|f(j, m) − ∑_{j=0}^{n−1} |{n − 1 \atop j}|(α(n − 1) + βj + γ)f(j, m)

− ∑_{j=0}^{n−1} |{n − 1 \atop j}|(α′(n − 1) + β′(j − 1) + γ′)f(j, m)

− |{n \atop 0}|f(0, m) + |{n − 1 \atop 0}|(α(n − 1) + γ)f(0, m) − |{n − 1 \atop n}|(α(n − 1) + βn + γ)f(n, m).

Since the recursion definition implies |_{0}^{n}| = |_{0}^{n−1}|(α(n−1)+γ) and |_{n}^{n−1}| = 0, collecting terms yields the result.

The most useful values of f(j, m) in Theorem 4 for the present work are numbers ∥_{k}^{n}∥ (with j = n and m = k) themselves satisfying a recurrence of the form (1).

Corollary 5. Suppose |_{k}^{n}| = (α(n−1)+βk +γ)|_{k}^{n−1}|+(α′(n−1)+β′(k −1)+γ′)|_{k−1}^{n−1}|+[n = k = 0] and ∥_{k}^{n}∥ = (ᾱ(n − 1) + β̄k + γ̄)∥_{k}^{n−1}∥ + (¯ᾱ(n − 1) + ¯ β̄(k − 1) + ¯ γ̄)∥_{k−1}^{n−1}∥ + [n = k = 0]. Then

∑_{j=0}^{n} |{n \atop j}| ∥{j \atop k}∥ = ∑_{j=0}^{n−1} |{n − 1 \atop j}| ∥{j \atop k}∥( (α + α′ (ᾱj + β̄k + γ̄)) (n − 1)

+ (β + β′ (ᾱj + β̄k + γ̄) + γ′ᾱ) j + γ + γ′ (β̄k + γ̄) )

+ ∑_{j=0}^{n−1} |{n − 1 \atop j}| ∥{j \atop k − 1}∥(α′ (¯ᾱj + ¯ β̄(k − 1) + ¯ γ̄) (n − 1)

+ (β′ (¯ᾱj + ¯ β̄(k − 1) + ¯ γ̄) + γ′ ¯ᾱ) j + γ′ ( ¯β̄(k − 1) + ¯ γ̄) )

+ [n = k = 0].

Proof. If n = 0 then ∑_{j=0}^{n} |_{j}^{0}| ∥_{k}^{j}∥ = ∥_{k}^{0}∥ = [k = 0]. For n ≥ 1 and j ≥ 0, we have

Δ_{j}∥{j \atop k}∥ = ∥{j + 1 \atop k}∥ − ∥{j \atop k}∥

= (ᾱj + β̄k + γ̄)∥{j \atop k}∥ + (¯ᾱj + ¯ β̄(k − 1) + ¯ γ̄)∥{j \atop k − 1}∥ − ∥{j \atop k}∥

= (ᾱj + β̄k + γ̄ − 1)∥{j \atop k}∥ + (¯ᾱj + ¯ β̄(k − 1) + ¯ γ̄)∥{j \atop k − 1}∥.

Applying Theorem 4 and collecting terms yields the result.

Corollary 5 is important mainly because of special cases of α, β, γ, α′, β′, and γ′ in which all of the terms involving j vanish. Then Corollary 5 reduces to a recurrence of the form S(n, k) = f_{1}(n, k)S(n − 1, k) + f_{2}(n, k)S(n − 1, k − 1) + [n = k = 0], where S(n, k) = ∑_{j=0}^{n} |_{j}^{n}|∥_{k}^{j}∥. If, furthermore, the terms involving nk also vanish, then f_{1} and f_{2} are each linear functions of n and k, and thus we have a recurrence relation of the form (1). (Neuwirth [7] gives examples of scenarios in which this happens.) The value of these latter special cases of Corollary 5 is that they enable us to “factor” certain recurrences of the type (1) into simpler recurrences that may be solvable. In particular, when combined with Theorem 1, we can obtain the expression (2) due to Neuwirth [7] for the case α′ = 0 of recurrence (1), although we express it in a slightly different form.

Theorem 6. (Neuwirth) If |_{k}^{n}| = (α(n − 1) + βk + γ)|_{k}^{n−1}| + (β′k + γ′)|_{k−1}^{n−1}| + [n = k = 0], then

|{n \atop k}| = ∏_{i=1}^{k}(β′i + γ′) ∑_{i=0}^{n} ∑_{j=0}^{n} \left[{n \atop i}\right]\binom{i}{j}\left\{{j \atop k}\right\}α^{n−i}β^{j−k}γ^{i−j}.

Proof. By Theorem 1, |_{k}^{n}| = ∏_{i=1}^{k}(β′i + γ′)∥_{k}^{n}∥, where ∥_{k}^{n}∥ satisfies

∥{n \atop k}∥ = (α(n − 1) + βk + γ)∥{n − 1 \atop k}∥ + ∥{n − 1 \atop k − 1}∥ + [n = k = 0].

By Corollary 5, ∥_{k}^{n}∥ = ∑_{j=0}^{n} R(n, j)S(j, k), where

R(n, k) = (α(n − 1) + γ)R(n − 1, k) + R(n − 1, k − 1) + [n = k = 0],
S(n, k) = βkS(n, k) + S(n − 1, k − 1) + [n = k = 0].

By Corollary 2, S(n, k) = \left\{{n \atop k}\right\}β^{n−k}, and an expression for R(n, k) can be obtained by applying Corollary 5 again. We have R(n, k) = ∑_{i=0}^{n} T (n, i)U(i, k), where

T (n, k) = α(n − 1)T (n − 1, k) + T (n − 1, k − 1) + [n = k = 0],
U(n, k) = γU(n − 1, k) + U(n − 1, k − 1) = [n = k = 0].

By Corollary 2, T (n, k) = \left[{n \atop k}\right]α^{n−k} and U(n, k) = \binom{n}{k}γ^{n−k}.

Regev and Roichman [9] refer to solutions |_{k}^{n}| in Theorem 6 for the case β′ = 0, γ′ = 1 as binomial-Stirling numbers.

If any of α, β, or γ is zero then the following identities (see, for example, [5, p. 265]) can be used to simplify the solution in Theorem 6:

∑_{i=0}^{n} \left[{n \atop i}\right]\binom{i}{j} = \left[{n + 1 \atop j + 1}\right],

∑_{j=0}^{n} \binom{n}{j}\left\{{j \atop k}\right\} = \left\{{n + 1 \atop k + 1}\right\}.

For example, Theorem 6 gives the solution to the recurrence (7) to be

|{n \atop k}| = ∑_{i=0}^{n} ∑_{j=0}^{n} \left[{n \atop i}\right]\binom{i}{j}\left\{{j \atop k}\right\}.

Simplifying this result and comparing it with our original solution to (7) yields the following identity:

Identity 7.

\binom{n}{k}^{2}(n − k)! = ∑_{j=0}^{n} \left[{n + 1 \atop j + 1}\right]\left\{{j \atop k}\right\} = ∑_{j=0}^{n} \left[{n \atop j}\right]\left\{{j + 1 \atop k + 1}\right\}.

We can also obtain an expression for the solution to the case α = −β in the recurrence (1) by combining Theorem 3 with Theorem 6.

Theorem 8. If |_{k}^{n}| = (αn − αk + γ)|_{k}^{n−1}| + (α′(n − 1) + β′(k − 1) + γ′)|_{k−1}^{n−1}| + [n = k = 0] then

|{n \atop k}| = ∏_{i=1}^{n−k}(αi + γ) ∑_{i=0}^{n} ∑_{j=0}^{n} \left[{n \atop i}\right]\binom{i}{j}\left\{{j \atop n − k}\right\}(α′ + β′)^{n−i}(−β′)^{j+k−n}(γ′)^{i−j}.

Proof. By Theorem 3, |_{k}^{n}| = ∥_{n−k}^{n}∥, where ∥_{k}^{n}∥ satisfies the recurrence

∥{n \atop k}∥ = ((α′ + β′)(n − 1) − β′k + γ′)∥{n − 1 \atop k}∥ + (αk + γ)∥{n − 1 \atop k − 1}∥ + [n = k = 0].

Applying Theorem 6 completes the proof.

In addition, we can find an expression for the solution to (1) when β = β′ = 0, α′ ≠ 0, by going back to Corollary 5. (If α′ = 0 then we use Theorem 6 instead.)

Theorem 9. If α′ ≠ 0 and |_{k}^{n}| = (α(n − 1) + γ)|_{k}^{n−1}| + (α′(n − 1) + γ′)|_{k−1}^{n−1}| + [n = k = 0] then

|{n \atop k}| = ∑_{i=0}^{n} ∑_{j=0}^{n} \left[{n \atop i}\right]\binom{i}{n − j}\binom{j}{k}α^{j−k}(γα′ − αγ′)^{n−j}(α′)^{k−i}(γ′)^{i+j−n}.

Proof. By Corollary 5, |_{k}^{n}| = ∑_{j=0}^{n} R(n, j)S(j, k), where

R(n, k) = (γ − \frac{αγ′}{α′} ) R(n − 1, k) + (n − 1 + \frac{γ′}{α′} ) R(n − 1, k − 1) + [n = k = 0],
S(n, k) = αS(n, k) + α′S(n − 1, k − 1) + [n = k = 0].

By Corollary 2, S(n, k) = \binom{n}{k}α^{n−k}(α′)^{k}. By Theorem 3 and Corollary 2, R(n, k) = T (n, n − k)(γ − \frac{αγ′}{α′})^{n−k}, where

T (n, k) = (n − 1 + \frac{γ′}{α′} ) T (n − 1, k) + T (n − 1, k − 1) + [n = k = 0].

By Theorem 6, T (n, k) = ∑_{i=0}^{n} \left[{n \atop i}\right]\binom{i}{k}(\frac{γ′}{α′})^{i−k}.

4 An upper binomial transform

Using Theorems 6, 8, and 9 to factor a recurrence of type (1) into recurrences of simpler types is based on cases of Corollary 5 in which all nonlinear terms and terms involving j vanish. In this section we prove that for most cases letting ∥_{k}^{n}∥ = \binom{n}{k} in Corollary 5, scaling the coefficient of |_{k}^{n−1}| or |_{k−1}^{n−1}| appropriately via Corollary 2, and applying properties specific to \binom{n}{k} will also cause all nonlinear terms and terms involving j to vanish. The cases 1) α ≠ 0, β = 0, β′ ≠ 0 and 2) α′ ≠ 0, β′ = 0, β ≠ 0 are the only two for which this procedure does not work. Thus, except in these cases, the solution |_{k}^{n}| to any recurrence of type (1) produces a sum ∥_{k}^{n}∥ = ∑_{j=0}^{n} |_{j}^{n}|\binom{j}{k}, where ∥_{k}^{n}∥ satisfies another recurrence of type (1). Then the inverse relation [10, p. 45]

∥{n \atop k}∥ = ∑_{j=0}^{n} |{n \atop j}|\binom{j}{k} ⟺ |{n \atop k}| = ∑_{j=0}^{n} ∥{n \atop j}∥\binom{j}{k}(−1)^{j+k}  (8)

implies that if we can find an expression for ∥_{k}^{n}∥ then we have one for |_{k}^{n}| as well. In particular, for the case \frac{α}{β} = \frac{α′}{β′} + 1, ∥_{k}^{n}∥ can be factored using Theorem 8.

Since the expression ∑_{j=0}^{n} \binom{n}{j}a_{j} is sometimes called the binomial transform [13] the sum ∑_{j=0}^{n} |_{j}^{n}|\binom{j}{k} can be considered a kind of upper binomial transform.

Theorem 10. Suppose |_{k}^{n}| = (α(n−1)+βk +γ)|_{k}^{n−1}|+(α′(n−1)+β′(k −1)+γ′)|_{k−1}^{n−1}|+[n = k = 0]. Let ∥_{k}^{n}∥ denote the sum ∑_{j=0}^{n} |_{j}^{n}|\binom{j}{k}. Then

∥{n \atop k}∥ = (β + β′)(k + 1)∥{n − 1 \atop k + 1}∥ + ((α + α′)(n − 1) + (β + 2β′)k + γ + γ′)∥{n − 1 \atop k}∥

+ (α′(n − 1) + β′(k − 1) + γ′)∥{n − 1 \atop k − 1}∥ + [n = k = 0].

Proof. By Corollary 5,

∑_{j=0}^{n} |{n \atop j}|\binom{j}{k}

= ∑_{j=0}^{n} |{n − 1 \atop j}|\binom{j}{k}((α + α′)(n − 1) + (β + β′)j + γ + γ′)

+ ∑_{j=0}^{n} |{n − 1 \atop j}|\binom{j}{k − 1}(α′(n − 1) + β′j + γ′) + [n = k = 0]

= ∑_{j=0}^{n} |{n − 1 \atop j}|\binom{j}{k}((α + α′)(n − 1) + (β + β′)(j − k) + (β + β′)k + γ + γ′)

+ ∑_{j=0}^{n} |{n − 1 \atop j}|\binom{j}{k − 1}(α′(n − 1) + β′(j − k + 1) + β′(k − 1) + γ′) + [n = k = 0]

= (β + β′)(k + 1) ∑_{j=0}^{n} |{n − 1 \atop j}|\binom{j}{k + 1}

+ ∑_{j=0}^{n} |{n − 1 \atop j}|\binom{j}{k}((α + α′)(n − 1) + (β + 2β′)k + γ + γ′)

+ ∑_{j=0}^{n} |{n − 1 \atop j}|\binom{j}{k − 1}(α′(n − 1) + β′(k − 1) + γ′) + [n = k = 0],

where we have used the fact that (j − k)\binom{j}{k} = (k + 1)\binom{j}{k+1}. (This is easily proved by expressing \binom{j}{k} as \frac{j!}{k!(j−k)!}.)

Thus if β + β′ = 0, the choice of ∥_{k}^{j}∥ = \binom{j}{k} in Corollary 5 produces a recurrence of type (1). We state this fact formally in the following corollary.

Corollary 11. Suppose |_{k}^{n}| = (α(n−1)+βk+γ)|_{k}^{n−1}|+(α′(n−1)+β′(k−1)+γ′)|_{k−1}^{n−1}|+[n = k = 0], with β + β′ = 0. Let ∥_{k}^{n}∥ denote the sum ∑_{j=0}^{n} |_{j}^{n}|\binom{j}{k}. Then

∥{n \atop k}∥ =((α + α′)(n − 1) + β′k + γ + γ′)∥{n − 1 \atop k}∥ + (α′(n − 1) + β′(k − 1) + γ′)∥{n − 1 \atop k − 1}∥
+ [n + k = 0].

We now give a few examples illustrating Corollary 11. The first is a short derivation of two known expressions relating the Eulerian numbers \left⟨{n \atop k}\right⟩ (\underline{A008292}) and the Stirling numbers of the second kind \left\{{n \atop k}\right\} (\underline{A008277}).

Identity 12.

\left\{{n \atop k}\right\}k! = ∑_{j=0}^{n} \left⟨{n \atop j}\right⟩\binom{j}{n − k}

Identity 13.

\left⟨{n \atop k}\right⟩ = ∑_{j=0}^{n} \left\{{n \atop j}\right\}\binom{n − j}{k}(−1)^{n−j+k}j!

Proof. The Eulerian numbers satisfy the recurrence [5, p. 268]

\left⟨{n \atop k}\right⟩ = (k + 1)\left⟨{n − 1 \atop k}\right⟩ + (n − k)\left⟨{n − 1 \atop k − 1}\right⟩ + [n = k = 0].

By Corollary 11, ∥_{k}^{n}∥ = ∑_{j=0}^{n} \left⟨{n \atop j}\right⟩\binom{j}{k} satisfies ∥_{k}^{n}∥ = (n−k)∥_{k}^{n−1}∥+(n−k)∥_{k−1}^{n−1}∥+[n = k = 0]. But this recurrence is easy to solve: Corollary 2 tells us that ∥_{k}^{n}∥ = (n − k)!R(n, k), where R(n, k) satisfies

R(n, k) = R(n − 1, k) + (n − k)R(n − 1, k − 1) + [n = k = 0].

By Theorem 3, R(n, k) = \left\{{n \atop n−k}\right\}. This proves \left\{{n \atop n−k}\right\}(n − k)! = ∑_{j=0}^{n} \left⟨{n \atop j}\right⟩\binom{j}{k}. Reindexing produces Identity 12.

Applying the inverse relation (8) to Identity 12, we have \left⟨{n \atop k}\right⟩ = ∑_{j=0}^{n} \left\{{n \atop n−j}\right\}\binom{j}{k}(−1)^{j+k}(n− j)!. Reindexing yields Identity 13.

Identities 12 and 13 are stated in Graham, Knuth, and Patashnik [5, p. 269], and Identity 13 is proved in Charalambides [2, p. 519] via Eulerian polynomials.

Another example yields what are apparently new identities relating the second-order Eulerian numbers \begin{matrix}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{matrix} (\underline{A008517}) and the associated Stirling numbers of the first kind \begin{aligned}[ \\ [ & {n \atop k} & ] \\ & & ] \end{aligned} (\underline{A008306}). The second-order Eulerian numbers satisfy the recurrence [5, p. 270]

\begin{aligned}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{aligned} = (k + 1) \begin{matrix}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{matrix} + (2n − k − 1) \begin{matrix}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{matrix} + [n = k = 0],

and the associated Stirling numbers of the first kind \begin{aligned}[ \\ [ & {n \atop k} & ] \\ & & ] \end{aligned} satisfy (see, for example, Comtet [3, p. 256] or Fekete [4])

\begin{aligned}[ \\ [ & {n \atop k} & ] \\ & & ] \end{aligned} = (n − 1) \begin{matrix}[ \\ [ & {n − 1 \atop k} & ] \\ & & ] \end{matrix} + (n − 1) \begin{matrix}[ \\ [ & {n − 2 \atop k − 1} & ] \\ & & ] \end{matrix} + [n = k = 0].

We have the following.

Identity 14.

\begin{aligned}[ \\ [ & {n + k \atop k} & ] \\ & & ] \end{aligned} = ∑_{j=0}^{n} \begin{aligned}⟨ \\ ⟨ & {n \atop j} & ⟩ \\ & & ⟩ \end{aligned} \binom{j}{n − k}

Identity 15.

\begin{aligned}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{aligned} = ∑_{j=0}^{n} \begin{aligned}[ \\ [ & {n + j \atop j} & ] \\ & & ] \end{aligned} \binom{n − j}{k}(−1)^{n−j+k}

Proof. The recurrence satisfied by the associated Stirling numbers of the first kind can be converted to the form of the recurrence (1) via the transformation S_{1}(n, k) = \begin{aligned}[ \\ [ & {n+k \atop k} & ] \\ & & ] \end{aligned}, which changes diagonals of \begin{aligned}[ \\ [ & {n \atop k} & ] \\ & & ] \end{aligned} into rows of S_{1}(n, k). The numbers S_{1}(n, k) then satisfy

S_{1}(n, k) = (n + k − 1)S(n − 1, k) + (n + k − 1)S(n − 1, k − 1) + [n = k = 0]. (9)

Applying Corollary 11, we have that the sum T (n, k) = ∑_{j=0}^{n}⟨⟨{n \atop j}⟩⟩\binom{j}{k} satisfies the recurrence

T (n, k) = (2n − k − 1)T (n − 1, k) + (2n − k − 1)T (n − 1, k − 1) + [n = k = 0].

By Theorem 3, T (n, n − k) satisfies the recurrence for S_{1}(n, k). This proves Identity 14.

Replacing k with n − k in Identity 14 and applying the inverse relation (8) yields \begin{aligned}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{aligned} = ∑_{j=0}^{n}[[{2n−j \atop n−j}]]\binom{j}{k}(−1)^{j+k}. Reindexing produces Identity 15.

In many cases the restriction that β + β′ be zero does not really prevent one from using Corollary 11. This is because, thanks to Corollary 2, any recurrence of the form (1) with β ≠ 0 and β′ ≠ 0 can have the coefficient of |_{k}^{n−1}| or |_{k−1}^{n−1}| scaled so that Corollary 11 can be applied. In addition, if α = β = 0, then Corollary 2 allows for the factor β′(n − k) to be introduced to the coefficient of |_{k}^{n−1}| so that Corollary 11 can be applied. Similarly, if α′ = β′ = 0, then Corollary 2 shows that introducing the factor −βk to the coefficient of |_{k−1}^{n−1}| allows Corollary 11 to be used. We illustrate this idea by deriving an apparently new relationship between the associated Stirling numbers of the first (\underline{A008306}) and second (\underline{A008299}) kinds. The associated Stirling numbers of the second kind are denoted \begin{aligned}\{ \\ \{ & {n \atop k} & \} \\ & & \} \end{aligned} and satisfy the recurrence (see, for example, Comtet [3, p. 221–222] or Fekete [4])

\begin{aligned}\{ \\ \{ & {n \atop k} & \} \\ & & \} \end{aligned} = k \begin{aligned}\{ \\ \{ & {n − 1 \atop k} & \} \\ & & \} \end{aligned} + (n − 1) \begin{matrix}\{ \\ \{ & {n − 2 \atop k − 1} & \} \\ & & \} \end{matrix} + [n = k = 0].

Identity 16.

\begin{aligned}[ \\ [ & {n + k \atop k} & ] \\ & & ] \end{aligned} = ∑_{j=0}^{n} \begin{aligned}\{ \\ \{ & {n + j \atop j} & \} \\ & & \} \end{aligned} \binom{j − 1}{k − 1}(−1)^{n+j} + [n = k = 0]

Identity 17.

\begin{aligned}\{ \\ \{ & {n + k \atop k} & \} \\ & & \} \end{aligned} = ∑_{j=0}^{n} \begin{aligned}[ \\ [ & {n + j \atop j} & ] \\ & & ] \end{aligned} \binom{j − 1}{k − 1}(−1)^{n+j} + [n = k = 0]

Proof. As with the associated Stirling numbers of the first kind, the recurrence for the associated Stirling numbers of the second kind can be converted to the form (1) via the transformation S_{2}(n, k) = \begin{aligned}\{ \\ \{ & {n+k \atop k} & \} \\ & & \} \end{aligned}, where, as before, diagonals are changed to rows. Then the numbers S_{2}(n, k) satisfy

S_{2}(n, k) = kS_{2}(n − 1, k) + (n + k − 1)S_{2}(n − 1, k − 1) + [n = k = 0].  (10)

Moreover, we can see from the recurrence that S_{2}(n, 0) = [n = 0] and S_{2}(1, 1) = 1. Thus S′_{2}(n, k) = S_{2}(n + 1, k + 1) is also of the form (1) and, in fact, satisfies

S′_{2}(n, k) = (k + 1)S′_{2}(n, k) + (n + k + 1)S′_{2}(n, k) + [n = k = 0].

It is also the case that S_{1}(n, 0) = [n = 0] and S_{1}(1, 1) = 1; thus S′_{1}(n, k) = S_{1}(n + 1, k + 1) is of the form (1) as well, and

S′_{1}(n, k) = (n + k + 1)S′_{1}(n, k) + (n + k + 1)S′_{1}(n, k) + [n = k = 0].

By Corollaries 2 and 11 the sum T (n, k) = ∑_{j=0}^{n} S′_{2}(n, j)\binom{j}{k}(−1)^{j} satisfies

T (n, k) = (−n − k − 1)T (n − 1, k) + (−n − k − 1)T (n − 1, k − 1) + [n = k = 0].

Applying Corollary 2 again, we see that (−1)^{n} ∑_{j=0}^{n} S′_{2}(n, j)\binom{j}{k}(−1)^{j} satifies the recurrence for S′_{1}(n, k). Putting all of this together, we have, for k ≥ 0, the identity \begin{aligned}[ \\ [ & {n+k+2 \atop k+1} & ] \\ & & ] \end{aligned} = ∑_{j=0}^{n}\{\{{n+j+2 \atop j+1}\}\}\binom{j}{k}(−1)^{n+j}. Reindexing and including the boundary condition \begin{aligned}[ \\ [ & {n \atop 0} & ] \\ & & ] \end{aligned} = [n = k = 0] produces Identity 16.

By Equation (8), we also have, for k ≥ 0, \begin{aligned}\{ \\ \{ & {n+k+2 \atop k+1} & \} \\ & & \} \end{aligned} = ∑_{j=0}^{n}[[{n+j+2 \atop j+1}]]\binom{j}{k}(−1)^{n+j}. Reindexing and including the boundary condition \begin{aligned}\{ \\ \{ & {n \atop 0} & \} \\ & & \} \end{aligned} = [n = k = 0] yields Identity 17.

We also have the following more general result, which uses Corollary 11 to transform recurrences of type (1) in which \frac{α}{β} = \frac{α′}{β′} + 1 into a form in which Theorem 8 can be applied.

Theorem 18. If \frac{α}{β} = \frac{α′}{β′} + 1, then the solution to |_{k}^{n}| = (α(n − 1) + βk + γ)|_{k}^{n−1}| + (α′(n − 1) + β′(k − 1) + γ′)|_{k−1}^{n−1}| + [n = k = 0] is

|{n \atop k}| = ∑_{l=0}^{n} (∏_{i=1}^{n−l} (−i + 1 − \frac{γ}{β} + \frac{γ′}{β′} )) \binom{l}{k}

× (∑_{i=0}^{n} ∑_{j=0}^{n} \left[{n \atop i}\right]\binom{i}{j}\left\{{j \atop n − l}\right\}(−1)^{j}α^{n−i}β^{i−k} (β′)^{j+k−i} (γ′)^{i−j}) .

Proof. By Corollary 2, |_{k}^{n}| = R(n, k)(−1)^{n−k}(\frac{β}{β′})^{n−k}, where R(n, k) satisfies the recurrence

R(n, k) = (−\frac{αβ′}{β} (n − 1) − β′k − \frac{γβ′}{β} ) R(n − 1, k)
+ (α′(n − 1) + β′(k − 1) + γ′)R(n − 1, k − 1) + [n = k = 0].

Letting S(n, k) = ∑_{j=0}^{n} R(n, j)\binom{j}{k} and applying Corollary 11, we have

S(n, k) = ((α′ − \frac{αβ′}{β} ) (n − 1) + β′k + (γ′ − \frac{γβ′}{β} )) S(n − 1, k)
+ (α′(n − 1) + β′(k − 1) + γ′)S(n − 1, k − 1) + [n = k = 0].

Since, by assumption, α′ = \frac{αβ′}{β} − β′, this is the recurrence

S(n, k) = (−β′(n − 1) + β′k + (γ′ − \frac{γβ′}{β} )) S(n − 1, k)
+ (α′(n − 1) + β′(k − 1) + γ′)S(n − 1, k − 1) + [n = k = 0].

By Theorem 8,

S(n, k) = ∏_{i=1}^{n−k} (−β′i + β′ + γ′ − \frac{γβ′}{β} ) ∑_{i=0}^{n} ∑_{j=0}^{n} \left[{n \atop i}\right]\binom{i}{j}\left\{{j \atop n − k}\right\}(α′+β′)^{n−i}(−β′)^{j+k−n}(γ′)^{i−j}.

Applying Equation (8), we have

|{n \atop k}| =(−1)^{n−k} (\frac{β}{β′} )^{n−k} ∑_{l=0}^{n}(−1)^{l+k} (∏_{i=1}^{n−l} (−β′i + β′ + γ′ − \frac{γβ′}{β} )) \binom{l}{k}

× (∑_{i=0}^{n} ∑_{j=0}^{n} \left[{n \atop i}\right]\binom{i}{j}\left\{{j \atop n − l}\right\}(α′ + β′)^{n−i}(−β′)^{j+l−n}(γ′)^{i−j}) .

Since, by assumption, α′ + β′ = \frac{αβ′}{β}, simpifying this expression completes the proof.

5 Row sums and power sums

For many combinatorial numbers |_{k}^{n}| satisfying recurrence (1) the row sum ∑_{j=0}^{n} |_{j}^{n}|, or, more generally, the power sum ∑_{j=0}^{n} |_{j}^{n}|j^{m}, is of interest. In this section we discuss some consequences of our results pertaining to these quantities. Denote the power sum ∑_{j=0}^{n} |_{j}^{n}|j^{m} by S_{n}^{m}. For notational simplicity we also refer to the row sum S_{n}^{0} by S_{n}.

First, we have the following result on row sums (also proved by Neuwirth [7]).

Corollary 19. (Neuwirth) Suppose |_{k}^{n}| satisfies |_{k}^{n}| = (α(n − 1) + βk + γ)|_{k}^{n−1}| + (α′(n − 1) + β′(k − 1) + γ′)|_{k−1}^{n−1}| + [n = k = 0] and that β + β′ = 0. Then

∑_{k=0}^{n} |{n \atop k}| = ∏_{i=0}^{n−1} ((α + α′)i + γ + γ′) .

Proof. Taking k = 0 in Corollary 11 means that the row sum S_{n} satisfies the recurrence

S_{n} = ((α + α′)(n − 1) + γ + γ′)S_{n−1} + [n = 0].

The (known) row sums for several well-known combinatorial numbers are special cases of Corollary 19. Some of these are given in Table 1.

Recurrence Values

Name  Notation (α, β, γ; α′, β′, γ′)  Row Sum
Binomial coefficients  \binom{n}{k}  (0, 0, 1; 0, 0, 1)  2^{n}
Alternating binomial coefficients \binom{n}{k}(−1)^{k} (0, 0, 1; 0, 0, −1)  [n = 0]
Signed Stirling numbers, first kind  s(n, k)  (−1, 0, 0; 0, 0, 1) [n = 0] + [n = 1]
Unsigned Stirling numbers, first kind  \left[{n \atop k}\right]  (1, 0, 0; 0, 0, 1)  n!
Eulerian numbers  \left⟨{n \atop k}\right⟩  (0, 1, 1; 1, −1, 0)  n!
Second-order Eulerian numbers  \begin{aligned}⟨ \\ ⟨ & {n \atop k} & ⟩ \\ & & ⟩ \end{aligned}  (0, 1, 1; 2, −1, 0)  (2n − 1)!!

Table 1: Row sums for some combinatorial numbers

Corollary 19, applied to the recurrences (9) and (10), immediately yields the following identities on alternating diagonal sums of the two kinds of associated Stirling numbers (\underline{A008306}, \underline{A008299}).

Identity 20.

∑_{k=0}^{n} \begin{matrix}[ \\ [ & {n + k \atop k} & ] \\ & & ] \end{matrix} (−1)^{k} = (−1)^{n}

Identity 21.

∑_{k=0}^{n} \begin{matrix}\{ \\ \{ & {n + k \atop k} & \} \\ & & \} \end{matrix} (−1)^{k} = (−1)^{n}n!

(Identity 20 at least is known, as it appears in Comtet [3, p. 256].)

In addition, Theorem 10 and Corollary 19 answer a question in the author’s paper [11]. In this work we derive formulas that can be used to find the row sums for numbers satisfying recurrences of the form (1) that have β = β′ = 0. In particular, numbers of this type have “nice” row sums. However, some combinatorial numbers that do not have β = β′ = 0 (such as the Eulerian (\underline{A008292}) and second-order Eulerian numbers (\underline{A008517})) also have “nice” expressions for their rows sums, while others (such as the Stirling numbers of the second kind (\underline{A008277})) do not. Theorem 10 and Corollary 19 explain this difference: The requirement for a “nice” row sum (in the sense here) is that β + β′ be zero. If β + β′ = 0, then we obtain the fairly simple expression in Corollary 19, but if β + β′ ≠ 0 then, from Theorem 10, we have the more complicated expression

S_{n} = (β + β′)S_{n−1}^{1} + ((α + α′)(n − 1) + γ + γ′)S_{n−1} + [n = 0]

that also contains the sum S_{n−1}^{1} = ∑_{j=0}^{n−1} |_{j}^{n−1}|j.

In the more general case of the power sum ∑_{k=0}^{n} |_{j}^{n}|j^{m} we can also use Theorem 10 or Corollary 11. This is because \binom{j}{m}m! = j\underline{m}, and we can convert falling powers j\underline{m} to ordinary powers j^{m} via the relation [5, p. 264]

j^{m} = ∑_{i=0}^{m} \left\{{m \atop i}\right\}j\underline{i}.  (11)

As examples, we find expressions for the sums ∑_{j=0}^{n} \left⟨{n \atop j}\right⟩j^{m}, ∑_{j=0}^{m}⟨⟨{n \atop j}⟩⟩j^{m}, ∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m}, and ∑_{j=0}^{n} \left\{{n \atop j}\right\}(−1)^{j}j^{m}. Doing so completes the author’s study begun in Spivey [11] of using finite differences to find explicit expressions for the power sum ∑_{j=0}^{n} |_{j}^{n}|j^{m} for some common combinatorial numbers |_{k}^{n}| .

Identity 22.

∑_{j=0}^{n} \left⟨{n \atop j}\right⟩j^{m} = ∑_{i=0}^{m} \left\{{m \atop i}\right\}\left\{{n \atop n − i}\right\}i!(n − i)!

Proof. Identity 12 implies

∑_{j=0}^{n} \left⟨{n \atop j}\right⟩j\underline{i} = ∑_{j=0}^{n} \left⟨{n \atop j}\right⟩\binom{j}{i}i! = \left\{{n \atop n − i}\right\}i!(n − i)!.

Applying Equation (11) then yields the result.

Identity 23.

∑_{j=0}^{n} \begin{aligned}⟨ \\ ⟨ & {n \atop j} & ⟩ \\ & & ⟩ \end{aligned} j^{m} = ∑_{i=0}^{m} \left\{{m \atop i}\right\} \begin{aligned}[ \\ [ & {2n − i \atop n − i} & ] \\ & & ] \end{aligned} i!

Proof. Identity 14 implies

∑_{j=0}^{n} \begin{aligned}⟨ \\ ⟨ & {n \atop j} & ⟩ \\ & & ⟩ \end{aligned} j\underline{i} = ∑_{j=0}^{n} \begin{aligned}⟨ \\ ⟨ & {n \atop j} & ⟩ \\ & & ⟩ \end{aligned} \binom{j}{i}i! = \begin{aligned}[ \\ [ & {2n − i \atop n − i} & ] \\ & & ] \end{aligned} i!.

Applying Equation (11) produces the identity.

The power sum for the Stirling numbers of the second kind (\underline{A008277}), ∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m}, is more complicated because Theorem 10 must be used instead of Corollary 11. In particular, if ∥_{m}^{n}∥ denotes ∑_{j=0}^{n} \left\{{n \atop j}\right\}\binom{j}{m}, then Theorem 10 implies, for m ≥ 0,

∥{n \atop m}∥ = (m + 1)∥{n − 1 \atop m + 1}∥ + (m + 1)∥{n − 1 \atop m}∥ + ∥{n − 1 \atop m − 1}∥,

Reindexing and rearranging terms, we have, for m ≥ 1,

∥{n \atop m}∥ = \frac{1}{m}∥{n + 1 \atop m − 1}∥ − ∥{n \atop m − 1}∥ − \frac{1}{m}∥{n \atop m − 2}∥.  (12)

Taking m = 1, we see that ∑_{j=0}^{n} \left\{{n \atop j}\right\}\binom{j}{1} can be expressed as a linear combination of the Bell numbers (\underline{A000110}) ϖ(n) and ϖ(n + 1), where ϖ(n) = ∑_{j=0}^{n} \left\{{n \atop j}\right\} [3, p. 210], and the coefficients do not depend on n. Taking m = 2 in the recurrence (12) shows that ∑_{j=0}^{n} \left\{{n \atop j}\right\}\binom{j}{2} can be written as a linear combination of ϖ(n), ϖ(n+1), and ϖ(n+2), where, once again, the coefficients do not depend on n. In general, we can see that ∑_{j=0}^{n} \left\{{n \atop j}\right\}\binom{j}{m} can be expressed as a linear combination of ϖ(n), ϖ(n + 1), …, ϖ(n + m), where the coefficients do not depend on n. Since \binom{j}{m}m! = j\underline{m}, and in view of Equation (11), the power sum ∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m} can be expressed in the form ∑_{i=0}^{m} c_{mi}ϖ(n + i), where the c_{mi} coefficients do not depend on n. Determining the c_{mi} for small values of m leads to the conjecture c_{mi} = \binom{m}{i}R(m − i), where R(n) = ∑_{j=0}^{n} \left\{{n \atop j}\right\}(−1)^{j}, the nth alternating row sum of the Stirling numbers of the second kind, also known as the the nth Rao-Uppuluri-Carpenter number (\underline{A000587}) [8]. This turns out to be the case, and, once conjectured, easily established using generating functions. More generally, we have the following identities.

Identity 24.

∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m} = ∑_{i=0}^{m} \binom{m}{i}R(m − i)ϖ(n + i)

Identity 25.

∑_{j=0}^{n} \left\{{n \atop j}\right\}(−1)^{j}j^{m} = ∑_{i=0}^{m} \binom{m}{i}ϖ(m − i)R(n + i)

Proof. The Bell numbers have exponential generating function (egf) e^{e^{x}−1}, and the Rao-Uppuluri-Carpenter numbers have egf e^{1−e^{x}} [5, p. 351]. It is known that if f(x) is the egf of the sequence {a_{i}}_{0}^{∞}, then D^{n}(f(x)) is the egf of the sequence {a_{n+i}}_{0}^{∞} [14, p. 40], where D^{n} denotes differentiation n times with respect to x. Thus the egf of {ϖ(n+i)}_{i=0}^{∞} is D^{n}(e^{e^{x}−1}), and the egf of {R(n + i)}_{i=0}^{∞} is D^{n}(e^{1−e^{x}}).

We now prove, by induction, that D^{n}(e^{e^{x}−1}) = e^{e^{x}−1} ∑_{j=0}^{n} \left\{{n \atop j}\right\}e^{jx}. We know the claim is true for n = 0. Since D(e^{e^{x}−1}) = e^{x}(e^{e^{x}−1}), the claim is also true for n = 1. Assuming, for n ≥ 2, the claim is true in the case n − 1, we have

D^{n} (e^{e^{x}−1}) = D (e^{e^{x}−1} ∑_{j=0}^{n−1} \left\{{n − 1 \atop j}\right\}e^{jx})

= e^{e^{x}−1} (∑_{j=0}^{n−1} \left\{{n − 1 \atop j}\right\}je^{jx} + ∑_{j=0}^{n−1} \left\{{n − 1 \atop j}\right\}e^{(j+1)x})

= e^{e^{x}−1} (∑_{j=0}^{n−1} \left\{{n − 1 \atop j}\right\}je^{jx} + ∑_{j=1}^{n} \left\{{n − 1 \atop j − 1}\right\}e^{jx})

= e^{e^{x}−1} (∑_{j=0}^{n−1} \left\{{n \atop j}\right\}e^{jx} + \left\{{n − 1 \atop n − 1}\right\}e^{jx})

= e^{e^{x}−1} (∑_{j=0}^{n} \left\{{n \atop j}\right\}e^{jx}) .

(In the second-to-last step, we used the recurrence \left\{{n \atop k}\right\} = k\left\{{n−1 \atop k}\right\} + \left\{{n−1 \atop k−1}\right\} and the fact that \left\{{n \atop 0}\right\} = 0 for n ≥ 1. In the last step, we used the fact that \left\{{n \atop n}\right\} = \left\{{n−1 \atop n−1}\right\}.) A similar argument shows that D^{n}(e^{1−e^{x}}) = e^{1−e^{x}} ∑_{j=0}^{n} \left\{{n \atop j}\right\}(−1)^{j}e^{jx}.

Since it is the case that if f(x) is the egf for {a_{n}}_{0}^{∞} and g(x) is the egf of {b_{n}}_{0}^{∞}, then f(x)g(x) is the egf of the sequence ∑_{i=0}^{n} \binom{n}{i}a_{i}b_{n−i} [14, p. 42], we have that the egf of ∑_{i=0}^{m} \binom{m}{i}R(m − i)ϖ(n + i) is ∑_{j=0}^{n} \left\{{n \atop j}\right\}e^{jx}. Because e^{jx} = ∑_{m=0}^{∞} \frac{j^{m}x^{m}}{m!} this egf can be expressed as

∑_{m=0}^{∞} ∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m} \frac{x^{m}}{m!} .  (13)

Since the coefficient of \frac{x^{m}}{m!} in this expression is ∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m}, Expression (13) must also be the egf of ∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m}. Thus ∑_{j=0}^{n} \left\{{n \atop j}\right\}j^{m} = ∑_{i=0}^{m} \binom{m}{i}R(m−i)ϖ(n+i). A similar argument shows that ∑_{j=0}^{n} \left\{{n \atop j}\right\}(−1)^{j}j^{m} = ∑_{i=0}^{m} \binom{m}{i}ϖ(m − i)R(n + i).

Remark: Here, the investigation of Equation (12) led to expressions for the power sum and alternating power sum for the Stirling numbers of the second kind (\underline{A008277}). Viewing Equation (12) from another perspective led to a new recurrence for the Bell numbers (\underline{A000110}) [12].

References

[1] N. P. Cakić, On the numbers related to the Stirling numbers of the second kind, Facta Univ. Ser. Math. Inform. 22 (2007), 105–108.

[2] C. A. Charalambides, Enumerative Combinatorics, CRC Press, 2002.

[3] L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

[4] A. E. Fekete, Apropos two notes on notation, Amer. Math. Monthly 101 (1994), 771–778.

[5] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.

[6] Ẑ. Mijajlović and Z. Marković, Some recurrence formulas related to the differential operator θd, Facta Univ. Ser. Math. Inform. 13 (1998) 7–17.

[7] E. Neuwirth, Recursively defined combinatorial functions: extending Galton’s board, Discrete Math. 239 (2001), 33–51.

[8] V. R. Rao-Uppuluri and J. A. Carpenter, Numbers generated by the function e^{1−e^{x}}, Fibonacci Quart. 7 (1969), 437–448.

[9] A. Regev and Y. Roichman, Statistics on wreath products and generalized binomial-Stirling numbers, Israel J. Math. 151 (2006), 189–221.

[10] J. Riordan, Combinatorial Identities, John Wiley & Sons, 1968.

[11] M. Z. Spivey, Combinatorial sums and finite differences, Discrete Math. 307 (2007), 3130–3146.

[12] M. Z. Spivey, A generalized recurrence for Bell numbers, J. Integer Sequences 11 (2008), Article 08.2.5.

[13] M. Z. Spivey and L. L. Steil, The k-binomial transforms and the Hankel transform, J. Integer Sequences 9 (2006), Article 06.1.1.

[14] H. S. Wilf, Generatingfunctionology, 2nd ed., Academic Press, 1994.

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

2010 Mathematics Subject Classification: Primary 11B37; Secondary 05A10, 05A19, 11B65, 11B73, 11B83, 65Q30. Keywords: Recurrence relation, finite difference, associated Stirling number, Bell number, Eulerian number, Rao-Uppuluri-Carpenter number.

(Concerned with sequences \underline{A000110}, \underline{A000587}, \underline{A007318}, \underline{A008275}, \underline{A008277}, \underline{A008292}, \underline{A008297}, \underline{A008299}, \underline{A008306}, \underline{A008517}, \underline{A021009}, \underline{A094587}, \underline{A094638}, and \underline{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.