MacMahon’s Partition Analysis IV: Hypergeometric Multisums

George E. Andrews^{∗} Department of Mathematics The Pennsylvania State University University Park, PA 16802, USA

                andrews@math.psu.edu

Peter Paule^{†} Research Institute for Symbolic Computation Johannes Kepler University Linz A–4040 Linz, Austria

          Peter.Paule@risc.uni-linz.ac.at

February 16, 1999

Abstract

In his famous book “Combinatory Analysis” MacMahon introduced Partition Analysis as a computational method for solving problems in connection with linear homogeneous diophantine inequalities and equations, respectively. The object of this paper is to introduce an entirely new application domain for MacMahon’s operator technique. Namely, we show that Partition Analysis can be also used for proving hypergeometric multisum identities. Our examples range from combinatorial sums involving binomial coefficients, harmonic and derangement numbers to multisums which arise in physics and which are related to the Knuth-Bender theorem.

∗Partially supported by the visiting researcher program of the J. Kepler University Linz.

†Supported by SFB-grant F1305 of the Austrian FWF.

1 Introduction

MacMahon devoted about hundred pages of his famous book [19, Vol. 2] to the study of Partition Analysis, a computational method for solving problems in connection with linear homogeneous diophantine inequalities and equations, respectively. Nevertheless, with the exception of Stanley’s article [20], MacMahon’s method has remained dormant until recently when M. Bousquet-Mélou and K. Eriksson [10] discovered their “Lecture Hall Partition Theorem”, a beautiful refinement of Euler’s classic result [1, p. 5]. It was exactly this achievement that brought Partition Analysis back on stage. Namely, the first named author observed in [3] that this type of partition theorem is perfectly tailored for MacMahon’s approach; see also [4].

In addition, it turned out that Partition Analysis is ideally suited for being supplemented by modern computer algebra methods. We developed the computer algebra package Omega which implements various aspects of MacMahon’s ideas. For an introduction to basic facts of “Omega Calculus” and for a variety of applications see [6] and [7].

In order to illustrate what Partition Analysis is about, we recall the definition of MacMahon’s Omega operator Ω_{≧}:

Definition 1.1. The operator Ω_{≧} is defined by

Ω_{≧} ∑_{s_{1}=−∞}^{∞} ⋯ ∑_{s_{r}=−∞}^{∞} A_{s_{1},...,s_{r}}λ_{1}^{s_{1}} ⋯ λ_{r}^{s_{r}} := ∑_{s_{1}=0}^{∞} ⋯ ∑_{s_{r}=0}^{∞} A_{s_{1},...,s_{r}},

where the domain of the terms A_{s_{1},...,s_{r}} (e.g., functions of several complex variables, or certain formal Laurent or power series) is such that the action is well-defined in some suitable analytic or algebraic context. In the context of this paper convergence is no issue at all because the operator Ω_{≧} will only act on (multivariate) Laurent polynomials

C[λ_{1}, …, λ_{r}, λ_{1}^{−1}, …, λ_{r}^{−1}] over the complex numbers; the only exceptions are in Sections 3 and 4 where we must assume |λ| > 1.

The operator Ω_{≧} can be viewed as a generalization of the constant term operator for

which MacMahon introduced the symbol Ω_{=}. More precisely we have:

Definition 1.2. The operator Ω_{=} is defined by

Ω_{=} ∑_{s_{1}=−∞}^{∞} ⋯ ∑_{s_{r}=−∞}^{∞} A_{s_{1},...,s_{r}}λ_{1}^{s_{1}} ⋯ λ_{r}^{s_{r}} := A_{0,...,0}.

Let a(λ_{1}, …, λ_{r}) denote the multisum expression. For picking up coefficients we will use the notation

⟨λ_{1}^{t_{1}} ⋯ λ_{r}^{t_{r}}⟩ a(λ_{1}, …, λ_{r}) := A_{t_{1},...,t_{r}}.

In other words, we have

⟨λ_{1}^{t_{1}} ⋯ λ_{r}^{t_{r}}⟩ a(λ_{1}, …, λ_{r}) = Ω_{=} \frac{a(λ_{1}, …, λ_{r})}{λ_{1}^{t_{1}} ⋯ λ_{r}^{t_{r}}}.

As pointed out by MacMahon [19, Vol. II, VIII, p. 104] the Ω_{=} operator is related to Ω_{≧}

by

Ω_{=}F (λ) = Ω_{≧}F (λ) + Ω_{≧}F (1/λ) − F (1).  (1.1)

On page 102 of his book [19, Vol. II, VIII] MacMahon gives a “short study” of The operation Ω_{≧}: “In connection with the inequality α_{1} ≥ α_{2} we have already found that

the sum ∑ x^{α_{1}}y^{α_{2}} depends upon

Ω_{≧} \frac{1}{(1 − λx)(1 − \frac{y}{λ})} = \frac{1}{(1 − x)(1 − x y)}.”  (1.2)

Then MacMahon continues by adding eleven similar rules, all being “easily verifiable results”. For instance,

Proof of (1.2). By geometric series expansion the left hand side equals

Ω_{≧} ∑_{i,j≥0} λ^{i−j}x^{i}y^{j} = Ω_{≧} ∑_{j,k≥0} λ^{k}x^{j+k}y^{j},

where the summation parameter i has been replaced by i = j + k. But now Ω_{≧} sets λ to

1 which completes the proof.

Next we come back to MacMahon’s remark concerning the sum ∑ x^{α_{1}}y^{α_{2}} where the summation parameters are nonnegative integers satisfying the inequality α_{1} ≥ α_{2}. Obviously this sum can be rewritten as

Ω_{≧} ∑_{α_{1},α_{2}≥0} λ^{α_{1}−α_{2}}x^{α_{1}}y^{α_{2}} = Ω_{≧} \frac{1}{(1 − λx) (1 − \frac{y}{λ})},

and after applying rule (1.2) we arrive at a closed form representation. In other words, the rule is used in order to eliminate the Ω_{≧}-variable λ.

This elimination approach is the essence of MacMahon’s method. For all applications of Partition Analysis to find in Section VIII of his book, he applied his catalogue of rules in order to compute closed forms of generating functions by successive elimination of those variables the Ω_{≧} operator acts on. In [6] and [7] we show that this procedure can be

put into an algorithmic setting, i.e., the elimination can be done in an entirely automatic fashion without any table-look up. Roughly spoken the application domain for this algorithmic machinery concerns problems in connection with partitions or compositions of numbers.

The application domain we consider in this paper is a different one. In enumeration problems (e.g., lattice paths, analysis of algorithms, graph theory) one often meets multidimensional sums over hypergeometric summands with constraints on the summation indices. In many of these cases the constraints are in form of Diophantine inequalities. Thus the multisums may involve binomial coefficients. But also single sums involving combinatorial numbers as, for instance, the derangement numbers D_{n} or the harmonic numbers H_{n}, can be rewritten as double- or multisums over hypergeometric summands. We list a few examples that are treated in the following sections: Calkin’s identity [11],

∑_{k=0}^{n} (∑_{j=0}^{k} \binom{n}{j})^{3} = \frac{n}{2} 8^{n} + 8^{n} − \frac{3n}{4} 2^{n}\binom{2n}{n},  (1.3)

Callan’s identity [12], for derangement numbers (defined in equation (3.1))

∑_{j=0}^{k} \binom{k}{j}D_{k+n−j} = k! ∑_{j=0}^{min(n,k)} \binom{k}{j}\binom{k + n − j}{k}D_{n−j},  (1.4)

a harmonic number identity (defined in equation (4.1)) that must be well-known,

∑_{k=0}^{n} \binom{k}{m}(H_{k} − H_{n−k}) = \binom{n + 1}{m + 1}H_{m},  (1.5)

and an identity found by Essam and Guttmann [15]

∑_{k_{1}} ∑_{k_{1}≤k_{2}} \frac{k_{1} − k_{2}}{n + 1} \binom{n + 1}{k_{1}}\binom{n + 1}{k_{2}} = \binom{2n + 1}{n}.  (1.6)

In the following sections we will show that MacMahon’s Partition Analyis can be used to treat also problems of this kind. In order to do so, one essentially needs to exploit elementary properties of the Ω_{≧} operator. We remark that using Omega calculus

in this way for proving multisum identities seems to be entirely new. At least we have not found any such example in MacMahon’s work.

However, because of (1.1) which relates the Ω_{≧} operator to the constant term operator,

such type of application does not come as a complete surprise. For instance, a good portion of Egorychev’s book [14] is devoted to the “method of coefficients”. This method formally corresponds to using certain properties of the constant term operator in order to lift a summation identity into a generating function algebra. Related to this technique is what Wilf [22, Ch. 4.3] describes as the “Snake Oil” method for combinatorial identities.

As an elementary introduction to Omega calculus we prove the simple doublesum identity

∑_{k=0}^{n} ∑_{j=0}^{k} \binom{n}{j} = 2^{n} + n 2^{n−1}.  (1.7)

Proof. Denote by f(n) the doublesum in question and let F (x) = ∑_{n=0}^{∞} f(n)x^{n} be the corresponding generating function. We rewrite F (x) in terms of the Ω_{≧} operator,

F (x) = ∑_{n=0}^{∞} ∑_{k=0}^{n} ∑_{j=0}^{k} \binom{n}{j}x^{n}

= Ω_{≧} ∑_{n,k,j} λ^{k−j}\binom{n + k}{j}x^{n+k}
= Ω_{≧} ∑_{n,k}(1 + λ^{−1})^{n+k}λ^{k}x^{n+k}

(by the Binomial Theorem)

= Ω_{≧} \frac{1}{(1 − x (1 + \frac{1}{λ})) (1 − xλ(1 + \frac{1}{λ}))}

(by the geometric series)

= \frac{1}{(1 − x)^{2}} Ω_{≧} \frac{1}{(1 − \frac{x}{1−x}λ^{−1}) (1 − \frac{x}{1−x}λ)}

= \frac{1}{(1 − x)^{2}} \frac{1}{(1 − \frac{x}{1−x}) (1 − (\frac{x}{1−x})^{2})}

(by (1.2))

= \frac{1}{1 − 2x} + \frac{x}{(1 − 2x)^{2}} .

From this the closed form evaluation of f(n) is immediate.

This way of using the Ω_{≧} operator is very close to MacMahon’s Partition Analysis. The

examples presented below will show that the scope of possible ways to apply this operator is much broader; sometimes certain properties of Ω_{≧} even lead to surprising extra insight.

Despite the success of the method in these examples, we have to point out that this usage of Ω_{≧} manipulatorics is non-algorithmic. Today we already have computer

programs for the automatic treatment of hypergeometric multisums. For instance, the WZ-engine of of Wilf and Zeilberger [23] has been fine-tuned by Wegschaider [21]. A more general engine, based on Zeilberger’s “holonomic systems approach to special functions” [24] has been designed by Chyzak [13]; its underlying mechanism is elimination via Gröbner bases methods for non-commutative operator algebras. These computer algebra packages are remarkably powerful for various applications. For instance, see Chyzak’s computer proof [13] of Calkin’s identity (1.3), or the proofs supplied by Wegschaider’s package [21] including a fully automatic proof of (1.6). But still one can observe certain complexity limitations; more detailed remarks on this aspect are to find in Section 5. Therefore manipulation methods like the Ω_{≧} calculus that we are going to introduce still

remain valuable tools in practical problem solving. Another application concerns the possibility that such methods might help to transform a problem into a form that finally can be treated automatically by a computer program.

In Section 2 Omega calculus is applied to derive a new proof of Calkin’s identity (1.3). It is interesting to observe that the method provides insight into a whole class of such identities as, for instance, identity (1.7).

In Section 3 we treat identities involving derangement numbers D_{n}. Besides proving Callan’s identity (1.4), Partition Analysis reveals its underlying structure and leads to a more general result in a straightforward manner.

In Section 4 we show that harmonic number identities also fit into the scope of Partition Analysis. A well-known summation is derived as a corollary from a more general identity which we could not find in the standard literature.

Finally in Section 5 we use Partition Analysis to evaluate the doublesum identity (1.6) together with a triplesum companion. As explained by Essam and Guttman [15] such identities arise in certain physical models. Moreover, it is remarkable that these identities can be obtained as special cases of the Bender-Knuth conjecture which has been proved by Gordon [17] and independently by Andrews [2].

2 Calkin’s Identity

The basis of the application of Partition Analysis in this section lies in the simple observation that for n = 2 or 3,

Ω_{≧}λD_{λ}(λ^{a_{1}−a_{2}} + λ^{a_{2}−a_{3}} + ⋯ + λ^{a_{n}−a_{1}}) = max(a_{1}, a_{2}, …, a_{n}) − min(a_{1}, a_{2}, …, a_{n}),(2.1)

where D_{λ} denotes differentiation with respect to λ.

Our object is to provide a new proof of Calkin’s intriguing identity [11]:

Theorem 2.1.

∑_{k=0}^{n} (∑_{j=0}^{k} \binom{n}{j})^{3} = \frac{n}{2} 8^{n} + 8^{n} − \frac{3n}{4} 2^{n}\binom{2n}{n} .  (2.2)

Proof. We begin by defining

M(n) = ∑_{k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}} max(k_{1}, k_{2}, k_{3})  (2.3)

and

m(n) = ∑_{k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}} min(k_{1}, k_{2}, k_{3}) .  (2.4)

Next we note that

∑_{k=0}^{n} (∑_{j=0}^{k} \binom{n}{j})^{3}

= ∑_{k=0}^{n} ∑_{n≥k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}}

= ∑_{n≥k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}} ∑_{k=max(k_{1},k_{2},k_{3})}^{n} 1

= ∑_{n≥k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}}(n − max(k_{1}, k_{2}, k_{3}) + 1)
= (n + 1)8^{n} − M(n) .  (2.5)

So to prove Calkin’s identity we only need to prove that

M(n) = \frac{n}{2} 8^{n} + \frac{3n}{4} 2^{n}\binom{2n}{n} .  (2.6)

To achieve this we note that

M(n) = ∑_{n≥k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}} max(n − k_{1}, n − k_{2}, n − k_{3})
= ∑_{n≥k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}}(n − min(k_{1}, k_{2}, k_{3}))
= n 8^{n} − m(n) .  (2.7)

In addition, using (2.1) we find that

M(n) − m(n)
= ∑_{n≥k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}}(max(k_{1}, k_{2}, k_{3}) − min(k_{1}, k_{2}, k_{3}))
= Ω_{≧}λD_{λ} ∑_{n≥k_{1},k_{2},k_{3}≥0} \binom{n}{k_{1}}\binom{n}{k_{2}}\binom{n}{k_{3}}(λ^{k_{1}−k_{2}} + λ^{k_{2}−k_{3}} + λ^{k_{3}−k_{1}})
= 3 · 2^{n} Ω_{≧}λ D_{λ}(1 + λ)^{n}(1 + λ^{−1})^{n}
= −3 · 2^{n}n Ω_{≧}(1 − λ)λ^{−n}(1 + λ)^{2n−1}
= −3 · 2^{n}n (∑_{j=n}^{2n−1} \binom{2n − 1}{j} − ∑_{j=n−1}^{2n−1} \binom{2n − 1}{j})
= 3 · 2^{n}n\binom{2n − 1}{n − 1} = \frac{3}{2} 2^{n}n\binom{2n}{n} .  (2.8)

Eliminating m(n) from these two identities, we find that

M(n) = \frac{n8^{n}}{2} + \frac{3}{4} n 2^{n}\binom{2n}{n} ,  (2.9)

which proves our theorem.

Remark. When we computed M(n) − m(n) we met the problem of evaluating the expression Ω_{≧}(1 − λ)λ^{−n}(1 + λ^{−1})^{n}. In Section 5 we will see that this is typical for such

kind of Ω_{≧} applications; compare in particular Lemma 5.1.

Unfortunately our Partition Analysis representation of

max(a_{1}, …, a_{n}) − min(a_{1}, …, a_{n})

is not valid for n > 3. Consequently, we cannot expect similarly nice results for

∑_{k=0}^{n} (∑_{j=0}^{k} \binom{n}{j})^{m}

when m > 3. Of course, the same method can be used to prove easily that

∑_{k=0}^{n} (∑_{j=0}^{k} \binom{n}{j})^{2} = \frac{n 4^{n}}{2} + 4^{n} − \frac{n}{2}\binom{2n}{n} .

3 Derangement Numbers

The derangement numbers, D_{n}, are well-known in combinatorics. D_{n} is the number of permutations of n letters without fixed points, and, in fact,

D_{n} = n! ∑_{j=0}^{n} \frac{(−1)^{j}}{j!} .  (3.1)

So we see immediately that

D_{n} = Ω_{≥}n!λ^{n} ∑_{j=0}^{∞} \frac{(−1)^{j}λ^{−j}}{j!}
= n! Ω_{≧}λ^{n}e^{− \frac{1}{λ}} .  (3.2)

To illustrate the utility of Partition Analysis in treating derangement number problems, we shall consider an identity of David Callan [12]:

∑_{j=0}^{k} \binom{k}{j}D_{k+n−j} = k! ∑_{j=0}^{min(n,k)} \binom{k}{j}\binom{k + n − j}{k}D_{n−j} .  (3.3)

Partition Analysis applied to each side of this identity leads us to a much stronger and more surprising result.

Theorem 3.1. For any N ≥ n − k,

∑_{j≧0} \binom{k}{j}\frac{(k + n − j)!}{(k + N − j)!}D_{k+N−j} = (−1)^{n} ∑_{j=0}^{n}(−1)^{j}\binom{n}{j}(j + k)!  (3.4)
( = (−1)^{n}k! _{2}F_{0}(−n, k + 1; 1) ) .

Remark. The left-hand side of the above identity is the left-hand side of Callan’s identity when N = n and the right-hand side of Callan’s identity when N = n − k. Since the right-hand side of the above identity is independent of N, we see that Callan’ identity is a direct consequence of our theorem.

Lemma 3.1. For nonnegative integers n and k,

D_{λ}^{n}λ^{k+n}e^{\frac{1}{λ}} = ∑_{j=k−n}^{k} c(k, n, j)λ^{j}e^{\frac{1}{λ}} ,  (3.5)

where

c(k, n, j) = (−1)^{k+j}\binom{n}{k − j}\frac{(j + n)!}{k!} .  (3.6)

Proof. For n = 0 we see immediately that c(k, 0, k) = 1. For n = 1,

D_{λ}λ^{k+1}e^{\frac{1}{λ}} = (k + 1)λ^{k}e^{\frac{1}{λ}} − λ^{k−1}e^{\frac{1}{λ}} ,  (3.7)

so c(k, 1, k − 1) = −1 and c(k, 1, k) = k + 1. Hence our Lemma is true for n = 0 and 1. We now proceed by mathematical induction.

D_{λ}^{n+1}λ^{k+n+1}e^{\frac{1}{λ}} = D_{λ}^{n}(D_{λ}λ^{k+n+1}e^{\frac{1}{λ}})
= D_{λ}^{n}((k + n + 1)λ^{k+n}e^{\frac{1}{λ}} − λ^{k+n−1}e^{\frac{1}{λ}})
= (k + n + 1) ∑_{j=k−n}^{k} c(k, n, j)λ^{j}e^{\frac{1}{λ}} − ∑_{j=k−1−n}^{k−1} c(k − 1, n, j)λ^{j}e^{\frac{1}{λ}}(3.8)

For this last expression, in order to equal

∑_{j=k−(n+1)}^{k} c(k, n + 1, j)λ^{j}e^{\frac{1}{λ}} ,  (3.9)

we must have

c(k, n + 1, j) = \{ \begin{matrix}(k + n + 1)c(k, n, k), & if j = k, \\ (k + n + 1)c(k, n, j) − c(k − 1, n, j), & if k − n ≤ j < k, \\ −c(k − 1, n, k − 1 − n), & if j = k − n − 1. \end{matrix} (3.10)

It is a matter of simple algebra to show that (−1)^{k+j}\binom{n}{k−j}(j + n)!/k! satisfies these defining recurrences and initial conditions. This shows that

c(k, n, j) = (−1)^{k+j}\binom{n}{k − j}\frac{(j + n)!}{k!}  (3.11)

and proves Lemma 3.1.

Proof of Theorem 3.1. First we note that

k! ∑_{j=k−n}^{k} c(k, n, j) = (−1)^{k} ∑_{j=k−n}^{k}(−1)^{j}\binom{n}{k − j}(j + n)!

= (−1)^{n} ∑_{j=0}^{n}(−1)^{j}\binom{n}{j}(j + k)! ,  (3.12)

which is the right-hand side of the identity in our theorem. Finally, using (3.2) and Lemma 3.1, for N ≧ n − k we obtain,

∑_{j≧0} \binom{k}{j}\frac{(k + n − j)!}{(k + N − j)!} D_{k+N−j}

= ∑_{j≧0} \binom{k}{j}\frac{(k + n − j)!}{(k + N − j)!} (k + N − j)! Ω_{≧}λ^{k+N−j}e^{− \frac{1}{λ}}

= k! Ω_{≧}e^{− \frac{1}{λ}} λ^{N} ∑_{j≧0} \frac{(k + n − j)!}{(k − j)! j!} λ^{k−j}

= k! Ω_{≧}e^{− \frac{1}{λ}} λ^{N}D_{λ}^{n} ∑_{j≧0}^{∞} \frac{λ^{k+n−j}}{j!}
= k! Ω_{≧}e^{− \frac{1}{λ}} λ^{N}D_{λ}^{n}λ^{k+n}e^{\frac{1}{λ}}
= k! Ω_{≧}e^{− \frac{1}{λ}} λ^{N} ∑_{j=k−n}^{k} c(k, n, j)λ^{j}e^{\frac{1}{λ}}

= k! Ω_{≧} ∑_{j=k−n}^{k} c(k, n, j)λ^{N+j}

= k! ∑_{j=k−n}^{k} c(k, n, j)  (3.13)

because N ≧ n − k.

The discovery of this result was quite straightforward using Partition Analysis. Each side of Callan’s identity was represented in Partition Analysis, and each side came out to the final lines of the proof of our theorem first with N = n then with N = n − k. Once that was observed, it was clear that any N ≧ n−k would produce the same result. While Lemma 3.1 was found to be the necessary element in the proof, it was only upon examination of the c(k, n, j) that we observed the closed form for them.

4 Harmonic Numbers

Previously [5] harmonic number identities have been reduced to binomial coefficient or hypergeometric series identities by means of the operator identity

δ\binom{x + n}{n} = ∑_{j=1}^{n} \frac{1}{j} = H_{n} ,  (4.1)

where

δ f(x) = f′(0) .  (4.2)

In terms of Partition Analysis we may write

H_{n} = Ω_{≧}λ^{n} ∑_{j=1}^{∞} \frac{λ^{−j}}{j}

= −Ω_{≧}λ^{n} log(1 − \frac{1}{λ}) .  (4.3)

We suspected that the previous treatment via operators would be replicated by Partition Analysis. Again we were surprised. We chose as a test case the identity [18; p. 14]

∑_{k=0}^{n} \binom{k}{m}H_{k} = \binom{n + 1}{m + 1} (H_{n+1} − \frac{1}{m + 1})  (4.4)

Our attempt to prove this wound up proving instead:

Theorem 4.1.

∑_{k=0}^{n} \binom{k}{m}(H_{k} − H_{n−k}) = \binom{n + 1}{m + 1}H_{m} .  (4.5)

Proof. As suggested, we start with

∑_{k=0}^{n} \binom{k}{m}H_{k} = Ω_{≧} ∑_{k≥0} λ^{n−k}\binom{k}{m}δ\binom{x + k}{k}
= δΩ_{≧}λ^{n} ∑_{k≥0} λ^{−k}\binom{x + k}{k − m}\binom{x + m}{m}
= δΩ_{≧}λ^{n}\binom{x + m}{m} ∑_{k≥0} λ^{−k−m}\binom{x + k + m}{k}
= δΩ_{≧}λ^{n}\binom{x + m}{m}λ^{−m}(1 − λ^{−1})^{−x−m−1}
= Ω_{≧}λ^{n−m}(−(1 − λ^{−1})^{−m−1} log(1 − λ^{−1}) + (1 − λ^{−1})^{−m−1}H_{m})
= Ω_{≧} (− ∑_{j=0}^{∞} \binom{m + j}{j}λ^{n−m−j} log(1 − λ^{−1}) + ∑_{j=0}^{∞} \binom{m + j}{j}λ^{n−m−j}H_{m})
= ∑_{j=0}^{n−m} \binom{m + j}{j}H_{n−m−j} + H_{m} ∑_{j=0}^{n−m} \binom{m + j}{j}
= ∑_{k=0}^{n} \binom{k}{m}H_{n−k} + H_{m}\binom{n + 1}{m + 1} ,  (4.6)

which proves our Theorem 4.1. Corollary 4.1.

∑_{k=0}^{n} \binom{k}{m}H_{n−k} = \binom{n + 1}{m + 1}(H_{n+1} − H_{m+1}) .  (4.7)

Proof. This follows immediately from (4.4) and (4.5) once we note that

H_{m} + \frac{1}{m + 1} = H_{m+1} .

5 An Example from Physics

In [15] Essam and Guttmann considered configurations of p vicious random walkers on a multi-dimensional lattice. The problem of vicious walkers finds many physical applications, for instance, in the context of Brownian motion or of directed polymer networks. For an introduction to fundamental results and examples, Essam and Guttmann refer to Fisher [16]. In [15] they were able to express the generating functions for the number of such configurations in terms of (generalized) hypergeometric functions.

In particular, they found a hypergeometric multisum expression for the number S_{n}(p) of configurations that combinatorially can be described, e.g., as the number of “brushes of mutually avoiding hairs” of length n. Namely,

S_{n}(p) = ∑_{0≤q_{1}≤···≤q_{p}≤n} w_{n}(q_{1}, …, q_{p}),  (5.1)

where

w_{n}(q_{1}, …, q_{p}) = ∏_{1≤i<j≤p}(q_{j} − q_{i} + j − i) ∏_{j=1}^{p} \frac{(n + p − j)!}{(q_{j} + j − 1)! (n − q_{j} + p − j)!}. (5.2)

In the trivial case p = 1 one has S_{n}(1) = 2^{n}. The next cases are slightly more involved, for instance, S_{n}(2) = \binom{2n+1}{n} and S_{n}(3) = \frac{2^{n+1}}{n+2} \binom{2n+1}{n}. But, as remarked by Essam and Guttmann, “a clear pattern emerges”, which led them to conjecture that

S_{n}(p) = 2^{pn} ∏_{j=1}^{p} \frac{((j + 1)/2)_{n}}{(j)_{n}} .  (5.3)

Here we use the Pochhammer symbol (x)_{n} = x(x + 1) … (x + n − 1).

This closed form representation indepently has been conjectured by Arrowsmith et al. [8]. Finally, as described by Arrowsmith and Essam [9], it turned out, as an observation of Krattenthaler, that (5.3) can be obtained from the Bender-Knuth conjecture for the specialization q → 1. As mentioned above this conjecture is now a theorem, but the proofs (e.g. Gordon [17] or Andrews [2]) are far from being trivial. Therefore our motivation to look at this problem is guided by the question whether there are possible ways to derive the multisum evaluations via elementary Ω_{≧}-manipulatorics.

Actually the idea of applying Partition Analysis to the multisum in (5.1) is a very natural one since the inequality constraints on the summation parameters q_{i} just invite to do so.

5.1 The case p = 2

We reformulate the case p = 2 of (5.1) as follows:

Proposition 5.1. For any nonnegative integer n:

S_{n}(2) = ∑_{k_{1}} ∑_{k_{2}≤k_{1}} \frac{k_{1} − k_{2}}{n + 1} \binom{n + 1}{k_{1}}\binom{n + 1}{k_{2}}  (5.4)

= \binom{2n + 1}{n}.  (5.5)

The doublesum representation (5.4) is immediate from (5.1). In order to compute the evaluation (5.5) we introduce a lemma that serves as a standard tool in applications of this kind. (Cf., for instance, the proof of (2.8).) It concerns a “difference property” of the factor λ−1 which enables the reduction of an Ω_{≧} expression to a simpler “coefficient-

of” operation designated by ⟨ ⟩.

Lemma 5.1. Let f(λ) be a Laurent polynomial over the complex numbers, in short, f(λ) ∈ ℂ[λ, λ^{−1}]. Then for any integer α:

Ω_{≧} (λ − 1)λ^{−α}f(λ) = ⟨λ^{α−1}⟩ f(λ).  (5.6)

Proof. Let f(λ) = ∑_{k} f_{k}λ^{k} then the left hand side of (5.6) equals

Ω_{≧} ∑_{k} f_{k}λ^{k−α+1} − Ω_{≧} ∑_{k} f_{k}λ^{k−α} = ∑_{k≥α−1} f_{k} − ∑_{k≥α} f_{k} = f_{α−1}.

Now we are able to evaluate the doublesum. Proof of Proposition 5.1. Let D_{λ} denote the derivation operator with respect to λ. We rewrite the doublesum in (5.4) as

S_{n}(2) = \frac{1}{n + 1} Ω_{≧} ∑_{k_{1},k_{2}} λ^{k_{1}−k_{2}}(k_{1} − k_{2})\binom{n + 1}{k_{1}}\binom{n + 1}{k_{2}}

= \frac{1}{n + 1} Ω_{≧} λD_{λ} ∑_{k_{1},k_{2}} λ^{k_{1}−k_{2}} \binom{n + 1}{k_{1}}\binom{n + 1}{k_{2}}

= \frac{1}{n + 1} Ω_{≧} λD_{λ}(1 + λ)^{n+1}(1 + \frac{1}{λ})^{n+1} = \frac{1}{n + 1} Ω_{≧} λD_{λ} \frac{(1 + λ)^{2n+2}}{λ^{n+1}}

= \frac{1}{n + 1} Ω_{≧} \frac{(2n + 2)(1 + λ)^{2n+1}λ^{n+1} − (1 + λ)^{2n+2}(n + 1)λ^{n}}{λ^{2n+1}}

= Ω_{≧} (λ − 1)\frac{(1 + λ)^{2n+1}}{λ^{n+1}} = ⟨λ^{n}⟩ (1 + λ)^{2n+1} = \binom{2n + 1}{n},

where in last line we used Lemma 5.1.

5.2 The case p = 3

Similar to the case p = 2 we can treat the case p = 3 of (5.1) which we state as follows: Proposition 5.2. For any nonnegative integer n:

S_{n}(3) = ∑_{k_{1}} ∑_{k_{2}≤k_{1}} ∑_{k_{3}≤k_{2}} \frac{(k_{1} − k_{2})(k_{2} − k_{3})(k_{1} − k_{3})}{(n + 2)^{2}(n + 1)}\binom{n + 2}{k_{1}}\binom{n + 2}{k_{2}}\binom{n + 2}{k_{3}} (5.7)
= \frac{2^{n+1}}{n + 2}\binom{2n + 1}{n}.  (5.8)

Again the verification of equality (5.7) is immediate from the presentation (5.1). As the next step we derive a Ω_{≧}-presentation of the triple sum.

In the following we will often use λ and μ instead of the “standard” Ω_{≧}-variables λ_{1} and λ_{2}. Lemma 5.2. For any nonnegative integer n:

S_{n}(3) = Ω_{≧} (λμ − 1)(λ − μ^{2})(μ − λ^{2})\frac{(1 + λ)^{n}(λ + μ)^{n}(1 + μ)^{n}}{λ^{n+2}μ^{n+2}} .  (5.9)

Proof. Let D_{i} denote the derivation operator with respect to λ_{i}, i ∈ {1, 2, 3}. We rewrite the triplesum in (5.7) as

S_{n}(3) =

= Ω_{≧} ∑_{k_{1},k_{2},k_{3}} λ_{1}^{k_{1}−k_{2}}λ_{2}^{k_{2}−k_{3}}λ_{3}^{k_{1}−k_{3}} \frac{(k_{1} − k_{2})(k_{2} − k_{3})(k_{1} − k_{3})}{(n + 2)^{2}(n + 1)}\binom{n + 2}{k_{1}}\binom{n + 2}{k_{2}}\binom{n + 2}{k_{3}}

= Ω_{≧} λ_{1}λ_{2}λ_{3}D_{1}D_{2}D_{3} ∑_{k_{1},k_{2},k_{3}} \frac{λ_{1}^{k_{1}−k_{2}}λ_{2}^{k_{2}−k_{3}}λ_{3}^{k_{1}−k_{3}}}{(n + 2)^{2}(n + 1)} \binom{n + 2}{k_{1}}\binom{n + 2}{k_{2}}\binom{n + 2}{k_{3}}

= Ω_{≧} λ_{1}λ_{2}λ_{3}D_{1}D_{2}D_{3}(1 + λ_{1}λ_{3})^{n+2}(1 + \frac{λ_{2}}{λ_{1}} )^{n+2}(1 + \frac{1}{λ_{2}λ_{3}} )^{n+2}/((n + 2)^{2}(n + 1))

= Ω_{≧} \frac{(λ_{1}λ_{2}λ_{3}^{2} − 1)(λ_{2} − λ_{1}^{2}λ_{3})(λ_{1} − λ_{2}^{2}λ_{3})}{(λ_{1}λ_{2}λ_{3})^{2}}(1 + λ_{1}λ_{3})^{n}(1 + \frac{λ_{2}}{λ_{1}} )^{n}(1 + \frac{1}{λ_{2}λ_{3}} )^{n}.

If we now replace λ_{1}λ_{3} by λ, and λ_{2}λ_{3} by μ we obtain the expression in (5.9).

For the evaluation of the Ω_{≧}-presentation we need a generalization of Lemma 5.1. Lemma 5.3. Let f(λ, μ) ∈ ℂ[λ, λ^{−1}, μ, μ^{−1}]. Then for any pair of integers α and β:

Ω_{≧}(λμ − 1)λ^{−α}μ^{−β}f(λ, μ) =
⟨λ^{α−1}μ^{β−1}⟩ f(λ, μ) + ∑_{i≥α}⟨λ^{i}μ^{β−1}⟩ f(λ, μ) + ∑_{j≥β}⟨λ^{α−1}μ^{j}⟩ f(λ, μ).  (5.10)

Proof. Let f(λ, μ) = ∑_{i,j} f_{i,j}λ^{i}μ^{j} and let the Ω_{≧} operator act on λ and μ. The left hand side of (5.10) equals

Ω_{≧} ∑_{i,j} f_{i,j}λ^{i−α+1}μ^{j−β+1} − Ω_{≧} ∑_{i,j} f_{i,j}λ^{i−α}μ^{j−β} =

∑_{i≥α−1} ∑_{j≥β−1} f_{i,j} − ∑_{i≥α} ∑_{j≥β} f_{i,j} = f_{α−1,β−1} + ∑_{i≥α} f_{i,β−1} + ∑_{j≥β} f_{α−1,j}.

The following corollary is an immediate consequence. Corollary 5.1. Let f(λ, μ) ∈ C[λ, λ^{−1}, μ, μ^{−1}] be symmetric, i.e., f(λ, μ) = f(μ, λ). Then for any integer α:

Ω_{≧} (λμ − 1)λ^{−α}μ^{−α}f(λ, μ) = ⟨λ^{α−1}μ^{α−1}⟩ f(λ, μ) + 2 ∑_{i≥α}⟨λ^{i}μ^{α−1}⟩ f(λ, μ).

Symmetric Laurent polynomials satisfy another useful property. Lemma 5.4. Let f(λ, μ) ∈ C[λ, λ^{−1}, μ, μ^{−1}] be such that f(λ, μ) = f(μ, λ), then for any univariate Laurent polynomial g:

Ω_{≧} f(λ, μ)g(λ) = Ω_{≧} f(λ, μ)g(μ).

Proof. Let f(λ, μ) = ∑_{i,j} f_{i,j}λ^{i}μ^{j}. The operator Ω_{≧} is linear, hence it suffices to prove

the lemma for g(λ) = λ^{−α} where α is an arbitrary integer:

Ω_{≧} f(λ, μ)λ^{−α} = Ω_{≧} ∑_{i,j} f_{i,j}λ^{i−α}μ^{j} = ∑_{i≥α} ∑_{j} f_{i,j}

= ∑_{i≥α} ∑_{j} f_{j,i} = ∑_{i} ∑_{j≥α} f_{i,j} = Ω_{≧} ∑_{i,j} f_{i,j}λ^{i}μ^{j−α}.

After this preparatory work which essentially exhibits some elementary properties of the Ω_{≧} operator, we state another lemma which is convenient to introduce for technical reasons.

Lemma 5.5. For nonnegative integers α, β, a, b, and c:

⟨λ^{α}μ^{β}⟩ (1 + λ)^{a}(λ + μ)^{b}(1 + μ)^{c} = ∑_{i} \binom{a}{i}\binom{b}{α − i}\binom{c}{α + β − b − i}.  (5.11)

Proof. The left hand side of (5.11) equals

⟨λ^{α}μ^{β}⟩ ∑_{i,j,k} \binom{a}{i}\binom{b}{j}\binom{c}{k}λ^{i+j}μ^{b−j+k}.

Hence the lemma follows by rewriting the equations i + j = α and b − j + k = β as j = α − i and k = β − b + α − i.

Now we are in the position to prove Proposition 5.2. Proof of Proposition 5.2. Let p_{n}(λ, μ) = (1 + λ)^{n}(λ + μ)^{n}(1 + μ)^{n}. By Lemma 5.2,

S_{n}(3) = Ω_{≧} \frac{(λμ − 1)(λ − μ^{2})(μ − λ^{2})}{λ^{n+2}μ^{n+2}}p_{n}(λ, μ)

= Ω_{≧} (λμ − 1)λ^{−n}μ^{−n}p_{n}(λ, μ) + Ω_{≧} (λμ − 1)λ^{−(n+1)}μ^{−(n+1)}p_{n}(λ, μ)

− Ω_{≧} (λμ − 1)λ^{−(n−1)}μ^{−(n+2)}p_{n}(λ, μ) − Ω_{≧} (λμ − 1)λ^{−(n+2)}μ^{−(n−1)}p_{n}(λ, μ)

= Ω_{≧} (λμ − 1)λ^{−n}μ^{−n}p_{n}(λ, μ) + Ω_{≧} (λμ − 1)λ^{−(n+1)}μ^{−(n+1)}p_{n}(λ, μ)

− 2 Ω_{≧} (λμ − 1)λ^{−(n−1)}μ^{−(n+2)}p_{n}(λ, μ).

The last equality is by Lemma 5.4. In the next step we apply Lemma 5.3 and Corollary 5.1, respectively, and obtain

S_{n}(3) = a_{n} + b_{n} − 2 c_{n} + 2(A_{n} + B_{n} − C_{n}^{(1)} − C_{n}^{(2)})

where

a_{n} = ⟨λ^{n−1}μ^{n−1}⟩ p_{n}(λ, μ), b_{n} = ⟨λ^{n}μ^{n}⟩ p_{n}(λ, μ), c_{n} = ⟨λ^{n−2}μ^{n+1}⟩ p_{n}(λ, μ),

A_{n} = ∑_{i≥n}⟨λ^{i}μ^{n−1}⟩ p_{n}(λ, μ), B_{n} = ∑_{i≥n+1}⟨λ^{i}μ^{n}⟩ p_{n}(λ, μ) and

C_{n}^{(1)} = ∑_{i≥n−1}⟨λ^{i}μ^{n+1}⟩ p_{n}(λ, μ), C_{n}^{(2)} = ∑_{j≥n+2}⟨λ^{n−2}μ^{j}⟩ p_{n}(λ, μ).

By Lemma 5.5, with a = b = c = n, we have,

a_{n} = ∑_{i} \binom{n}{i}\binom{n}{i + 1}\binom{n}{i + 2}, b_{n} = ∑_{i} \binom{n}{i}^{3} and c_{n} = a_{n}.

Again by Lemma 5.5, with a = b = c = n, we have,

A_{n} = ∑_{j≥n} ∑_{i} \binom{n}{i}\binom{n}{j − i}\binom{n}{j − i − 1}, B_{n} = ∑_{j≥n+1} ∑_{i} \binom{n}{i}\binom{n}{j − i}^{2},

C_{n}^{(1)} = ∑_{j≥n−1} ∑_{i} \binom{n}{i}\binom{n}{j − i}\binom{n}{j − i + 1} = A_{n} and

C_{n}^{(2)} = ∑_{j≥n+2} ∑_{i} \binom{n}{i}\binom{n}{i + 2}\binom{n}{j − i − 2}.

Summarizing, the application of the Ω_{≧} operator results in the reduction of the triplesum

problem into one involving a linear combination of single- and double-sums, namely

S_{n}(3) = b_{n} − a_{n} + 2(B_{n} − C_{n}^{(2)}).

Finally we observe that

2 B_{n} = 2^{n}\binom{2n}{n} − b_{n}  (5.12)

and

2 C_{n}^{(2)} = 2^{n}\binom{2n}{n − 2} − a_{n},  (5.13)

which gives

S_{n}(3) = 2^{n}\binom{2n}{n} − 2^{n}\binom{2n}{n − 2} = \frac{2^{n+1}}{n + 2}\binom{2n + 1}{n}.

First we prove relation (5.12). To this end we evaluate a variation of the doublesum representation for B_{n}. Namely, after dropping the condition on the summation parameter j we obtain by Vandermonde’s formula,

∑_{j} ∑_{i} \binom{n}{i}\binom{n}{j − i}^{2} = ∑_{i} \binom{n}{i} ∑_{j} \binom{n}{j}^{2} = \binom{2n}{n} ∑_{i} \binom{n}{i} = 2^{n}\binom{2n}{n}.

In addition, we observe that

∑_{j≤n} ∑_{i} \binom{n}{i}\binom{n}{j − i}^{2} = ∑_{j≥n} ∑_{i} \binom{n}{i}\binom{n}{j − i}^{2}.  (5.14)

This is verified by applying to the left hand side the summation parameter transform j → 2n − j, i.e.,

∑_{j≤n} ∑_{i} \binom{n}{i}\binom{n}{j − i}^{2} = ∑_{j≥n} ∑_{i} \binom{n}{i}\binom{n}{2n − j − i}^{2}.

Then after i → n − i we arrive at the right hand side of (5.14). Finally we combine all this in order to obtain (5.12):

2^{n}\binom{2n}{n} = (∑_{j≤n} + ∑_{j≥n+1}) ∑_{i} \binom{n}{i}\binom{n}{j − i}^{2}

= ∑_{j≥n} ∑_{i} \binom{n}{i}\binom{n}{j − i}^{2} + B_{n} = 2 B_{n} + b_{n}.

The proof of relation (5.13) is completely analogous. Dropping the condition on the summation parameter j gives,

∑_{j} ∑_{i} \binom{n}{i}\binom{n}{i + 2}\binom{n}{j − i − 2} = ∑_{i} \binom{n}{i}\binom{n}{i + 2} ∑_{j} \binom{n}{j} = 2^{n}\binom{2n}{n − 2},

where we used again Vandermonde’s formula. The analogue to identity (5.14) reads as

∑_{j≤n+1} ∑_{i} \binom{n}{i}\binom{n}{i + 2}\binom{n}{j − i − 2} = ∑_{j≥n+1} ∑_{i} \binom{n}{i}\binom{n}{i + 2}\binom{n}{j − i − 2}. (5.15)

For the proof we apply j → 2n + 2 − j to the left hand side, i.e.,

∑_{j≤n+1} ∑_{i} \binom{n}{i}\binom{n}{i + 2}\binom{n}{j − i − 2} = ∑_{j≥n+1} ∑_{i} \binom{n}{i}\binom{n}{i + 2}\binom{n}{2n − j − i}.

Then after i → n − i − 2 we arrive at the right hand side of (5.15). Finally we obtain (5.13) as follows:

2^{n}\binom{2n}{n − 2} = ( ∑_{j≤n+1} + ∑_{j≥n+2}) ∑_{i} \binom{n}{i}\binom{n}{i + 2}\binom{n}{j − i − 2}

= ∑_{j≥n+1} ∑_{i} \binom{n}{i}\binom{n}{i + 2}\binom{n}{j − i − 2} + C_{n}^{(2)} = 2 C_{n}^{(2)} + a_{n}.

This completes the proof of Proposition 5.2.

5.3 Remarks on the general case

Weschaider [21, Ch. 5.6] has derived quite different proofs for the Propositions 5.1 and 5.2. These proofs are based on his Mathematica package MULTISUM which is an implementation of Wegschaider’s algorithmic refinement of WZ-theory [23] for hypergeometric multisums. Using the MULTISUM package together with human insight and interaction, Wegschaider was able to derive elegant proofs for (5.5) and (5.8). In addition he pointed out that in principle these identities can be proved in an entirely automatic fashion by the computer. However, due to memory overflow he only was able to present such a proof for (5.5).

This indicates that Ω_{≧}-manipulation on multisums may be used also in order to reduce

complexity of computation. For instance, our Ω_{≧}-proof of (5.8) reduces the triplesum

problem to a problem involving only single- and double-sums that then could be taken as input for computer programs like MULTISUM.

Another aspect of Ω_{≧}-manipulation is the flexibility of the method. For instance,

another lemma that might be useful in similar applications reads as follows:

Lemma 5.6. Let f(λ, μ) ∈ C[λ, λ^{−1}, μ, μ^{−1}] be such that f(λ, μ) = f(μ, λ). Then for integers α, β, γ with α ≤ γ and β ≤ γ:

Ω_{≧} (λ^{α}μ^{β} − λ^{β}μ^{α})λ^{−γ}μ^{−γ}f(λ, μ) = 0.

Therefore in problems of the type

Ω_{≧} p(λ, μ)f(λ, μ),

where p and f are Laurent polynomials, one could try to represent Ω_{≧} p(λ, μ)f(λ, μ) as

a linear combination of summands involving as many terms as possible that are of the same form as in the lemma. One can expect that in this context Gröbner bases methods could be useful. We remark that if this technique is applied to the case of (5.8), one essentially ends up with a proof of a similar type as above.

Finally we want to add that the Ω_{≧}-method as described above can be used to prove

also the cases p = 4, p = 5, etc., of (5.1). However, so far we have not found a common underlying pattern that proves all the cases in one stroke. If such a pattern would be discovered, we have no doubt that the q-case could be done analogously. In other words, this approach then would give a new alternative proof of the Knuth-Bender conjecture.

References

[1] G.E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Vol. 2, G.-C. Rota ed., Addison-Wesley, Reading, 1976. (Reissued: Cambridge University Press, Cambridge, 1985.)

[2] G.E. Andrews, Plane Partitions II: the equivalence of the Bender-Knuth and MacMahon Conjectures, Pac. J. Math. 72 (1977), 283–291.

[3] G.E. Andrews, MacMahon’s partition analysis I: the lecture hall partition theorem, (to appear).

[4] G.E. Andrews, MacMahon’s partition analysis II: fundamental theorems, (to appear).

[5] G.E. Andrews and K. Uchimura, Identities in Combinatorics IV: differentiation and harmonic numbers, Utilitas Math. 28 (1985), 265–269.

[6] G.E. Andrews, P. Paule and A. Riese, MacMahon’s partition analysis III: The Omega Package, 1999, preprint.

[7] G.E. Andrews, P. Paule and A. Riese, MacMahon’s partition analysis V: magic squares, (in preparation).

[8] D.K. Arrowsmith, P. Mason and J.W. Essam, Vicious walkers, flows and directed percolation, Physica A 177 (1991), 267–272.

[9] D.K. Arrowsmith and J.W. Essam, Chromatic polynomials and mod-λ flows on directed graphs and their applications, 1998, preprint.

[10] M. Bousquest-Mélou and K. Eriksson, Lecture hall partitions, The Ramanujan Journal 1 (1997), 101–111.

[11] N.J. Calkin, A curious binomial identity, Discrete Math. 131 (1994), 335–337.

[12] D. Callan, Problem 10643, Amer. Math. Monthly 105, No. 2, (1998).

[13] F. Chyzak, Fonctions holonomes en Calcul formel, Ph.D. Thesis, Ecole Polytech-

    nique, Paris, 1998. Available via: http://algo.inria.fr/libraries/.

[14] G.P. Egorychev, Integral Representation and the Computation of Combinatorial Sums, AMS Translations 59, 1984.

[15] J.W. Essam and A.J. Guttmann, Vicious walkers and directed polymer networks in general dimension, Phys. Rev. E 52 (1995), 5849–5862.

[16] M.E. Fisher, Walk, walls, wetting and melting, J. Stat. Phys. 34 (1984), 667–729.

[17] B. Gordon, A proof of the Bender-Knuth conjecture, Pacific J. Math. 108, 99–113.

[18] D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms, Birkhaeuser, Boston, 1981.

[19] P.A. MacMahon, Combinatory Analysis, 2 vols., Cambridge University Press, Cambridge, 1915-1916 (Reprinted: Chelsea, New York, 1960).

[20] R.P. Stanley, Linear homogeneous diophantine equations and magic labelings of graphs, Duke Math. J. 40 (1973), 607–632.

[21] K. Wegschaider, Computer Generated Proofs of Binomial Multi-Sum Identities, Diploma Thesis, RISC, J. Kepler University Linz, 1997. Available via:

    http://www.risc.uni-linz.ac.at/research/combinat/ risc/.

[22] H.S. Wilf, Generating functionology, Academic Press, 1990.

[23] H.S. Wilf and D. Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Inventiones Mathematicae 108 (1992), 575–633.

[24] D. Zeilberger, A holonomic systems approach to special functions identities, J. Comp. Appl. Math. 32 (1990), 321–368.