PROOF OF THE ALTERNATING SIGN MATRIX CONJECTURE ^{1}

Doron ZEILBERGER^{2}

Submitted: May 1, 1995; Accepted: July 25, 1995

Checked by^{3}: David Bressoud and

Gert Almkvist, Noga Alon, George Andrews, Anonymous, Dror Bar-Natan, Francois Bergeron, Nantel Bergeron, Gaurav Bhatnagar, Anders Björner, Jonathan Borwein, Mireille Bousquest-Mélou, Francesco Brenti, E. Rodney Canfield, William Chen, Chu Wenchang, Shaun Cooper, Kequan Ding, Charles Dunkl, Richard Ehrenborg, Leon Ehrenpreis, Shalosh B. Ekhad, Kimmo Eriksson, Dominique Foata, Omar Foda, Aviezri Fraenkel, Jane Friedman, Frank Garvan, George Gasper, Ron Graham, Andrew Granville, Eric Grinberg, Laurent Habsieger, Jim Haglund, Han Guo-Niu, Roger Howe, Warren Johnson, Gil Kalai, Viggo Kann, Marvin Knopp, Don Knuth, Christian Krattenthaler, Gilbert Labelle, Jacques Labelle, Jane Legrange, Pierre Leroux, Ethan Lewis, Daniel Loeb, John Majewicz, Steve Milne, John Noonan, Kathy O’Hara, Soichi Okada, Craig Orr, Sheldon Parnes, Peter Paule, Bob Proctor, Arun Ram, Marge Readdy, Amitai Regev, Jeff Remmel, Christoph Reutenauer, Bruce Reznick, Dave Robbins, Gian-Carlo Rota, Cecil Rousseau, Bruce Sagan, Bruno Salvy, Isabella Sheftel, Rodica Simion, R. Jamie Simpson, Richard Stanley, Dennis Stanton, Volker Strehl, Walt Stromquist, Bob Sulanke, X.Y. Sun, Sheila Sundaram, Raphaële Supper, Nobuki Takayama, Xavier G. Viennot, Michelle Wachs, Michael Werman, Herb Wilf, Celia Zeilberger, Hadas Zeilberger, Tamar Zeilberger, Li Zhang, Paul Zimmermann .

Dedicated to my Friend, Mentor, and Guru, Dominique Foata.

Two stones build two houses. Three build six houses. Four build four and twenty

houses. Five build hundred and twenty houses. Six build Seven hundreds and twenty houses. Seven build five thousands and forty houses. From now on, [exit and] ponder what the mouth cannot speak and the ear cannot hear.

(Sepher Yetsira IV,12)

Abstract: The number of n × n matrices whose entries are either −1, 0, or 1, whose row- and column- sums are all 1, and such that in every row and every column the non-zero entries alternate in sign, is proved to be [1!4! … (3n − 2)!]/[n!(n + 1)! … (2n − 1)!], as conjectured by Mills, Robbins, and Rumsey.

1 original version written December 1992. The Maple package ROBBINS accompanying this paper, can be down-

loaded from the www address in footnote 2 below. 2 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA.

E-mail:zeilberg@math.temple.edu. WWW:http://www.math.temple.edu/~ zeilberg. Supported in part by the

NSF. 3 See the Exodion for affiliations, attribution, and short bios.

INTRODUCTION

The number of permutations (“houses”) that can be made using n objects (“stones”), for n ≤ 7, is given in Sepher Yetsira (Ch. IV, v. 12), a Cabalistic text written more than 1700 years ago. The general formula, n!, was stated and proved about 1000 years later by Rabbi Levi Ben Gerson (“Ralbag”). The Cabala, which is a combinatorial Theory Of Everything (both physical and spiritual), was interested in this problem because n! is the number of inverse images τ^{−1}(w) of a generic n−lettered word w under the canonical homomorphism τ:

τ : {ℵ, bet, …, shin, tav}^{∗} → {ℵ, …, tav}^{∗}/{ℵ (bet) = (bet) ℵ, …, (shin) (tav) = (tav) (shin)} .

The homomorphism τ is of considerable interest, since two words w_{1}, and w_{2} are temura-equivalent (anagrams) if τ(w_{1}) = τ(w_{2}).

A coarser, but just as important, equivalence relation on Hebrew words and sentences is the one induced by the homomorphism

G : {ℵ , bet , …, shin , tav}^{∗} → N ,

defined by G(ℵ) = 1, G(bet) = 2, …, G(shin) = 300, G(tav) = 400, and extended homomorphically. Two words w_{1}, w_{2} are said to be Gematrically equivalent if G(w_{1}) = G(w_{2}).

Modern-day numerologists, like Mills, Robbins, and Rumsey, use a different kind of Gematria, one that searches for equality between sequences of cardinalities of combinatorial families. This enabled them to conjecture a series of remarkable and tantalizing enumeration identities[MRR1-3],[Stanl]. Most of these conjectures concern a natural generalization of the notion of permutation, called alternating sign matrix.

A permutation π may be described in terms of its corresponding permutation matrix, that is the 0 − 1 matrix obtained by making the i^{th} row have all zeros except for a 1 at the π(i)^{th} column. What emerges is a 0 − 1 matrix whose row- and column- sums are all 1.

Since 3 is the cardinality of the set {ℵ , mem , shin}, the “mother-letters”, dear to the authors of Sepher Yetsira, they would have most likely enthusiastically approved of the generalization of permutation matrices, alternating sign matrices, introduced by Robbins and Rumsey[RR] in their study of a determinant-evaluation rule due to yet another wizard, the Rev. Charles Dodgson. Rather than use only the two symbols 0, 1 as entries, an alternating sign matrix is allowed the use of the three symbols {−1, 1, 0} (corresponding to guilt, innocence, and the tongue of the law, respectively). The row- and column- sums have still to be 1, and in addition, in every row and every column, the non-zero elements, 1, −1 (right and wrong), have to alternate.

Mills, Robbins, and Rumsey[MRR1] discovered that, like their predecessors the permutations, that are enumerated by the beautiful formula n!, these new mysterious objects seem to be enumerated by an almost equally simple formula:

A_{n} := ∏_{i=0}^{n−1} \frac{(3i + 1)!}{(n + i)!} ,

the now famous[R][Z3] sequence 1, 2, 7, 42, 429, 7436 …, first encountered by George Andrews[A1].

In this paper I present the first proof of this fact. I do hope that this is not the last proof, and that a shorter, more direct, elegant, and combinatorial proof will be found one day. Meanwhile, this paper should relieve at least some of Dave Robbins’s mathschmerz, expressed so eloquently in [R]:

These conjectures are of such compelling simplicity that it is hard to understand how any mathematician can bear the pain of living without understanding why they are true.

Much more serious than not knowing whether a given fact is true, is the agony of realizing that our cherished tools of the trade are inadequate to tackle a given problem. The fact that a conjecture resists vigorous attacks by skilled practitioners is an impetus for us either to sharpen our existing tools, or else create new ones. The value of a proof of an outstanding conjecture should be judged, not by its cleverness and elegance, and not even by its “explanatory power”, but by the extent in which it enlarges our toolbox. By this standard, the present proof is adequate. Like most new tools, the present method of proof is a judicious assembly of existing tools, which I will now describe.

The first ingredient consists of partial recurrence equations (alias partial difference equations) and operators. The calculus of finite differences was introduced in the last century by discrete mathematician George Boole, but in this century was taken up, and almost monopolized by, continuous number crunchers, who called them finite difference schemes. A notable exception was Dick Duffin (e.g. [D]) through whose writings I learnt about these objects, and immediately fell in love with them (e.g. [Z1][Z2]). It was fun returning to my first love.^{4}

Conspicuously missing from the present paper is my second love, bijective proofs (e.g. [ZB]), that were taught to me by Dominique Foata, Xavier G. Viennot, Herb Wilf and many others. However, doing bijections made me a better mathematician and person, so their implicit impact is considerable.

The second ingredient is my third love, constant term identities introduced to me by Dick Askey. Dennis Stanton[Stant] and John Stembridge[Ste] showed me how to crack them[Z4][Z5]. The Stanton-Stembridge trick (see below) was indeed crucial.

The third and last ingredient, which is not mentioned explicitly, but without which this proof could never have come to be, is my current love: computer algebra and Maple. Practically every lemma, sublemma, subsublemma …, was first conjectured with the aid of Maple, and then tested by it. A Maple package, ROBBINS, that empirically (and in a few cases rigorously,) checks every non-trivial fact proved in this paper, is given as a companion to this paper, and should be used in conjunction with it. Almost every statement is followed by a reference to the procedure in ROBBINS

that empirically corroborates it. [These are enclosed in square brackets; For example to see all alternating sign matrices of size 4, type ASM(4):.]

4 “Mathematicians, like Proust and everyone else, are at their best when writing about their first love”- Gian-Carlo

Rota (in: ‘Discrete Thoughts’, p. 3).

Once you have downloaded ROBBINS to your favorite directory, get into Maple by typing maple<CR>. Once in Maple, type read ROBBINS:, and follow the instructions given there. (By the way ezra means ‘help’ in Hebrew.) No knowledge of Maple is required, except for the fact that every command must end with a colon or semi-colon. For example, typing S15(4): would verify sublemma 1.5 for k = 4.

I wish to thank Shalosh B. Ekhad for its diligent computations, and Russ de Flavia, our dedicated local UNIX guru, for his constant technical support.

This paper would have been little more than a curiosity if not for George Andrews’s[A2] recent brilliant proof of another conjecture of Mills, Robbins, and Rumsey[MRR3] (conj. 2 of [Stanl]), that the number of so-called Totally Symmetric, Self- Complementary Plane Partitions (TSSCPP) is also given by A_{n}. All that I show is, that the sequence enumerating ASMs is the same as the one enumerating TSSCPPs, and then I take a free ride on Andrews’s[A2] result that the latter is indeed {1, 2, 7, 42, 429, …}.

This paper only settles the first, and simplest, conjecture, concerning the enumeration of alternating sign matrices. There are many variations and refinements listed in [Stanl][R][MRR2,3]. I am sure that the method of this paper should be capable of proving all of them. It is also possible that the present method of proof, combined with the multi-WZ method[WZ], could be used to prove a stronger conjecture of [MRR1,2](conj. 3 of [Stanl]), directly, in which case the present paper would also furnish an alternative proof of Andrews’s[A2] TSSCPP theorem.

A MORE GENERAL, AND HENCE EASIER, CONJECTURE

The first step, already undertaken in [MRR2-3], is to find more congenial “data structures” for both alternating sign matrices, and for TSSCPPs. Alternating sign matrices of size n are in easy bijection ([MRR2][R]) with monotone triangles. A monotone triangle is a triangular array of positive integers a_{i,j}, 1 ≤ i ≤ n, 1 ≤ j ≤ n − i + 1, such that, a_{i,j} < a_{i,j+1}, and a_{i,j} ≤ a_{i+1,j} ≤ a_{i,j+1}. In addition we require that the first row is 1, 2, ⋯, n, i.e. a_{1,j} = j, for j = 1, ⋯, n. We will rename them n-Gog triangles, and the creatures obtained by chopping off all entries with j > k, will be called n × k-Gog trapezoids. An n-Gog triangle is an n × n-Gog trapezoid. For example the following is one of the 429 5−Gog triangles (formerly called monotone triangles of size 5.)

1 2 3 4 5 1 3 4 5 2 4 5 3 5 4 .

[In order to view all of them type ‘GOG(5,5):’ in ROBBINS.] Retaining only the first three columns of the

above triangle, yields one of the 387 5 × 3-Gog trapezoids:

1 2 3 1 3 4 2 4 5 3 5 4 .

[In order to view all of them type ‘GOG(3,5):’ in ROBBINS.]

On the TSSCPP side, it was shown in [MRR3] that TSSCPPs whose 3D Ferrers graphs lie in the cube [0, 2n]^{3} are in trivial bijection with triangular arrays c_{i,j}, 1 ≤ i ≤ n, 1 ≤ j ≤ n − i + 1, of integers such that: (i) 1 ≤ c_{i,j} ≤ j, (ii) c_{i,j} ≥ c_{i+1,j}, and (iii) c_{i,j} ≤ c_{i,j+1}. We will call such triangles n-Magog triangles, and the corresponding chopped variety, with exactly the same conditions as above, but c_{i,j} is only defined for 1 ≤ i ≤ k rather than for 1 ≤ i ≤ n, n × k-Magog trapezoids. For example the following is one of the 429 5−Magog triangles:

1 2 3 3 5 1 2 2 3 1 2 2 1 2 1 .

[In order to view all of them type ‘MAGOG(5,5):’ in ROBBINS.] Retaining only the first three rows of the

above Magog-triangle, yields one of the 387 5 × 3-Magog trapezoids:

1 2 3 3 5 1 2 2 3 1 2 2 .

[ In order to view all of them type ‘MAGOG(3,5):’ in ROBBINS.]

Our goal is to prove the following statement, conjectured in [MRR3], and proved there for k = 2.

Lemma 1: For n ≥ k ≥ 1, the number of n × k-Gog trapezoids equals the number of n × k-Magog trapezoids.

[ The number of n by k Magog trapezoids, for specific n and k, is obtained by typing b(k,n); while the number of n by k Gog trapezoids is given by m(k,n);. To verify lemma 1, type S1(k,n):.]

This would imply, by setting n = k, that,

Corollary 1’: For n ≥ 1, the number of n-Gog triangles equals the number of n-Magog triangles.

Since n-Gog triangles are equi-numerous with n × n alternating sign matrices, and n-Magog triangles are equi-numerous with TSSCPPs bounded in [0, 2n]^{3}, this would imply, together with Andrews’s[A2] affirmative resolution of the TSCCPP conjecture, the following result, that was conjectured in [MRR1].

The Alternating Sign Matrix Theorem: The number of n × n alternating sign matrices, for n ≥ 1, is:

\frac{1!4! … (3n − 2)!}{n!(n + 1)! … (2n − 1)!} = ∏_{i=0}^{n−1} \frac{(3i + 1)!}{(n + i)!} .

The rest of this paper will consist of a proof of Lemma 1.

NOMENCLATURE

Throughout this paper, we will meet discrete functions F (n; a_{1}, …, a_{k}) of k + 1 discrete variables, n, a_{1}, …, a_{k}, where n ≥ 0, and (a_{1}, …, a_{k}) is confined to certain regions of discrete k-space N^{k}, that depend on n. We will make extensive use of the shift operators A_{i}, i = 1, …, k, defined by:

A_{i}F (a_{1}, …, a_{i}, …, a_{k}) = F (a_{1}, …, a_{i} + 1, …, a_{k}) .

For any (positive or negative) integer r, we have:

A_{i}^{r}F (a_{1}, …, a_{i}, …, a_{k}) = F (a_{1}, …, a_{i} + r, …, a_{k}) ,

and more generally,

A_{1}^{r_{1}} … A_{i}^{r_{i}} … A_{k}^{r_{k}} F (a_{1}, …, a_{i}, …, a_{k}) = F (a_{1} + r_{1}, …, a_{i} + r_{i}, …, a_{k} + r_{k}) .

We denote the identity operator by I. A partial linear recurrence operator (with constant coefficients) P (A_{1}, …, A_{k}) is any Laurent polynomial in the fundamental shift operators A_{1}, …, A_{k}. For example

(I − A_{1}^{−1})(I − A_{2}^{−1})F (a_{1}, a_{2}) = F (a_{1}, a_{2}) − F (a_{1} − 1, a_{2}) − F (a_{1}, a_{2} − 1) + F (a_{1} − 1, a_{2} − 1) .

We will also meet polynomials and rational functions f(x_{1}, …, x_{k}) that live on continuous k-space. The symmetric group S_{k} of permutations acts on f(x_{1}, …, x_{k}) as follows. For any permutation π = [π(1), …, π(k)], let πf(x_{1}, …, x_{k}) be the rational function obtained from f(x_{1}, …, x_{k}) by replacing x_{i} by x_{π(i)}, for i = 1 … k. In symbols:

πf(x_{1}, …, x_{k}) = f(x_{1}, …, x_{k})|_{{x_{1}→x_{π(1)},...,x_{k}→x_{π(k)}}} ,

for example, [2, 3, 1](x_{1} + 2x_{2} + 3x_{3}) = x_{2} + 2x_{3} + 3x_{1}.

Recall that the number of inversions, inv π, of a permutation π ∈ S_{k} is the number of pairs (i, j), with 1 ≤ i < j ≤ k such that π(i) > π(j). Recall also that the sign of a permutation sgn(π) may be defined by (−1)^{inv π}.

A rational function f(x_{1}, …, x_{k}) is called S_{k}-antisymmetric, or antisymmetric for short, if for i = 1 , …, k − 1:

f(x_{1}, …, x_{k})|_{x_{i}↔x_{i+1}} = −f(x_{1}, …, x_{k}) ,

the electronic journal of combinatorics 3 (2) (1996), #R13 7

or equivalently, since the transpositions {(i, i + 1), 1 ≤ i ≤ k − 1} generate the symmetric group S_{k}, the equality :πf(x) = sgn(π)f(x), holds for every π ∈ S_{k}. The group of signed permutations, that we will denote by W (B_{k}) (since it happens to be the Weyl group of the root system B_{k}, but this is not (directly) relevant to our proof), consists of pairs (π, ε), where π ∈ S_{k} and ε is a sign-assignment: ε = (ε_{1}, …, ε_{k}), where the ε_{i} are either +1 or −1. A sign assignment ε acts on f(x_{1}, …, x_{k}) by

εf(x) = f(ε_{1}(x_{1}), …, ε_{k}(x_{k})) ,

where, for any variable t:

ε_{i}(t) := t if ε_{i} = 1, and ε_{i}(t) := 1 − t if ε_{i} = −1 .

For example [−1, −1, +1](x_{1}^{2}x_{2}^{3}x_{3}^{4}) = (1 − x_{1})^{2}(1 − x_{2})^{3}x_{3}^{4}. A signed permutation (π, ε) acts on f(x_{1}, …, x_{k}) in the following way:

(π, ε)f(x) = επf(x) .

For example ([2, 3, 1], [+1, −1, −1])[x_{1}^{2} + 2x_{2} + x_{3}^{3}] = (1 − x_{2})^{2} + 2(1 − x_{3}) + x_{1}^{3}. Now it is time to define the sign of a signed permutation (no pun intended!), g = (π, ε). Definition SIGN: For any signed permutation g = (π, ε), we define sgn(g) := sgn(π) sgn(ε), where sgn(ε) is (−1) [number of −1’s]. Throughout this paper t̄:= 1−t. Since this notation will be used so frequently we will say it again, in bold face: Crucial Notation : t̄ := 1 − t. Warning: t̄ Is Not Complex Conjugation! A rational function f(x_{1}, …, x_{k}) is W (B_{k})-antisymmetric if it is S_{k}−antisymmetric, and also

f(x̄_{1}, …, x_{k}) = −f(x_{1}, …, x_{k}).

Equivalently, f(x_{1}, …, x_{k}) is W (B_{k})-antisymmetric if for any signed-permutation g ∈ W (B_{k}), we have: gf(x) = sgn(g)f(x). This follows from the well-known (and easy) fact that the group W (B_{k}) is generated by the generators (i, i + 1) of the symmetric group, along with the ‘sign change’ x_{1} → x̄_{1}. A Laurent formal power series f(x_{1}, …, x_{k}) is anything of the form

f(x_{1}, …, x_{k}) = ∑_{α_{1}≥L,...,α_{k}≥L} a_{α_{1},...,α_{k}}x_{1}^{α_{1}} … x_{k}^{α_{k}}  ,

where L is a (non-positive) integer. If L = 0 then it is a run-of-the-mill formal power series. If a_{α_{1},...,α_{k}} is zero except for finitely many α’s then we have a Laurent polynomial. The constant term of a Laurent formal power series f(x) = f(x_{1}, …, x_{k}), denoted by CT f(x), is the coefficient of x_{1}^{0} … x_{k}^{0}, i.e. a_{0,0,...,0,0}.

CRUCIAL FACTS

Crucial Fact ℵ_{0}: A rational function f(x_{1}, …, x_{k}) possesses a Laurent expansion if it is of the form

f(x_{1}, …, x_{k}) = \frac{P (x_{1}, …, x_{k})}{x_{1}^{γ_{1}} … x_{k}^{γ_{k}}Q(x_{1}, …, x_{k})} ,

where P and Q are polynomials in (x_{1}, …, x_{k}), and most importantly, Q has a non-zero constant term, i.e. Q(0, 0, …, 0) ≠ 0, and the γ_{i} are (not necessarily positive) integers.

Proof: Let the constant term of Q, Q(0, 0, …, 0), be denoted by C. Expanding, we get:

\frac{1}{Q(x_{1}, …, x_{k})} = (C+ ∑_{α_{1}+...+α_{k}>0} q_{α_{1},...,α_{k}}x_{1}^{α_{1}} … x_{k}^{α_{k}})^{−1} = ∑_{l=0}^{∞}(−1)^{l} \frac{(∑_{α_{1}+...+α_{k}>0} q_{α_{1},...,α_{k}}x_{1}^{α_{1}} … x_{k}^{α_{k}})^{l}}{C^{l+1}} .

The right side “converges” in the ring of formal power series (the coefficient of any fixed monomial gets contributions from only finitely many terms in the above sum). It follows that, under the condition on Q, P/Q also possesses a formal power series, and dividing by the monomial x_{1}^{γ_{1}} … x_{k}^{γ_{k}} results in a formal Laurent series.

The condition Q(0, …, 0) ≠ 0 is necessary, since, for example, 1/(x + y) does not have a formal Laurent series. (Try it!)

Iterated Constant-Terming

The constant term CT_{x}f(x) of a rational function f(x) of a single variable x, is defined to be the coefficient of x^{0} in its Laurent expansion. This is well-defined, since such a rational function f(x) of the single variable, x, can always be written in the form P (x)/(x^{a}Q(x)), where P (x) is a polynomial and Q(x) is a polynomial with Q(0) ≠ 0, and a is a non-negative integer. By crucial fact ℵ_{0}, it possesses a genuine Laurent expansion, and CT_{x}f(x) is always well-defined.

Consider now an arbitrary rational function f(x_{1}, …, x_{k}). It can be viewed as a rational function in the variable x_{k}, with coefficients that are rational functions of the other variables (x_{1}, …, x_{k−1}). It follows that CT_{x_{k}}f(x_{1}, …, x_{k}) is well-defined, and is a certain rational function of (x_{1}, …, x_{k−1}), Hence CT_{x_{k−1}}CT_{x_{k}}f(x_{1}, …, x_{k}) is well-defined, and is a certain rational function of (x_{1}, …, x_{k−2}) and so on, until we get that CT_{x_{1}}CT_{x_{2}} … CT_{x_{k}}f(x_{1}, …, x_{k}), that we will abbreviate to CT_{x_{1},...,x_{k}}f(x_{1}, …, x_{k}), is well-defined and is a certain number.

More formally we have the following recursive definition:

Definition ITERCT: Let f(x_{1}, …, x_{k}) be any rational function. For r = 1, …, k, CT_{x_{1},...,x_{r}}f(x_{1}, …, x_{k}) is equal to CT_{x_{1}}f(x_{1}, …, x_{k}) if r = 1, and otherwise

CT_{x_{1},...,x_{r}}f(x_{1}, …, x_{k}) := CT_{x_{1},...,x_{r−1}} [CT_{x_{r}}f(x_{1}, …, x_{k})] .

Crucial Fact ℵ_{1}: Let f(x_{1}, …, x_{k}) be a rational function that possesses a Laurent formal power series, and that is antisymmetric w.r.t. two variables x_{i}, x_{j} (i.e. f|_{x_{i}↔x_{j}} = −f.) Then CT_{x_{1},...,x_{k}}f(x_{1}, …, x_{k}) = 0.

Crucial Fact ℵ_{2}: Let P (x) be a polynomial of degree ≤ 2A, in (the single variable) x, that is anti-symmetric w.r.t. to the operation x → 1 − x (i.e. P (1 − x) = −P (x)). Then

CT_{x} [\frac{P (x)}{(1 − x)^{A+1}x^{A}} ] = 0.

Proof: Immediate from crucial fact ℵ_{5} below.

Crucial Fact ℵ_{3}: Let f(x_{1}, …, x_{k}) be a rational function, and define a discrete function F (a_{1}, …, a_{k}) by

F (a_{1}, …, a_{k}) := CT_{x_{1},...,x_{k}} \frac{f(x_{1}, …, x_{k})}{x_{1}^{a_{1}} … x_{k}^{a_{k}}} .

Then for any Laurent polynomial P (x_{1}, …, x_{k}), we have

P (A_{1}^{−1}, …, A_{k}^{−1})F (a_{1}, …, a_{k}) = CT_{x_{1},...,x_{k}} \frac{P (x_{1}, …, x_{k})f(x_{1}, …, x_{k})}{x_{1}^{a_{1}} … x_{k}^{a_{k}}} .

Proof: This is obvious if P is a monomial. Since a polynomial is a linear combination of monomials, and both sides are linear in P, it is also clear in general.

Crucial Fact ℵ_{4} (The Stanton-Stembridge trick): For any permutation π ∈ S_{k} and any rational function that possesses a formal Laurent series, f(x) = f(x_{1}, …, x_{k}), we have

CT_{x_{1},...,x_{k}} [πf(x)] = CT_{x_{1},...,x_{k}}f(x) .

Equivalently:

CT_{x_{π(1)},...,x_{π(k)}}f(x) = CT_{x_{1},...,x_{k}}f(x) .

Proof: Applying π amounts to renaming the variables. However, the constant term is obviously unaffected by this renaming.

Warning: Crucial fact ℵ_{4} is false if the rational function f does not possess a Laurent series, for example when f(x_{1}, x_{2}) = x_{1}/(x_{1} + x_{2}).

Crucial Fact ℵ_{5}: Let A be a non-negative integer, and let P (x) be a Laurent polynomial in x of degree ≤ 2A, then

CT_{x} [\frac{P (x)}{(1 − x)^{A+1}x^{A}} ] = CT_{x} [\frac{P (1 − x)}{(1 − x)^{A+1}x^{A}} ] .

Proof: P (x) is a linear combination of powers x^{b}, for b ≤ 2A. If P (x) = x^{b}, with A < b ≤ 2A, both sides vanish, while for P (x) = x^{b}, with b ≤ A, we have

CT_{x} [\frac{x^{b}}{(1 − x)^{A+1}x^{A}} ] = CT_{x} [\frac{1}{(1 − x)^{A+1}x^{A−b}} ] = \binom{2A − b}{A − b}

= \binom{2A − b}{A} = CT_{x} [\frac{1}{(1 − x)^{A−b+1}x^{A}} ] = CT_{x} [\frac{(1 − x)^{b}}{(1 − x)^{A+1}x^{A}} ] .

We also need the celebrated

Vandermonde’s Determinant Identity:

∑_{π∈S_{k}} sgn(π) · π(∏_{i=1}^{k} x_{i}^{i−1}) = ∏_{1≤i<j≤k}(x_{j} − x_{i}) .

Proof: View both sides as polynomials in x_{1} of degree k − 1. Both sides agree (and in fact are zero) at x_{1} = x_{2}, …, x_{1} = x_{k}, and they also agree at x_{1} = 0 by induction on k. Since they agree at k distinct values, they agree everywhere.

A longer, but much nicer, proof (that turned out to be seminal[ZB]) was given by Ira Gessel[G].

Iterated Residues

Later, we will find it necessary to convert our constant-term expressions to “residue” expressions. People who, like myself, (and John Riordan), are horrified by analysis, need not worry. The residue, Res_{x}f(x), of a rational function of a single variable x, is defined as the coefficient of x^{−1} in the (formal) Laurent expansion of f(x). It is well-defined for the same reason that CT_{x}f(x) is: a function of a single variable always possesses a Laurent series, thanks to crucial fact ℵ_{0}.

the electronic journal of combinatorics 3 (2) (1996), #R13 11

The iterated residue Res_{x_{1},...,x_{k}}f is defined to be Res_{x_{1}}[Res_{x_{2}}[… [Res_{x_{k}}f] …]]. [Try out IterRes in

ROBBINS].

Trivial (Yet Crucial) Fact ℵ_{6} :

CT_{x_{1},...,x_{k}}f(x_{1}, …, x_{k}) = Res_{x_{1},...,x_{k}} [\frac{f(x_{1}, …, x_{k})}{x_{1} … x_{k}}] .

For future reference, we need to recast crucial facts ℵ_{4} and ℵ_{5} in terms of residues. Crucial Fact ℵ′_{4} (The Stanton-Stembridge trick): For any permutation π ∈ S_{k} and any rational function that possesses a formal Laurent series, f(x) = f(x_{1}, …, x_{k}), we have

Res_{x_{1},...,x_{k}}[πf(x)] = Res_{x_{1},...,x_{k}}f(x) .

Equivalently:

Res_{x_{π(1)},...,x_{π(k)}}f(x) = Res_{x_{1},...,x_{k}}f(x) .

Crucial Fact ℵ′_{5}: Let A be a non-negative integer, and let P (x) be a Laurent polynomial in x of degree ≤ 2A, then

Res_{x} [\frac{P (x)}{(1 − x)^{A+1}x^{A+1}} ] = Res_{x} [\frac{P (1 − x)}{(1 − x)^{A+1}x^{A+1}} ] .

antisymmetrizers Crucial Fact ℵ_{7}: For any rational function f(x_{1}, …, x_{k}), its antisymmetrizer w.r.t. S_{k}:

∑_{π∈S_{k}} sgn(π) · πf(x_{1}, …, x_{k}) ,

is an S_{k}- antisymmetric function.

[ Try antisymmetrizerS k in ROBBINS].

Crucial Fact ℵ′_{7}: For any rational function f(x_{1}, …, x_{k}), its antisymmetrizer w.r.t. W (B_{k}):

∑_{g∈W (B_{k})} sgn(g) · gf(x_{1}, …, x_{k}) ,

is a W (B_{k})-anti-symmetric function.

[ Try antisymmetrizerWB k in ROBBINS].

Crucial Fact ℵ_{8}: Any S_{k}− antisymmetric polynomial is divisible by

∏_{1≤i<j≤k}(x_{j} − x_{i}) .

Proof: Let’s view the polynomial as a polynomial in x_{1}. By anti-symmetry, it vanishes at x_{1} = x_{i}, for i = 2, 3, …, k, hence is divisible by (x_{1} − x_{2}) ⋯ (x_{1} − x_{n}). Similarly (or by (anti-)symmetry) it is also divisible by all (x_{i} − x_{j}), 2 ≤ i < j ≤ k, and hence by their product.

Crucial Fact ℵ′_{8}: Any W (B_{k})− antisymmetric polynomial is divisible by

Δ_{k}(x_{1}, …, x_{k}) := ∏_{i=1}^{k}(1 − 2x_{i}) ∏_{1≤i<j≤k}(x_{j} − x_{i})(x_{j} + x_{i} − 1) .  (Delta)

Proof: Let’s view the polynomial as a polynomial in x_{1}. By W (B_{k})-antisymmetry, it vanishes at x_{1} = x_{i}, for i = 2, 3, …, k, as well as at x_{1} = x̄_{i}, and at x_{1} = 1/2. Hence it is divisible by

(1 − 2x_{1}) ∏_{j=2}^{k}(x_{1} − x_{j})(x_{1} + x_{j} − 1) .

Similarly, (or by (anti-)symmetry) it is divisible by all the other factors of Δ_{k}, and hence by Δ_{k} itself.

Act I. COUNTING MAGOG

And I will send a fire on Magog … and they shall know that I am the Lord.

(Ezekiel XXXIX,6)

Recall that an n × k-Magog trapezoid, where n ≥ k ≥ 1, is a trapezoidal array of integers (c_{i,j}), 1 ≤ i ≤ k, 1 ≤ j ≤ n − i + 1, such that:

(i) 1 ≤ c_{i,j} ≤ j , (ii) c_{i,j} ≥ c_{i+1,j} , (iii) c_{i,j} ≤ c_{i,j+1} .

Sublemma 1.1: The total number of n × k− Magog trapezoids, let’s call it b_{k}(n), is given by the following constant term expression:

b_{k}(n) = CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{n+k−i−1}(x̄_{i})^{n+k+1} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})}\} ,  (MagogT otal)

where,

Δ_{k}(x_{1}, ..., x_{k}) := ∏_{i=1}^{k}(1 − 2x_{i}) ∏_{1≤i<j≤k}(x_{j} − x_{i})(x_{j} + x_{i} − 1)  .  (Delta)

[ Type ‘S11(k,n):’ in ROBBINS, for specific k,n.]

Proof: Let B_{k}(n; a_{1}, ..., a_{k}) be the number of n × k Magog trapezoids (c_{i,j}), such that for i = 1, …, k, c_{i,n−i+1} = a_{i}. In other words, the rightmost border is prescribed by the a_{i}. By the definition of Magog trapezoids, the natural domain of the (k + 1) − variable discrete function B_{k}(−; −, …, −) is

Land Of Magog_{k} :=

{(n; a_{1}, …, a_{k}) | n ≥ k , n ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{k} ≥ 1 , and a_{i} ≤ n−i+1 for i = 1 , …, k}.

It is convenient to extend this region to the larger region

{(n; a_{1}, …, a_{k}) | n ≥ k , n ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{k} ≥ 1 },

and to define B_{k}(n; a_{1}, …, a_{k}) to be 0 whenever a_{i} > n − i + 1 for one or more i (1 ≤ i ≤ k). This makes perfect combinatorial sense, since the number of Magog-trapezoids with such a_{i}’s, that break the rules, is 0.

The following subsublemma gives a constant term expression for B_{k}.

Subsublemma 1.1.1: Let

C_{k}(n; a_{1}, …, a_{k}) := CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, ..., x_{k})}{∏_{i=1}^{k} x_{i}^{a_{i}+k−i−1}(x̄_{i})^{k+n}} \} ,

the electronic journal of combinatorics 3 (2) (1996), #R13 14

where Δ_{k} is defined in Eq. (Delta) in the statement of sublemma 1.1 above. For n ≥ k ≥ 1 and for all (n; a_{1}, …, a_{k}) for which n ≥ a_{1} ≥ … ≥ a_{k} ≥ 1, we have:

B_{k}(n; a_{1}, ..., a_{k}) = C_{k}(n; a_{1}, ..., a_{k}) .

[ Type ‘S111(k,n):’ in ROBBINS, for specific k,n.]

Proof: It is convenient to extend B_{k} even further to the following larger domain:

\overline{Land Of Magog_{k}} :=

{(n; a_{1}, …, a_{k}) | n ≥ k ≥ 1, n − a_{1} ≥ −1 , a_{1} − a_{2} ≥ −1, …, a_{k−1} − a_{k} ≥ −1 , a_{k} ≥ 0 } , and to define B_{k} to be zero in the “no-man’s-land” points that are in \overline{Land Of Magog_{k}} but not in Land Of Magog_{k}. We will prove that subsublemma 1.1.1 holds in this larger domain \overline{Land Of Magog_{k}}. This would follow from the following three subsubsublemmas. Subsubsublemma 1.1.1.1: Let k ≥ 1. The following partial recurrence holds in the subset of \overline{Land Of Magog_{k}} of points (n; a_{1}, …, a_{k}) for which n > k, and n ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{k} ≥ 1:

{∏_{i=1}^{k}(I − A_{i}^{−1})} B_{k}(n; a_{1}, …, a_{k}) = B_{k}(n − 1 ; a_{1}, …, a_{k}) .  (P ΔE(B_{k}))

B_{k}(n; a_{1}, …, a_{k}) also satisfies the following initial/boundary conditions in (n; a_{1}, …, a_{k}) ∈ \overline{Land Of Magog_{k}}: For i = 1, 2, …, k − 1,

B_{k}(n; a_{1}, …, a_{k}) = 0 , on a_{i} − a_{i+1} = −1 . (B1_{i})

Also:

B_{k}(n; a_{1}, …, a_{k}) = 0 , on a_{k} = 0 . (B1_{k})

Furthermore:

B_{k}(n; n + 1 , a_{2} , …, a_{k}) = 0 , and  (B2)
B_{k}(k; a_{1}, …, a_{k−1}, a_{k}) = B_{k−1}(k; a_{1}, …, a_{k−1})δ(a_{k}, 1) ,  (B3)

where, as usual, δ(i, j) is 1 or 0 according to whether i = j is true or false respectively. Finally, B_{k}(n; −) satisfies the “Eve” condition:

B_{1}(1; a_{1}) = δ(a_{1}, 1),  (1 ; a_{1}) ∈ \overline{Land Of Magog_{1}} .  (B4)

[ Type ‘S1111all(k,n):’ in ROBBINS, for specific k,n.]

Proof: Let’s try to compute B_{k}(n; −) from B_{k}(n − 1 ; −). By looking at what vectors (b_{1}, …, b_{k}) can occupy the diagonal immediately to the left of the rightmost one, c_{i,n−i} = b_{i}, say, we get a recurrence, valid for n > k and all (n; a_{1}, …, a_{k}) ∈ Land Of Magog_{k}:

B_{k}(n; a_{1}, …, a_{k}) = ∑_{(b_{1},...,b_{k})} B_{k}(n − 1 ; b_{1}, …, b_{k}) .  (Ekhad)

The summation extends over all the b = (b_{1}, …, b_{k}) such that a_{i+1} ≤ b_{i} ≤ min(a_{i}, n − i) , i = 1 … k − 1 , b_{k} ≤ min(a_{k}, n − k). Note that these conditions imply that n − 1 ≥ b_{1} ≥ b_{2} … ≥ b_{k}.

(Ekhad) can be used to compile a table of B_{k}, together with the initial condition

B_{k}(k; a_{1}, …, a_{k−1}, 1) = B_{k−1}(k; a_{1}, …, a_{k−1}) ,

that holds because when n = k, we have a Magog triangle, and for it necessarily c_{k,1} = 1 and there is a one-one correspondence between k × k Magog triangles and k × (k − 1) Magog-trapezoids obtained by deleting that c_{k,1} entry (or putting it back, if one wishes to go the other way.) This enables us to go down in the k−ladder until we reach k = 1 for which B_{1}(1; 1) = 1.

We can extend the set of (n − 1; b_{1}, …, b_{k}) over which the summation in (Ekhad) takes place, so that (Ekhad) becomes (Ekhad′):

B_{k}(n; a_{1}, …, a_{k}) = ∑_{a_{i+1}≤b_{i}≤a_{i} (1≤i≤k)} B_{k}(n − 1 ; b_{1}, b_{2}, …, b_{k}) ,  (Ekhad′)

(where we put a_{k+1} = 0,) since, whenever b_{i} > n − i, the contribution is zero, by our extended definition of B_{k}. The next thing to observe is that (Ekhad′) holds not only for (n; a_{1}, …, a_{k}) ∈ Land Of Magog_{k} but for all points for which n ≥ a_{1} ≥ … ≥ a_{k} ≥ 1, since for these extra points, the left side is 0 by the extended definition of B_{k}, and all the terms on the right side are also 0 for the same reason. Now,

{(n − 1 ; b_{1}, …, b_{k}) | a_{2} ≤ b_{1} ≤ a_{1} , a_{3} ≤ b_{2} ≤ a_{2} , …, a_{k} ≤ b_{k−1} ≤ a_{k−1} , b_{k} ≤ a_{k} }
−{(n − 1 ; b_{1}, …, b_{k}) | a_{2} ≤ b_{1} ≤ (a_{1} − 1), a_{3} ≤ b_{2} ≤ a_{2} , …, a_{k} ≤ b_{k−1} ≤ a_{k−1} , b_{k} ≤ a_{k} }
= {(n − 1 ; a_{1}, b_{2}, …, b_{k}) | a_{3} ≤ b_{2} ≤ a_{2} , …, a_{k} ≤ b_{k−1} ≤ a_{k−1} , b_{k} ≤ a_{k} } .

Using (Ekhad′), we get that for all n ≥ a_{1} ≥ … ≥ a_{k} ≥ 1:

(I − A_{1}^{−1})B_{k}(n; a_{1}, …, a_{k}) = ∑_{a_{i+1}≤b_{i}≤a_{i} (2≤i≤k)} B_{k}(n − 1 ; a_{1}, b_{2}, …, b_{k}) ,

(with the convention that a_{k+1} = 0,) for (n; a_{1}, …, a_{k}) for which n > k and n ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{k} ≥ 1.

Iterating the process, we get, in turn, that

(I −A_{1}^{−1}) … (I −A_{l}^{−1})B_{k}(n; a_{1}, …, a_{k}) = ∑_{a_{i+1}≤b_{i}≤a_{i} (l+1≤i≤k)} B_{k}(n−1 ; a_{1}, …, a_{l}, b_{l+1}, …, b_{k}) ,

for l = 2, …, k. The final l = k is (P ΔE(B_{k})).

The boundary/initial conditions (B1)-(B2) follow from the fact that B_{k} is defined to be 0 in the ‘boundary’ \overline{Land Of Magog_{k}} \ Land Of Magog_{k}, while (B3) and (B4) follow straight from the (combinatorial) definition of B_{k}. This completes the proof of (sub)^{3}lemma 1.1.1.1.

Subsubsublemma 1.1.1.2: Let C_{k}(n : a_{1}, …, a_{k}) be the constant term expression defined in the statement of subsublemma 1.1.1. The following partial recurrence holds in the subset of \overline{Land Of Magog_{k}} of points (n; a_{1}, …, a_{k}) for which n > k, and n ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{k} ≥ 1:

{∏_{i=1}^{k}(I − A_{i}^{−1})} C_{k}(n; a_{1}, …, a_{k}) = C_{k}(n − 1 ; a_{1}, …, a_{k}) .  (P ΔE(C_{k}))

C_{k}(n; a_{1}, …, a_{k}) also satisfies the following initial/boundary conditions for (n; a_{1}, …, a_{k}) ∈ \overline{Land Of Magog_{k}}.

For i = 1, 2, …, k − 1,

C_{k}(n; a_{1}, …, a_{k}) = 0 ,  on  a_{i} − a_{i+1} = −1 .  (C1_{i})

Also:

C_{k}(n; a_{1}, …, a_{k}) = 0 ,  on  a_{k} = 0 .  (C1_{k})

Furthermore:

C_{k}(n; n + 1 , a_{2} , …, a_{k}) = 0 , and  (C2)
C_{k}(k; a_{1}, …, a_{k−1}, a_{k}) = C_{k−1}(k; a_{1}, …, a_{k−1})δ(a_{k}, 1) ,  (C3)

and

C_{1}(1; a_{1}) = δ(1, a_{1}) , (1; a_{1}) ∈ \overline{Land Of Magog_{1}}  .  (C4)

[ Type ‘S1112(k):’ in ROBBINS, for specific k.]

Proof: (P ΔE(C_{k})) follows from crucial fact ℵ_{3}. (In fact it holds for all (n; a_{1}, …, a_{k}), without the indicated restriction, but we only need it there.)

(C1_{i}), (1 ≤ i < k), is satisfied by crucial fact ℵ_{1}. (C1_{k}) is satisfied, since when a_{k} = 0, the constant-termand of the constant term expression defining C_{k} is a multiple of x_{k}, and hence its constant term w.r.t. to x_{k}, and hence w.r.t. to all variables, is 0. (C2) is satisfied thanks to crucial fact ℵ_{2}, since the degree of the numerator in x_{1}, 2k − 1 is ≤ 2(n + k − 1) (because we have n ≥ k ≥ 1.)

The proof of (C3) is not quite so easy. First let’s prove (C3) when a_{k} = 1. Since

Δ_{k}(x_{1}, …, x_{k}) = Δ_{k−1}(x_{1}, …, x_{k−1}) · (1 − 2x_{k}) ∏_{i=1}^{k−1}(x_{k} − x_{i})(x_{k} − x̄_{i}) ,

we have

C_{k}(k; a_{1}, …, a_{k−1}, 1) =

CT_{x_{1},...,x_{k−1}} \{\frac{Δ_{k−1}(x_{1}, …, x_{k−1})}{∏_{i=1}^{k−1}(x_{i}^{a_{i}+k−i−1}x̄_{i}^{2k})} · CT_{x_{k}} [\frac{(1 − 2x_{k}) ∏_{i=1}^{k−1}(x_{i} − x_{k})(x̄_{i} − x_{k})}{x_{k}^{0}(x̄_{k})^{2k}}]\}

= CT_{x_{1},...,x_{k−1}} \{\frac{Δ_{k−1}(x_{1}, …, x_{k−1})}{∏_{i=1}^{k−1}(x_{i}^{a_{i}+k−i−1}x̄_{i}^{2k})} · [∏_{i=1}^{k−1}(x_{i}x̄_{i})]\}

= CT_{x_{1},...,x_{k−1}} \{\frac{Δ_{k−1}(x_{1}, …, x_{k−1})}{∏_{i=1}^{k−1}(x_{i}^{a_{i}+(k−1)−i−1}x̄_{i}^{(k−1)+k})}\} = C_{k−1}(k; a_{1}, …, a_{k−1}) .

We will now show that (C3) holds when a_{k} ≥ 2. When (k; a_{1}, …, a_{k−1}, a_{k}) ∈ \overline{Land Of Magog_{k}} does not satisfy k ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{k}, then the left side of (C3) is already known to be 0 in virtue of (C1) or (C2). We are left with the task of showing that when k ≥ a_{1} ≥ … ≥ a_{k} ≥ 2, the following expression vanishes:

C_{k}(k; a_{1}, …, a_{k}) = CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, ..., x_{k})}{∏_{i=1}^{k} x_{i}^{a_{i}+k−i−1}(x̄_{i})^{2k}} \} = CT_{x_{1},...,x_{k}} \{\frac{[∏_{i=1}^{k} x_{i}^{k−a_{i}+i}] Δ_{k}(x_{1}, ..., x_{k})}{∏_{i=1}^{k} x_{i}^{2k−1}(x̄_{i})^{2k}} \}

= Res_{x_{1},...,x_{k}} \{\frac{[∏_{i=1}^{k} x_{i}^{k−a_{i}+i}] Δ_{k}(x_{1}, ..., x_{k})}{∏_{i=1}^{k} x_{i}^{2k}(x̄_{i})^{2k}} \} .  (Efes)

In order to show that the right side of (Efes) indeed vanishes, we will first prove a (sub)^{4}lemma that asserts that, under the stated conditions on the a_{i}, the right side of (Efes) remains invariant whenever its residuand is replaced by any of its images under the action of the group of signed permutations W (B_{k}).

Subsubsubsublemma 1.1.1.2.1: Let F_{k;a_{1},...,a_{k}}(x_{1}, …, x_{k}) be the residuand of the right side of (Efes), i.e.

F_{k;a_{1},...,a_{k}}(x_{1}, …, x_{k}) := \frac{[∏_{i=1}^{k} x_{i}^{k−a_{i}+i}] Δ_{k}(x_{1}, ..., x_{k})}{∏_{i=1}^{k} x_{i}^{2k}(x̄_{i})^{2k}} ,

where k ≥ a_{1} ≥ a_{2} … ≥ a_{k} ≥ 2, and Δ_{k} is defined in Eq. (Delta) in the statement of sublemma 1.1. Then for any signed permutation g = (π, ε) ∈ W (B_{k}), we have

Res_{x_{1},...,x_{k}} {g [ F_{k;a_{1},...,a_{k}}(x) ] } = Res_{x_{1},...,x_{k}} {F_{k;a_{1},...,a_{k}}(x)} .

[ Type ‘S11121(k,a):’ in ROBBINS, for specific k and a.]

Proof: Δ_{k}, defined in (Delta), is a polynomial of degree 2k − 1 in any one of its variables. By Crucial Fact ℵ′_{5} we can repeatedly change all the −1’s in ε to +1’s since the numerator is a polynomial of degree ≤ (2k − 1) + (k + k − 2) = 4k − 3 ≤ 2(2k − 1). Finally we can change the π in g into the identity element, by Crucial Fact ℵ′_{4}. This completes the proof of (sub)^{4}lemma 1.1.1.2.1.

We can now replace the right side of (Efes) by the iterated residue of the average of all its images under W (B_{k}):

Res_{x_{1},...,x_{k}} \{F_{k;a_{1},...,a_{k}}(x)\} = \frac{1}{2^{k}k!} ∑_{g∈W (B_{k})} Res_{x_{1},...,x_{k}} \{g[F_{k;a_{1},...,a_{k}}(x)]\}

= \frac{1}{2^{k}k!}Res_{x_{1},...,x_{k}} \{ ∑_{g∈W (B_{k})} g [ F_{k;a_{1},...,a_{k}}(x) ] \} .  (Efes′)

We now will prove that not only is the iterated residue on the right side of (Efes′) identically zero, but so is the whole residuand.

Subsubsubsublemma 1.1.1.2.2: Let F_{k;a_{1},...,a_{k}}(x_{1}, …, x_{k}) be the residuand of the right side of (Efes), i.e.

F_{k;a_{1},...,a_{k}}(x_{1}, …, x_{k}) := \frac{[∏_{i=1}^{k} x_{i}^{k−a_{i}+i}] Δ_{k}(x_{1}, ..., x_{k})}{∏_{i=1}^{k} x_{i}^{2k}(x̄_{i})^{2k}} ,

where k ≥ a_{1} ≥ a_{2} … ≥ a_{k} ≥ 2, and Δ_{k} is defined in Eq. (Delta) in the statement of sublemma 1.1. Then

∑_{g∈W (B_{k})} g [F_{k;a_{1},...,a_{k}}(x)] = 0 .  (Efes′′)

[ Type ‘S11122(k,a):’ in ROBBINS, for specific k and a.]

Proof: By the symmetry of the denominator and the anti-symmetry of Δ_{k} w.r.t. the group of signed permutations W (B_{k}), we have:

∑_{g∈W (B_{k})} g [F_{k;a_{1},...,a_{k}}(x)] = \frac{\{∑_{g∈W (B_{k})} sgn(g) · g [∏_{i=1}^{k} x_{i}^{k−a_{i}+i}]\} Δ_{k}(x_{1}, ..., x_{k})}{∏_{i=1}^{k} x_{i}^{2k}(x̄_{i})^{2k}} . (Efes′′′)

By crucial fact ℵ′_{7}, the expression inside the braces of (Efes′′′) is a W (B_{k})- anti-symmetric polynomial. By crucial fact ℵ′_{8}, it is divisible by Δ_{k}(x_{1}, …, x_{k}). The degree in x_{1} of the polynomial inside the braces of (Efes′′′) is ≤ k − 2 + k = 2k − 2, while the degree of Δ_{k}(x), in x_{1}, is 2k − 1. Hence it must be the zero polynomial. This completes the proof of subsubsubsublemma 1.1.1.2.2 .

This completes the proof that C_{k} satisfies (C3). Finally (C4) is completely routine. This completes the proof of subsubsublemma 1.1.1.2.

Subsubsublemma 1.1.1.3: There is a unique sequence of discrete functions X_{k}(n; a_{1}, …, a_{k}), defined for k ≥ 1 and (n; a_{1}, …, a_{k}) ∈ \overline{Land Of Magog_{k}}, satisfying the following partial difference equation:

{∏_{i=1}^{k}(I − A_{i}^{−1})} X_{k}(n; a_{1}, …, a_{k}) = X_{k}(n − 1 ; a_{1}, …, a_{k}) ,  (P ΔE(X_{k}))

for n > k and n ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{k} ≥ 1, and the following boundary/initial conditions for (n; a_{1}, …, a_{k}) ∈ \overline{Land Of Magog_{k}}.

For i = 1, 2, …, k − 1,

X_{k}(n; a_{1}, …, a_{k}) = 0 ,  on  a_{i} − a_{i+1} = −1 .  (X1_{i})

Also:

X_{k}(n; a_{1}, …, a_{k}) = 0 ,  on  a_{k} = 0 .  (X1_{k})

Furthermore:

X_{k}(n; n + 1 , a_{2} , …, a_{k}) = 0 and  (X2)
X_{k}(k; a_{1}, …, a_{k−1}, a_{k}) = X_{k−1}(k; a_{1}, …, a_{k−1})δ(a_{k}, 1) ,  (X3)

and

X_{1}(1; a_{1}) = δ(1, a_{1}) , (1; a_{1}) ∈ \overline{Land Of Magog_{1}}  .  (X4)

[ Type ‘S1113(k,n):’ in ROBBINS, for specific k and n.]

Proof: .

Subsublemma 1.1.1 now follows from subsubsublemmas 1.1.1.1, 1.1.1.2, and 1.1.1.3. This completes the proof of subsublemma 1.1.1.

Subsublemma 1.1.1 gave us a constant term expression for the number of n × k− Magog trapezoids with a prescribed rightmost border. In order to complete the proof of sublemma 1.1, we would have to sum them all up. In order to establish the constant term expression (MagogT otal) for b_{k}(n), we would need to go through an intermediary, not-so-nice expression, given by subsublemma 1.1.2 below.

Subsublemma 1.1.2: The number of n × k Magog-trapezoids, b_{k}(n), is given by the following constant term expression:

b_{k}(n) = CT_{x_{1},...,x_{k}} \{\frac{x_{1}x_{2}^{2} … x_{k}^{k} · Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n}x_{i}^{n+k−1}} · \frac{1}{(1 − x_{k})(1 − x_{k−1}x_{k}) … (1 − x_{k}x_{k−1} … x_{1})}\} .

(George)

[ Type ‘S112(k,n):’ in ROBBINS, for specific k and n.]

Proof: We will establish (George) by starting from the right side, and proving that it equals the left side. By the well-known symmetry property of the ‘=’ relation, it would follow that the left side is equal to its right side.

Since (1 − y)^{−1} = ∑_{α=0}^{∞} y^{α}, we have

(1−x_{k})^{−1}(1−x_{k−1}x_{k})^{−1} … (1−x_{k}x_{k−1} … x_{1})^{−1} = [ ∑_{α_{k}=0}^{∞} x_{k}^{α_{k}}][ ∑_{α_{k−1}=0}^{∞}(x_{k−1}x_{k})^{α_{k−1}}] … [ ∑_{α_{1}=0}^{∞}(x_{1} … x_{k−1}x_{k})^{α_{1}}]

= ∑_{0≤α_{1},...,α_{k}<∞} x_{1}^{α_{1}}x_{2}^{α_{1}+α_{2}} … x_{k}^{α_{1}+α_{2}+...+α_{k}} = ∑_{0≤λ_{1}≤...≤λ_{k}<∞} x_{1}^{λ_{1}} … x_{k}^{λ_{k}}  .

The right side of (George) is hence equal to:

CT_{x_{1},...,x_{k}} \{\frac{x_{1}x_{2}^{2} … x_{k}^{k} · Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n}x_{i}^{n+k−1}} · ∑_{0≤λ_{1}≤...≤λ_{k}<∞} x_{1}^{λ_{1}} … x_{k}^{λ_{k}} \}

= ∑_{0≤λ_{1}≤...≤λ_{k}<∞} CT_{x_{1},...,x_{k}} \{\frac{x_{1}x_{2}^{2} … x_{k}^{k} · Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n}x_{i}^{(n−λ_{i})+k−1}}\}

= ∑_{n≥(n−λ_{1})≥...≥ (n−λ_{k})>−∞} CT_{x_{1},...,x_{k}} \{\frac{x_{1}x_{2}^{2} … x_{k}^{k} · Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n}x_{i}^{(n−λ_{i})+k−1}}\}

= ∑_{n≥a_{1}≥...≥ a_{k}>−∞} CT_{x_{1},...,x_{k}} \{\frac{x_{1}x_{2}^{2} … x_{k}^{k} · Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n}x_{i}^{a_{i}+k−1}}\} .  (George′)

The sum on the right side of (George′) can be replaced by a sum over the restricted region n ≥ a_{1} ≥ … ≥ a_{k} ≥ 1, since whenever a_{k} < 1, the constant-termand there is a multiple of x_{k}, and hence its constant term is 0. So the right side of (George′) (and hence the right side of (George)) equals:

∑_{n≥a_{1}≥...≥ a_{k}≥1} CT_{x_{1},...,x_{k}} \{\frac{x_{1}x_{2}^{2} … x_{k}^{k} · Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n}x_{i}^{a_{i}+k−1}}\}

= ∑_{n≥a_{1}≥...≥ a_{k}≥1} C_{k}(n; a_{1}, …, a_{k}) = ∑_{n≥a_{1}≥...≥ a_{k}≥1} B_{k}(n; a_{1}, …, a_{k}) = b_{k}(n) , (George′′)

where the last equality in (George′′) is obvious, and the second-to-last equality follows from subsublemma 1.1.1. This completes the proof of subsublemma 1.1.2.

By crucial fact ℵ_{4}, we can replace the right side of (George) by the constant term of the average of all the S_{k}-images of its constant-termand. Since Δ_{k} is antisymmetric in (x_{1}, …, x_{k}), we see that b_{k}(n) equals

\frac{1}{k!}CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n}x_{i}^{n+k−1}} ( ∑_{π∈S_{k}} sgn(π) · π [\frac{x_{1}x_{2}^{2} … x_{k}^{k}}{(1 − x_{k})(1 − x_{k}x_{k−1}) … (1 − x_{k}x_{k−1} … x_{1})}])\} .

(Stanley)

We now need:

Subsublemma 1.1.3:

∑_{π∈S_{k}} sgn(π)·π [\frac{x_{1}x_{2}^{2} … x_{k}^{k}}{(1 − x_{k})(1 − x_{k}x_{k−1}) ⋯ (1 − x_{k}x_{k−1} … x_{1})}] = \frac{x_{1} ⋯ x_{k} ∏_{1≤i<j≤k}(x_{j} − x_{i})}{∏_{i=1}^{k}(1 − x_{i}) ∏_{1≤i<j≤k}(1 − x_{i}x_{j})} .

(Issai)

[ Type ‘S113(k);’ in ROBBINS, for specific k.]

Proof : See [PS], problem VII.47. Alternatively, (Issai) is easily seen to be equivalent to Schur’s identity that sums all the Schur functions ([Ma], ex I.5.4, p. 45). This takes care of subsublemma 1.1.3.

Inserting (Issai) into (Stanley), expanding ∏_{1≤i<j≤k}(x_{j} − x_{i}) by Vandermonde’s expansion,

∑_{π∈S_{k}} sgn(π) · π(x_{1}^{0}x_{2}^{1} ⋯ x_{k}^{k−1}) ,

using the antisymmetry of Δ_{k} once again, and employing crucial fact ℵ_{4}, we get the following string of equalities:

b_{k}(n) = \frac{1}{k!}CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n}x_{i}^{n+k−1}} (\frac{x_{1} ⋯ x_{k} ∏_{1≤i<j≤k}(x_{j} − x_{i})}{∏_{i=1}^{k}(1 − x_{i}) ∏_{1≤i<j≤k}(1 − x_{i}x_{j})})\}

= \frac{1}{k!}CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n+1}x_{i}^{n+k−2} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})} ( ∑_{π∈S_{k}} sgn(π) · π(x_{1}^{0}x_{2}^{1} … x_{k}^{k−1}))\}

= \frac{1}{k!} ∑_{π∈S_{k}} CT_{x_{1},...,x_{k}} \{π [\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n+1}x_{i}^{n+k−2} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})} (∏_{i=1}^{k} x_{i}^{i−1})]\}

= \frac{1}{k!} ∑_{π∈S_{k}} CT_{x_{1},...,x_{k}} \{π [\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n+1}x_{i}^{n+k−i−1} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})}]\}

= \frac{1}{k!} ∑_{π∈S_{k}} CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n+1}x_{i}^{n+k−i−1} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})}\}

= \frac{1}{k!} ( ∑_{π∈S_{k}} 1) CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n+1}x_{i}^{n+k−i−1} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})}\}

= CT_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{k+n+1}x_{i}^{n+k−i−1} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})}\} ,  (George′′′)

where in the last equality we have used Levi Ben Gerson’s celebrated result that the number of elements in S_{k} (the symmetric group on k elements,) equals k!. The extreme right of (George′′′) is exactly the right side of (MagogT otal). This completes the proof of sublemma 1.1.

the electronic journal of combinatorics 3 (2) (1996), #R13 22

Act II. COUNTING GOG And say, Thus saith the Lord God; Behold, I am against thee, O Gog …

(Ezekiel XXXIIX,3)

An n × k− Gog trapezoid (where n ≥ k ≥ 1) is a trapezoidal array of integers

(d_{i,j}) , 1 ≤ i ≤ n , 1 ≤ j ≤ min(k, n + 1 − i) ,

such that:

(i) d_{i,j} < d_{i,j+1} (ii) d_{i,j} ≤ d_{i+1,j} (iii) d_{i,j} ≥ d_{i+1,j−1}
(iv) d_{1,j} = j (v) d_{i,k} ≤ i + k − 1.

(Note that these five conditions imply that 1 ≤ d_{i,j} ≤ n.)

[ To view all n by k Gog trapezoids, for any given k and n, type ‘GOG(k,n):’ in ROBBINS. For example, GOG(3,4) would display all 4 by 3 Gog trapezoids.]

Sublemma 1.2: The total number of n × k− Gog trapezoids, let’s call it m_{k}(n), is given by the following constant term expression:

m_{k}(n) = CT_{x_{1},...,x_{k}} [\frac{Φ_{k}(x_{1}, …, x_{k})}{\{∏_{i=1}^{k} x_{i}^{n}(x̄_{i})^{n+i+1}\} \{∏_{1≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})\}}]  , (GogT otal)

where the polynomial Φ_{k}(x_{1}, …, x_{k}) is defined by:

Φ_{k}(x_{1}, …, x_{k}) = (−1)^{k} ∑_{g∈W (B_{k})} sgn(g) · g [∏_{i=1}^{k} x̄_{i}^{k−i}x_{i}^{k} ∏_{1≤i<j≤k}(1 − x_{i}x̄_{j})(1 − x̄_{i}x̄_{j})]  . (Gog_{1})

[ Type ‘S12(k,n):’ in ROBBINS, for specific k and n.]

Proof: Let M_{k}(n; a_{1}, a_{2}, …, a_{k}) be the number of n × k- Gog trapezoids

(d_{i,j}), 1 ≤ i ≤ n , 1 ≤ j ≤ min(k, n + 1 − i) ,

such that d_{n−k+i,k−i+1} = a_{i}, for i = 1, …, k. In other words: d_{n−k+1,k} = a_{1} , d_{n−k+2,k−1} = a_{2} , …, d_{n−k+i,k−i+1} = a_{i} , …, d_{n,1} = a_{k} .

The conceivable (n; a_{1}, …, a_{k}) range over the set

Land Of Gog_{k} := { (n; a_{1}, …, a_{k}) | n ≥ k , n ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{k} ≥ 1 , a_{1} ≥ k , a_{2} ≥ k − 1 , …, a_{k} ≥ 1 } .

[ To view this set, for specific k and n, type ‘LOGOG(k,n):’ in ROBBINS.]

For any (n; a_{1}, …, a_{k}) ∈ Land Of Gog_{k}, define the set:

T̃_{k}(n; a_{1}, …, a_{k}) := {(b_{1}, …, b_{k}) | n − 1 ≥ b_{1} ≥ b_{2} ≥ … ≥ b_{k} ≥ 1 , k − i + 1 ≤ b_{i} ≤ a_{i}} .

It turns out to be convenient (and most likely necessary) to introduce a related discrete function that we will call M̃_{k}. For n > k, and (n; a_{1} , …, a_{k}) ∈ Land Of Gog_{k}, define:

M̃_{k}(n; a_{1}, a_{2}, …, a_{k}) := ∑_{b∈_{T_{k}}(n; a_{1},...,a_{k})} M_{k}(n − 1 ; b_{1}, …, b_{k})  ,  (M̃_{k})

and when n = k > 1 define M̃_{k}(k; k, −, …, −) by

M̃_{k}(k; k, a_{2}, …, a_{k}) = M̃_{k−1}(k; a_{2}, …, a_{k})  , (k > 1) ,  (M̃_{k}(n = k))

while for n = k = 1 define

M̃_{1}(1; 1) := 1 .  (M̃_{k}(n = k = 1))

The following subsublemma gives a constant term expression for M̃_{k}.

Subsublemma 1.2.1: Let

H_{k}(n; a_{1}, …, a_{k}) := CT_{x_{1},...,x_{k}} \{\frac{Φ_{k}(x_{1}, ..., x_{k})}{\{∏_{i=1}^{k} x_{i}^{a_{i}−1}(x̄_{i})^{n+i}\} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})}\} , (H_{k})

where Φ_{k} is defined in the statement of sublemma 1.2 above. For all (n; a_{1} , …, a_{k}) ∈ Land Of Gog_{k}, we have

M̃_{k}(n; a_{1}, ..., a_{k}) = H_{k}(n; a_{1}, ..., a_{k}) .  (Gog)

[ Type ‘S121(k,n):’ in ROBBINS, for specific k and n.]

Proof: It is convenient to extend M̃_{k} to the following larger domain (except that we slightly ‘chop’ it when n = k):

\overline{Land Of Gog_{k}} := \{ (n; a_{1}, …, a_{k}) |n ≥ k , n − a_{1} ≥ −1 ,
a_{1} ≥ a_{2} ≥ … ≥ a_{k} , a_{1} ≥ k − 1 , a_{2} ≥ k − 2 , …, a_{k} ≥ 0
and a_{1} = n + 1 ⇒ a_{2} ≤ n and n = k = a_{1} ⇒ a_{2} < k)} ,

[ To view this set, for specific k and n, type ‘ELOGOG(k,n):’ in ROBBINS], and to define M̃_{k} to be 0 at all the

boundary points that are in \overline{Land Of Gog_{k}} \ Land Of Gog_{k}. Note that (M̃_{k}) extends to those boundary points for which a_{i} = k − i for one or more i’s, since then the summation-set, T̃_{k}, is the empty set. However, (M̃_{k}) does not hold for those boundary points for which a_{1} = n + 1.

We will prove that subsublemma 1.2.1 even holds in this larger domain \overline{Land Of Gog_{k}}. This would follow from the following three subsubsublemmas.

Subsubsublemma 1.2.1.1: Let k ≥ 1 and for any non-increasing vector of non-negative integers a = (a_{1}, …, a_{k}), define the partial difference operator P^{(a)} by:

P^{(a)}(A_{1}, …, A_{k}) := ∏_{{i|a_{i}−a_{i+1}>0}}(I − A_{i}^{−1})  ,

where we declare that a_{k+1} = 0. M̃_{k} satisfies the following partial recurrence:

P^{(a)}(A_{1}, …, A_{k})M̃_{k}(n; a_{1}, …, a_{k})
= M̃_{k}(n − 1 ; a_{1} , min(a_{1} − 1, a_{2}) , …, min(a_{k−1} − 1, a_{k}))  ,  (P ΔE(M̃_{k}))

valid whenever n > k and (n; a_{1}, …, a_{k}) ∈ Land Of Gog_{k}. M̃_{k}(n; a_{1}, …, a_{k}) also satisfies the following initial/boundary conditions for (n; a_{1} , …, a_{k}) ∈ \overline{Land Of Gog_{k}}:

M̃_{k}(n; a_{1}, …, a_{k}) = 0 on a_{i} = k − i  ,  (M1_{i})
M̃_{k}(n; n + 1, a_{2}, …, a_{k}) = 0 ,  (M2)
M̃_{k}(k; k, a_{2}, …, a_{k}) = M̃_{k−1}(k; a_{2}, …, a_{k})  ,  (M3)

and, finally the “Adam” condition:

M̃_{1}(1 ; 1) = 1  .  (M4)

[ Type ‘S1211all(k,n):’ in ROBBINS, for specific k and n.]

Proof: Consider a typical n × k Gog trapezoid (d_{i,j}) that is counted by M_{k}(n; a_{1}, …, a_{k}), where n > k and (n; a_{1} , …, a_{k}) ∈ Land Of Gog_{k}. This means that

d_{n−k+1,k} = a_{1} , d_{n−k+2,k−1} = a_{2} , …, d_{n−k+i,k−i+1} = a_{i} , …, d_{n,1} = a_{k} .

Now let

d_{n−k,k} = b_{1} , d_{n−k+1,k−1} = b_{2} , …, d_{n−k+i−1,k−i+1} = b_{i} , …, d_{n−1,1} = b_{k} .

By the conditions (i) − (v) defining Gogs, given right at the beginning of this section, it follows that the allowed b = (b_{1}, …, b_{k}) range over the set

T_{k}(n; a_{1}, …, a_{k}) :=

{(b_{1}, …, b_{k}) | n−1 ≥ b_{1} ≥ b_{2} ≥ … ≥ b_{k} ≥ 1 and k−i+1 ≤ b_{i} ≤ min(a_{i}, a_{i−1}−1) (i = 1, …, k) } ,

where a_{0} := ∞. By deleting d_{n,1} = a_{k} , d_{n−1,2} = a_{k−1} , …, d_{n−k+1,k} = a_{1} , we obtain a certain (n−1)×k− Gog trapezoid. Looking at all the conceivable possibilities for b = (b_{1}, …, b_{k}), we get the following (non-local) recurrence, valid for n > k, and (n; a_{1} , …, a_{k}) ∈ Land Of Gog_{k},

M_{k}(n; a_{1}, …, , a_{k}) = ∑_{b∈T_{k}(n; a_{1},...,a_{k})} M_{k}(n − 1 ; b_{1}, …, b_{k})  .  (Howard)

the electronic journal of combinatorics 3 (2) (1996), #R13 25

(Howard) Can be used to compile a table of M_{k} together with the obvious initial condition

M_{k}(k; k, a_{2}, …, a_{k}) = M_{k−1}(k; a_{2}, …, a_{k}) , (k > 1) , (Howard′)

(note that, when n = k, a_{1} must be k,) and the “Adam” condition M_{1}(1 ; 1) = 1. Using the definition (M̃_{k}), Eq. (Howard) can be rewritten as:

M_{k}(n; a_{1}, …, a_{k}) = M̃_{k}(n; a_{1} , min(a_{1} − 1, a_{2}) , …, min(a_{k−1} − 1, a_{k})) , (Bill)

valid for n > k and (n; a_{1}, …, a_{k}) ∈ Land Of Gog_{k}. We are now ready to prove that M̃_{k} satisfies (P ΔE(M̃_{k})) in the statement of the current subsubsublemma 1.2.1.1. Note that since a_{k} > 0, the factor (I − A_{k}^{−1}) is always present in P^{(a)}. Let (a_{1}, …, a_{k}) be arranged in maximal blocks of equal components as follows:

a_{1} = a_{2} = … = a_{r_{1}} > a_{r_{1}+1} = … = a_{r_{2}} > … > a_{r_{l−1}+1} = … = a_{r_{l}} ≥ 1 ,

where r_{l} = k, and r_{1}, r_{2} − r_{1}, …, r_{l} − r_{l−1}, are the lengths of (maximal) blocks of consecutive equal components of a. Let’s put

c_{1} := a_{r_{1}} , …, c_{l−1} := a_{r_{l−1}} , c_{l} := a_{r_{l}}(= a_{k}) .

We have:

P^{(a)} = (I − A_{r_{1}}^{−1}) … (I − A_{r_{l}}^{−1}) .

The recurrence that we have to show, (P ΔE(M̃_{k})), spells out to:

(I − A_{r_{1}}^{−1})(I − A_{r_{2}}^{−1}) … (I − A_{r_{l}}^{−1})M̃_{k}(n; c_{1}, …, c_{1}, c_{2}, …, c_{2}, …, …, c_{l}, …, c_{l})

= M̃_{k}(n − 1; c_{1}, c_{1} − 1, …, c_{1} − 1, c_{2}, c_{2} − 1, …, c_{2} − 1, …, …, c_{l}, c_{l} − 1, …, c_{l} − 1) ,

where the length of the ‘c_{i}’ block is r_{i} − r_{i−1}, for i = 1 … l (where we agree that r_{0} = 0.) Suppose first that c_{1} = a_{1} < n, so that (n − 1; a_{1} , …, a_{k}) ∈ Land Of Gog_{k}. Applying (I − A_{k}^{−1}) (note that k = r_{l}) to the sum (M̃_{k}), yields a sum over the subset:

T̃_{k}(n; a_{1}, …, a_{k−1}, a_{k}) \ T̃_{k}(n; a_{1}, …, a_{k−1}, a_{k} − 1) =

T̃_{k}(n; c_{1}, …, c_{1}, c_{2}, …, c_{2}, …, …, c_{l−1}, …, c_{l−1}, c_{l}, …, c_{l}, c_{l}) \
T̃_{k}(n; c_{1}, …, c_{1}, c_{2}, …, c_{2}, …, …, c_{l−1}, …, c_{l−1}, c_{l}, …, c_{l}, c_{l} − 1)
= {(b_{1}, …, b_{k}) | n − 1 ≥ b_{1} ≥ b_{2} ≥ … ≥ b_{k} ≥ 1 ,
k − i + 1 ≤ b_{i} ≤ a_{i} for i = 1, …, r_{l−1} , and b_{i} = c_{l} , for i = r_{l−1} + 1, …, k} .

The last equality follows from the fact that b_{r_{l−1}+1} ≥ … ≥ b_{r_{l}} = c_{l} and b_{r_{l−1}+1} ≤ c_{l} , implies that b_{r_{l−1}+1} = … = b_{r_{l}} = c_{l}. Applying next (I − A_{r_{l−1}}^{−1}) to this smaller sum, yields a sum with the same summand, but over the smaller subset:

{(b_{1}, …, b_{k}) | n − 1 ≥ b_{1} ≥ b_{2} ≥ … ≥ b_{k} ≥ 1 , k − i + 1 ≤ b_{i} ≤ a_{i} , for i = 1, …, r_{l−2} , b_{i} = c_{l−1} , for i = r_{l−2} + 1 … r_{l−1} , and b_{i} = c_{l} , for i = r_{l−1} + 1, …, k} .

Continuing to apply (I −A_{r_{i}}^{−1}) with i = l−2 , l−3 , …, 1, we keep getting a sum over continuously shrinking subsets of T̃_{k}, until at the end we get the sum of M_{k}(n − 1; b_{1}, …, b_{k}) over the singleton set

{(n − 1; b_{1}, …, b_{k}) = (n − 1; a_{1}, …, a_{k})} .

We have thus shown that, whenever n > k and (n; a_{1}, …, a_{k}) ∈ Land Of Gog_{k}, we have

P^{(a)}(A_{1}, …, A_{k})M̃_{k}(n; a_{1}, …, a_{k}) = M_{k}(n − 1 ; a_{1}, …, a_{k}) .

Now use (Bill), with n replaced by n − 1. ((Bill) holds with n replaced by n − 1 if n − 1 > k and (n − 1; a_{1}, ..., a_{k}) ∈ Land Of Gog_{k}. For this we need the assumed hypothesis a_{1} < n.)

This leaves those elements (n; a_{1}, ..., a_{k}) in Land Of Gog_{k}, n > k, for which (n − 1; a_{1}, ..., a_{k}) does not lie in Land Of Gog_{k}, namely the cases n − 1 = k or a_{1} = n. These are done in the next two paragraphs.

When n = k + 1, the sole surviving term, after applying P^{(a)} to (M̃_{k}), is M_{k}(k; k, a_{2}, …, a_{k}), which by (Howard′), equals M_{k−1}(k; a_{2}, …, a_{k}), which by (Bill) equals M̃_{k−1}(k; a_{2}, min(a_{2} − 1, a_{3}), …, min(a_{k−1}−1, a_{k})), which, in turn, by the definition (M̃_{k}(n = k)) equals M̃_{k}(k; k, a_{2}, min(a_{2}− 1, a_{3}), …, min(a_{k−1} − 1, a_{k})), which disposes of the case n = k + 1.

Now suppose that a_{1} = n, so that a_{1} = … = a_{r_{1}} = n. As before, applying (I −A_{r_{2}}^{−1}) … (I −A_{r_{l}}^{−1}) to the sum on the right of Eq. (M̃_{k}), leaves us a much reduced sum over the subset of T̃_{k}(n; a_{1}, …, a_{k}) for which b_{r_{1}+1} = a_{r_{1}+1}, …, b_{k} = a_{k}. Since we must have b_{1} ≤ n − 1 this is the same set as the one for which a_{1} = … = a_{r_{1}−1} = n and a_{r_{1}} = n − 1, so that applying (1 − A_{r_{1}}^{−1}) to that sum gives 0. But the right side of (P ΔE(M̃_{k})) is also 0 then, by the extended definition of M̃_{k}, since a_{1} = n =‘n − 1’+1, and n =‘n − 1’.

(M1_{i}) and (M2) hold because M̃_{k} was defined to be 0 there, while (M3) is the definition at n = k, given by (M̃_{k}(n = k)), and (M4) follows from the definition (M̃_{1}). This completes the proof of (sub)^{3}lemma 1.2.1.1.

Subsubsublemma 1.2.1.2: Let k ≥ 1, and for any non-increasing vector of non-negative integers a = (a_{1}, …, a_{k}), define the partial difference operator P^{(a)} by:

P^{(a)}(A_{1}, …, A_{k}) := ∏_{{i|a_{i}−a_{i+1}>0}}(I − A_{i}^{−1})  ,

where we declare that a_{k+1} = 0. The sequence of discrete functions H_{k}(n; a_{1}, …, a_{k}), (n ≥ k ≥ 1), defined in the statement of the subsublemma 1.2.1, satisfies the following partial recurrence:

P^{(a)}(A_{1}, …, A_{k})H_{k}(n; a_{1}, …, a_{k})
= H_{k}(n − 1 ; a_{1} , min(a_{1} − 1, a_{2}) , …, min(a_{k−1} − 1, a_{k}))  ,  (P ΔE(H_{k}))

valid whenever n > k and (n; a_{1}, …, a_{k}) ∈ Land Of Gog_{k}. H_{k}(n; a_{1}, …, a_{k}) also satisfies the following initial/boundary conditions for (n; a_{1} , …, a_{k}) ∈ \overline{Land Of Gog_{k}}:

H_{k}(n; a_{1}, …, a_{k}) = 0 on a_{i} = k − i  ,  (H1_{i})
H_{k}(n; n + 1, a_{2}, …, a_{k}) = 0 ,  (H2)
H_{k}(k; k, a_{2}, …, a_{k}) = H_{k−1}(k; a_{2}, …, a_{k})  ,  (H3)

and, finally the “Adam” condition

H_{1}(1 ; 1) = 1  .  (H4)

Proof: The task of proving this (sub)^{3}lemma will be divided between the following (sub)^{4}lemmas: 1.2.1.2.1, 1.2.1.2.2, 1.2.1.2.3, and 1.2.1.2.4, and 1.2.1.2.5, which will prove (P ΔE(H_{k})), (H1_{i}), (H2), (H3), and (H4) respectively.

Subsubsubsublemma 1.2.1.2.1: Let H_{k}(n; a_{1}, …, a_{k}) be the discrete function defined in the statement of subsublemma 1.2.1, i.e. :

H_{k}(n; a_{1}, …, a_{k}) := CT_{x_{1},...,x_{k}} \{\frac{Φ_{k}(x_{1}, ..., x_{k})}{\{∏_{i=1}^{k} x_{i}^{a_{i}−1}(x̄_{i})^{n+i}\} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})}\} ,

where Φ_{k} is the anti-symmetric polynomial defined in the statement of sublemma 1.2. (In fact all we need is that Φ_{k} is some anti-symmetric polynomial.) For all n > k, and (n; a_{1} , …, a_{k}) ∈ Land Of Gog_{k} (in fact whenever a_{1} ≥ … ≥ a_{k},) we have that the partial-recurrence equation (P ΔE(H_{k})), given in the statement of the parent (sub)^{3}lemma 1.2.1.2, holds.

[ Type ‘S12121all(k,n):’ in ROBBINS, for specific k and n.]

Proof: Suppose that we have:

a_{1} = a_{2} = … = a_{r_{1}} > a_{r_{1}+1} = … = a_{r_{2}} > … > a_{r_{l−1}+1} = … = a_{r_{l}} ≥ 1 ,

where r_{l} = k, and r_{1}, r_{2} − r_{1}, …, r_{l} − r_{l−1}, are the lengths of maximal blocks of equal components of a = (a_{1}, …, a_{k}). Putting c_{i} := a_{r_{i}}, for i = 1, …, l, we have to show that

(I − A_{r_{1}}^{−1})(I − A_{r_{2}}^{−1}) … (I − A_{r_{l}}^{−1})H_{k}(n; c_{1}, …, c_{1}, c_{2}, …, c_{2}, …, …, c_{l}, …, c_{l})
= H_{k}(n − 1; c_{1}, c_{1} − 1, …, c_{1} − 1, c_{2}, c_{2} − 1, …, c_{2} − 1, …, …, c_{l}, c_{l} − 1, …, c_{l} − 1) , (Rodica)

where, in the left, the block of c_{1} is r_{1}-component-long, the block of c_{2} is r_{2}- component-long, …, the block of c_{l} is r_{l}-component long. In the right side, the c_{i} − 1 block is r_{i} − 1 -component long, for i = 1, …, l.

By crucial fact ℵ_{3}, the difference between the left and right sides of (Rodica) equals:

CT_{x_{1},...,x_{k}} [\frac{\{x̄_{r_{1}} x̄_{r_{2}} … x̄_{r_{l}} − [x̄_{1}x̄_{2} … x̄_{k}](x_{2} … x_{r_{1}})(x_{r_{1}+2} … x_{r_{2}}) … (x_{r_{l−1}+2} … x_{r_{l}})\}Φ_{k}(x_{1}, …, x_{k})}{\{∏_{i=1}^{k} x_{i}^{a_{i}−1}(x̄_{i})^{n+i}\} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})}]

(Dave)

In order to prove (sub)^{4}lemma 1.2.1.2.1, we need to show that the constant-term expression in (Dave) is identically zero. To this end we need the following (sub)^{5} lemma:

Subsubsubsubsublemma 1.2.1.2.1.1: Let Jamie(x_{1}, …, x_{k}) be the polynomial in (x_{1}, …, x_{k}) inside the braces of (Dave), i.e. the polynomial:

Jamie(x_{1}, …, x_{k}) := ∏_{j=1}^{l} x̄_{r_{j}} − {∏_{i=1}^{k} x̄_{i}} {∏_{j=1}^{l} ∏_{i=r_{j−1}+2}^{r_{j}} x_{i}} .

Jamie(x_{1}, …, x_{k}) can be written as follows (recall that r_{l} = k and we put r_{0} = 0):

Jamie(x_{1}, …, x_{k}) = ∑_{{p=2 \atop p∉\{r_{1}+1,r_{2}+1,...,r_{l−1}+1\}}}^{k} P OL(x̂_{p−1}, x̂_{p}) · x̄_{p} (1 − x̄_{p−1}x_{p}),  (Herb)

where P OL(x̂_{p−1}, x̂_{p}) is shorthand for: “some polynomial of (x_{1}, …, x_{k}) that does not depend on the variables x_{p−1} and x_{p}”. (In other words, P OL(x̂_{p−1}, x̂_{p}) is some polynomial in the k − 2 variables (x_{1}, …, x_{p−2}, x_{p+1}, …, x_{k}).)

Proof: Since (let x̄_{0} := 1)

∏_{i=1}^{k} x̄_{i} = {∏_{j=1}^{l} ∏_{i=r_{j−1}+1}^{r_{j}} x̄_{i−1}} · x̄_{k} = {∏_{j=1}^{l} ∏_{i=r_{j−1}+2}^{r_{j}} x̄_{i−1}} · {∏_{j=1}^{l} ∏_{i=r_{j−1}+1}^{r_{j−1}+1} x̄_{i−1}} · x̄_{k}

= {∏_{j=1}^{l} ∏_{i=r_{j−1}+2}^{r_{j}} x̄_{i−1}} · {∏_{j=1}^{l} x̄_{r_{j}} } ,

we have that

Jamie(x_{1}, …, x_{k}) = ∏_{j=1}^{l} x̄_{r_{j}} − {∏_{i=1}^{k} x̄_{i}} {∏_{j=1}^{l} ∏_{i=r_{j−1}+2}^{r_{j}} x_{i}}

= ∏_{j=1}^{l} x̄_{r_{j}} − {∏_{j=1}^{l} ∏_{i=r_{j−1}+2}^{r_{j}}(x̄_{i−1}x_{i})} · ∏_{j=1}^{l} x̄_{r_{j}} = {∏_{j=1}^{l} x̄_{r_{j}} } · [1 − ∏_{j=1}^{l} ∏_{i=r_{j−1}+2}^{r_{j}}(x̄_{i−1}x_{i})] .

(Marvin)

We now need the following (sub)^{6} lemma:

Subsubsubsubsubsublemma 1.2.1.2.1.1.1: Let U_{j}, j = 1, …, l, be quantities in an associative algebra, then:

1 − ∏_{j=1}^{l} U_{j} = ∑_{j=1}^{l} {∏_{h=1}^{j−1} U_{h}} (1 − U_{j}) .

Proof: The series on the right telescopes to the expression on the left. Alternatively, use increasing induction on l, starting with the tautologous ground case l = 0.

Using (sub)^{6}lemma 1.2.1.2.1.1.1 with

U_{j} = ∏_{i=r_{j−1}+2}^{r_{j}}(x̄_{i−1}x_{i}) ,

we get that (Marvin) implies:

Jamie(x_{1}, …, x_{k}) = { ∏_{m=1}^{l} x̄_{r_{m}}} · ∑_{j=1}^{l} {∏_{h=1}^{j−1} ∏_{i=r_{h−1}+2}^{r_{h}}(x̄_{i−1}x_{i})} · ( 1 − ∏_{i=r_{j−1}+2}^{r_{j}}(x̄_{i−1}x_{i}) ) .

(Marvin′)

We can split (Marvin′) yet further apart, with the aid of the following (sub)^{6}lemma:

Subsubsubsubsubsublemma 1.2.1.2.1.1.2: Let U_{j}, (j = K, …, L), be quantities in an associative algebra, then:

1 − ∏_{i=K}^{L} U_{i} = ∑_{p=K}^{L}(1 − U_{p}) { ∏_{h=p+1}^{L} U_{h}} .

Proof: The sum on the right telescopes to the expression on the left. (Note that it is in the opposite direction to the way in which it happened in 1.2.1.2.1.1.1.) Alternatively, the identity is tautologous when K = L + 1, and follows by decreasing induction on K. This completes the proof of (sub)^{6} lemma 1.2.1.2.1.1.2. .

Going back to (Marvin′), we use the last (sub)^{6}lemma (1.2.1.2.1.1.2), with K = r_{j−1} + 2, L = r_{j}, and U_{i} := (x̄_{i−1}x_{i}), to rewrite:

Jamie(x_{1}, …, x_{k}) = {∏_{j=1}^{l} x̄_{r_{j}} } · ∑_{j=1}^{l} {∏_{h=1}^{j−1} ∏_{i=r_{h−1}+2}^{r_{h}}(x̄_{i−1}x_{i})} · ∑_{p=r_{j−1}+2}^{r_{j}}(1 − x̄_{p−1}x_{p}) ∏_{i=p+1}^{r_{j}}(x̄_{i−1}x_{i})

= ∑_{j=1}^{l} ∑_{p=r_{j−1}+2}^{r_{j}} { ∏_{m=1}^{l} x̄_{r_{m}}} {∏_{h=1}^{j−1} ∏_{i=r_{h−1}+2}^{r_{h}}(x̄_{i−1}x_{i})} · (1 − x̄_{p−1}x_{p}) { ∏_{i=p+1}^{r_{j}}(x̄_{i−1}x_{i})} .

(Marvin′′)

The right side of (Marvin′′) is a sum over all p in the range 1 ≤ p ≤ k except that p = r_{j} + 1, for j = 0, …, l − 1, are omitted (where r_{0} := 0.) For each such participating p, the summand is (1 − x̄_{p−1}x_{p}) times a product of x_{i}’s and x̄_{i}’s, neither of which is x_{p}, x̄_{p}, x_{p−1}, x̄_{p−1} except for a single x̄_{p}, which comes out of the first term of the product ∏_{i=p+1}^{r_{j}}(x̄_{i−1}x_{i}) in (Marvin′′), when p < r_{j} for some j, or from the j’th term of the product ∏_{j=1}^{l} x̄_{r_{j}} in case p = r_{j} for one of the j’s. Thus the polynomial Jamie(x_{1}, …, x_{k}) can indeed be expressed as claimed in (Herb). This completes the proof of (sub)^{5} lemma 1.2.1.2.1.1.

Going back to the proof of (sub)^{4}lemma 1.2.1.2.1, we insert Eq. (Herb) into Eq. (Dave), to get that the expression in (Dave) equals:

∑_{{p=2 \atop p∉\{r_{1}+1,r_{2}+1,...,r_{l−1}+1\}}}^{k} CT_{x_{1},...,x_{k}} \{\frac{P OL(x̂_{p−1}, x̂_{p}) · x̄_{p} (1 − x̄_{p−1}x_{p})Φ_{k}(x_{1}, ..., x_{k})}{\{∏_{i=1}^{k} x_{i}^{a_{i}−1}(x̄_{i})^{n+i}\} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})}\} .

(Dave′)

Let RAT (x̂_{p−1}, x̂_{p}) denote a rational function (that possesses a Laurent series) of the k−2 variables (x_{1}, …, x_{p−2}, x_{p+1}, …, x_{k}). We can express the constant-termand of the summand of (Dave′) as follows:

\frac{P OL(x̂_{p−1}, x̂_{p})}{\{∏k_{{i=1 \atop i≠p−1,p}} x_{i}^{a_{i}−1}(x̄_{i})^{n+i}\} ∏_{{1≤i<j≤k \atop i,j≠p−1,p}} (1 − x_{i}x_{j})(1 − x̄_{i}x_{j})}·

\frac{x̄_{p} (1 − x̄_{p−1}x_{p})Φ_{k}(x_{1}, ..., x_{k})}{x_{p−1}^{a_{p−1}−1}x_{p}^{a_{p}−1}x̄_{p−1}^{n+p−1}x̄_{p}^{n+p}(1 − x_{p−1}x_{p})(1 − x̄_{p−1}x_{p}) ∏_{i=1}^{p−2}(1 − x_{i}x_{p−1})(1 − x̄_{i}x_{p−1})(1 − x_{i}x_{p})(1 − x̄_{i}x_{p})}·

\frac{1}{∏_{j=p+1}^{k}(1 − x_{p−1}x_{j})(1 − x̄_{p−1}x_{j})(1 − x_{p}x_{j})(1 − x̄_{p}x_{j})}

= \frac{RAT (x̂_{p−1}, x̂_{p})Φ_{k}(x_{1}, ..., x_{k})}{x_{p−1}^{a_{p−1}−1}x_{p}^{a_{p}−1}x̄_{p−1}^{n+p−1}x̄_{p}^{n+p−1}(1 − x_{p−1}x_{p}) ∏_{i=1}^{p−2}(1 − x_{i}x_{p−1})(1 − x̄_{i}x_{p−1})(1 − x_{i}x_{p})(1 − x̄_{i}x_{p})}·

\frac{1}{∏_{j=p+1}^{k}(1 − x_{p−1}x_{j})(1 − x̄_{p−1}x_{j})(1 − x_{p}x_{j})(1 − x̄_{p}x_{j})} .

But this constant-termand is manifestly anti-symmetric w.r.t. x_{p−1} ↔ x_{p}, since Φ_{k} is, and the rest is symmetric, since a_{p−1} = a_{p} (recall that p ≠ r_{j} + 1, j = 0, …, l − 1.) It follows from crucial fact ℵ_{1} that its constant-term, CT_{x_{1},...,x_{k}} vanishes. Since every single term in (Dave′) vanishes, it follows that (Dave′), and hence (Dave) must also vanish. This completes the proof of (sub)^{4}lemma 1.2.1.2.1.

Subsubsubsublemma 1.2.1.2.2: For i = 1, …, k, we have, for (n; a_{1}, …, a_{k}) ∈ \overline{Land Of Gog_{k}},

H_{k}(n; a_{1}, …, a_{k}) = 0 on a_{i} = k − i .  (H1)_{i}

[ Type ‘S12122(k,n):’ in ROBBINS, for specific k and n.]

Proof: By the definition of H_{k},

H_{k}(n; a_{1}, …, a_{i−1}, k − i, a_{i+1}, …, a_{k}) =

CT_{x_{1},...,x_{k}} [\frac{Φ_{k}(x_{1}, …, x_{k})}{x_{1}^{a_{1}−1} ⋯ x_{i−1}^{a_{i−1}−1}x_{i}^{k−i−1} ⋯ x_{k}^{a_{k}−1}} · ∏_{i=1}^{k}(x̄_{i})^{−n−i} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})^{−1}(1 − x̄_{i}x_{j})^{−1}] .

For each term of the polynomial Φ_{k} (see (Gog_{1}) in the statement of sublemma 1.2 for its definition), there are at least i distinct x’s that appear as factors with multiplicity ≥ k−i. But the denominator of the constant termand has at least k − i + 1 x’s in the denominator with exponent ≤ k − i − 1. By the pigeonhole principle, these two sets must have a non-empty intersection. Say x_{l} appears in this intersection. Then, regarded as a Laurent series in x_{l}, our constant termand is a positive power of x_{l} times a power series in x_{l}. Thus its constant term with respect to x_{l} is zero. This completes the proof of (sub)^{4}lemma 1.2.1.2.2.

Subsubsubsublemma 1.2.1.2.3: For (n; n+1, a_{2}, …, a_{k}) ∈ \overline{Land Of Gog_{k}} , (note that a_{2} ≤ n,)

H_{k}(n; n + 1, a_{2}, …, a_{k}) = 0 .  (H2)

[ Type ‘S12123(k,n):’ in ROBBINS, for specific k and n.]

Proof: By definition,

H_{k}(n; n + 1, a_{2}, …, a_{k}) =

CT_{x_{1},...,x_{k}} [\frac{Φ_{k}(x_{1}, …, x_{k})}{x_{1}^{n}x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}} · x̄_{1}^{−n−1}x̄_{2}^{−n−2} … x̄_{k}^{−n−k} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})^{−1}(1 − x̄_{i}x_{j})^{−1}] .

(H2a)

(H2) is obvious for a_{2} = a_{3} = … = a_{k} = 0. It is reasonable to try induction on the size of the a_{i}, or more precisely, on their sum. As is often the case when trying to apply induction, we would have to consider points that we do not care about. So let’s invite all the vectors (a_{2}, …, a_{k}) for which the components are all ≤ n, to be included in the statement of subsubsubsublemma 1.2.1.2.3. Never mind that M̃_{k} doesn’t make sense unless a_{2} ≥ a_{3} ≥ … ≥ a_{k}, right now we are talking about H_{k}, for which it is meaningful to consider all such (a_{2}, …, a_{k}), and we are thus lead to prove the more general statement that (H2a) vanishes for all a_{2}, …, a_{k} ≤ n. By multiplying the numerator by

x̄_{2}^{n+2} … x̄_{k}^{n+k} ∏_{2≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j}) = 1 + O(x_{2}) + … + O(x_{k}) ,

and using the inductive hypothesis on a_{2} +…+a_{k}, it is clear that the assertion that (H2a) vanishes for all a_{2}, …, a_{k} ≤ n is equivalent to the following simpler statement:

Subsubsubsubsublemma 1.2.1.2.3.1: For all n ≥ k, and a_{2}, …, a_{k} ≤ n, the following identity holds. (Recall that for any variable t, its bar, t̄, stands for 1 − t.)

F_{k}(n; a_{2}, …, a_{k}) := CT_{x_{1},...,x_{k}} [\frac{Φ_{k}(x_{1}, …, x_{k})}{x_{1}^{n}x̄_{1}^{n+1}x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}} · ∏_{i=2}^{k}(1 − x_{1}x_{i})^{−1}(1 − x̄_{1}x_{i})^{−1}] = 0 ,

(H2b)

where Φ_{k}(x_{1}, …, x_{k}) is the polynomial defined in (Gog_{1}) (in the statement of sublemma 1.2.)

Proof: We can write F_{k}(n; a_{2}, …, a_{k}) as

F_{k}(n; a_{2}, …, a_{k}) := CT_{x_{1}} [\frac{P (x_{1})}{x_{1}^{n}x̄_{1}^{n+1}} ] ,

where, P (x_{1}) is the polynomial in x_{1} given by:

P (x_{1}) := CT_{x_{2},...,x_{k}} [\frac{Φ_{k}(x_{1}, …, x_{k})}{x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1} ∏_{i=2}^{k}(1 − x_{1}x_{i})(1 − x̄_{1}x_{i})}] .  (H2c)

Since P (x_{1}) is obviously anti-symmetric w.r.t. to x_{1} → 1 − x_{1}, it follows by Crucial Fact ℵ_{2}, that we would be done once we can prove that the degree of P (x_{1}) is ≤ 2n.

Let’s perform a partial-fraction decomposition of the constant-termand of (H2c), w.r.t. to x_{1}. Since the degree of Φ_{k}(x_{1}, …, x_{k}) in x_{1} is ≤ 4k − 3, we can set:

\frac{Φ_{k}(x_{1}, …, x_{k})}{∏_{i=2}^{k}(1 − x_{1}x_{i})(1 − x̄_{1}x_{i})} = Q_{k}(x_{1}; x_{2}, …, x_{k}) + ∑_{i=2}^{k} \frac{B_{i}}{1 − x_{1}x_{i}} + ∑_{i=2}^{k} \frac{C_{i}}{1 − x̄_{1}x_{i}} ,  (H2d)

where B_{i} and C_{i} do not depend on x_{1}, and Q_{k} is a polynomial of degree ≤ (4k−3)−(2k−2) = 2k−1, in x_{1}, with coefficients that are rational functions of (x_{2}, …, x_{k}). Inserting this into P (x_{1}) above shows that the contribution to it, due to Q_{k} has degree ≤ 2k − 1 < 2n. We now have to determine the B_{i}’s. By the anti-symmetry of Φ_{k}, we have that C_{i} = −B_{i}. B_{i} is given by the following (sub)^{6}lemma:

Subsubsubsubsubsublemma 1.2.1.2.3.1.1: B_{i} in (H2d) is given by:

B_{i} = ±\frac{(1 − 2x_{i})(1 − x_{i}^{2})(1 − x_{i}x̄_{i})Φ_{k−2}(x_{2}, x_{3}, …, x̂_{i}, …, x_{k})}{x_{i}^{k+1}}·

∏_{{j=2 \atop j≠i}}^{k}\{(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})(1 − x_{i}x̄_{j})(x_{j} + x_{i} − 1)\} .

Proof: This is a special case, R = 1, and z_{i} = x_{i}, for all 2 ≤ i ≤ k, of subsubsublemma 1.4.1.1 that is proved later, in act IV. This completes the proof of (sub)^{6} lemma 1.2.1.2.3.1.1.

Since C_{i} = −B_{i}, one can write:

P (x_{1}) = CT_{x_{2},...,x_{k}} \frac{Q_{k}(x_{1}; …, x_{k})}{x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}} +CT_{x_{2},...x_{k}} ∑_{i=2}^{k} B_{i}(\frac{1}{x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}(1 − x_{1}x_{i})}−\frac{1}{x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}(1 − x̄_{1}x_{i})}) .

(H2e)

We have already observed that the degree (in x_{1}) of the first piece is ≤ 2n. Since B_{i}/(1 − x_{1}x_{i}) possesses a Laurent series, we can use crucial fact ℵ_{4} to change the order of the constant-terming, for the i^{th} term, and get that its contribution is

CT_{x_{2},...,_{x_{i}},...,x_{k}}\{\frac{±Φ_{k−2}(x_{2}, x_{3}, …, x̂_{i}, …, x_{k})}{x_{2}^{a_{2}−1} … x_{i−1}^{a_{i−1}−1}x_{i+1}^{a_{i+1}−1} … x_{k}^{a_{k}−1}} ·

CT_{x_{i}}\{\frac{(1 − 2x_{i})(1 − x_{i}^{2})(1 − x_{i}x̄_{i}) ∏k_{{j=2 \atop j≠i}} [(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})(1 − x_{i}x̄_{j})(x_{j} + x_{i} − 1)]}{x_{i}^{a_{i}+k}}·\frac{1}{(1 − x_{i}x_{1})}\}\} .

Using the Maclaurin expansion (in x_{i})

(1 − x_{1}x_{i})^{−1} = ∑_{r=0}^{∞} x_{1}^{r}x_{i}^{r} ,

and expanding the numerator of the last constant-termand (w.r.t. x_{i}) in powers of x_{i}:

∑_{r=0}^{4k−3} L_{r}(x_{2}, …, x̂_{i}, …, x_{k})x_{i}^{r} ,

multiplying out, and then extracting the coefficient of x_{i}^{a_{i}+k}, shows that the inner constant-term (w.r.t. x_{i},) can be written as:

∑_{r=0}^{min(a_{i}+k,4k−3)} L_{r}(x_{2}, …, x̂_{i}, …, x_{k})x_{1}^{a_{i}+k−r} ,

which is a polynomial of degree ≤ k + a_{i} ≤ n + n = 2n in x_{1}, with coefficients that are polynomials in the remaining variables (x_{2}, …, x̂_{i}, …, x_{k}). Taking the outer constant-term does not change this fact, except that now we arrive at a polynomial in x_{1} with numerical coefficients. The same argument (with x̄_{1} replaced by x_{1}) holds for the term −B_{i}/(1 − x̄_{1}x_{i}).

Since each and every contribution to P (x_{1}) has degree ≤ 2n, the same must be true of P (x_{1}) itself, and hence completes the proof of subsubsubsubsublemma 1.2.1.2.3.1 .

This completes the proof of subsubsubsublemma 1.2.1.2.3 .

Subsubsubsublemma 1.2.1.2.4: For (k; k, a_{2}, …, a_{k}) ∈ \overline{Land Of Gog_{k}},

H_{k}(k; k, a_{2}, …, a_{k}) = H_{k−1}(k; a_{2}, …, a_{k}) .  (H3)

[ Type ‘S12124(k):’ in ROBBINS, for specific k.]

Proof: From the definition of H_{k},

H_{k}(k; k, a_{2}, …, a_{k}) = CT_{x_{1},...,x_{k}} \{\frac{Φ_{k}(x_{1}, …, x_{k})}{x_{1}^{k−1}x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}x̄_{1}^{k+1} … x̄_{k}^{2k}} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})^{−1}(1 − x̄_{i}x_{j})^{−1}\} .

(1.2.1.2.4a)

Recall, from the definition of \overline{Land Of Gog_{k}} (given at the beginning of the proof of 1.2.1), that k > a_{2}. Let’s look at the contributions of the various terms of Φ_{k} (defined in (Gog_{1})), to the constant term (1.2.1.2.4a). Because of the low exponents (< k) of the x_{i}’s that appear in the denominator of (1.2.1.2.4a), it is clear that only those g = (π, ε) for which all the ε_{i}’s equal −1, have any hope of contributing a non-zero term. It follows that (note that we “lose” a factor of (−1)^{k} due to fixing all the k ε_{i}’s to be −1):

H_{k}(k; k, a_{2}, …, a_{k}) = CT_{x_{1},...,x_{k}} \{\frac{Ψ_{k}(x_{1}, …, x_{k})}{x_{1}^{k−1}x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}x̄_{1}^{k+1} … x̄_{k}^{2k}} ∏_{1≤i<j≤k}(1 − x̄_{i}x_{j})^{−1}(1 − x_{i}x_{j})^{−1}\} ,

(1.2.1.2.4b)

where

Ψ_{k}(x_{1}, …, x_{k}) = ∑_{π∈S_{k}} sgn(π) · π [∏_{i=1}^{k} x_{i}^{k−i}x̄_{i}^{k} ∏_{1≤i<j≤k}(1 − x̄_{i}x_{j})(1 − x_{i}x_{j})]  .  (Gog′_{1})

Even now, there are lots of terms of Ψ_{k} that do not contribute to the constant term of (1.2.1.2.4b). All those terms corresponding to π for which π(1) ≠ 1, will have one of the x_{j}, for j > 1 raised to a power k − 1, which will introduce a factor of x_{j} and shatter any hope for a non-zero contribution to the constant term. So let’s write:

Ψ_{k}(x_{1}, …, x_{k}) = x_{1}^{k−1}x̄_{1}^{k}(1−x̄_{1}x_{2}) … (1−x̄_{1}x_{k})(1−x_{1}x_{2}) … (1−x_{1}x_{k})Ψ_{k−1}(x_{2}, …, x_{k}) + GARBAGE = x_{1}^{k−1}x̄_{1}^{k}(x̄_{2} … x̄_{k})(1) … (1)Ψ_{k−1}(x_{2}, …, x_{k}) + O(x_{1}^{k}) + GARBAGE ,

where GARBAGE denotes terms that clearly contribute 0 to the constant term, and in the second equality we have used that (1−x̄_{1}x_{2}) … (1−x̄_{1}x_{k}) = (x̄_{2} +x_{1}x_{2}) … (x̄_{k} +x_{1}x_{k}) = x̄_{2} … x̄_{k} +O(x_{1}).

Thus,

H_{k}(k; k, a_{2}, …, a_{k}) = CT_{x_{2},...,x_{k}}CT_{x_{1}}\{\frac{x_{1}^{k−1}x̄_{1}^{k}x̄_{2} … x̄_{k}Ψ_{k−1}(x_{2}, …, x_{k})}{x_{1}^{k−1}x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}x̄_{1}^{k+1} … x̄_{k}^{2k}}·

∏_{1<j≤k}(1 − x_{1}x_{j})^{−1}(1 − x̄_{1}x_{j})^{−1} ∏_{2≤i<j≤k}(1 − x_{i}x_{j})^{−1}(1 − x̄_{i}x_{j})^{−1}}

= CT_{x_{2},...,x_{k}}\{\frac{x̄_{2} … x̄_{k}Ψ_{k−1}(x_{2}, …, x_{k})}{x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}x̄_{2}^{k+2} … x̄_{k}^{2k}} · ∏_{2≤i<j≤k}(1 − x_{i}x_{j})^{−1}(1 − x̄_{i}x_{j})^{−1}·

CT_{x_{1}}{(1/x̄_{1}) ∏_{1<j≤k}(1 − x_{1}x_{j})^{−1}(1 − x̄_{1}x_{j})^{−1}}}

= CT_{x_{2},...,x_{k}}\{\frac{Ψ_{k−1}(x_{2}, …, x_{k})}{x_{2}^{a_{2}−1} … x_{k}^{a_{k}−1}x̄_{2}^{k+1} … x̄_{k}^{2k−1}} · ∏_{2≤i<j≤k}(1 − x_{i}x_{j})^{−1}(1 − x̄_{i}x_{j})^{−1} · 1 \} .

(H_{k}(k))

I claim that this equals H_{k−1}(k; a_{2}, …, a_{k}). By the definition (H_{k}) given in the statement of subsublemma 1.2.1, we have:

H_{k−1}(k; a_{2}, …, a_{k}) := CT_{x_{2},...,x_{k}} \{\frac{Φ_{k−1}(x_{2}, ..., x_{k})}{\{∏_{i=2}^{k} x_{i}^{a_{i}−1}(x̄_{i})^{(k−1)+i}\} ∏_{2≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})}\} ,

(H_{k−1}(k))

Since k > a_{2} ≥ a_{3} … ≥ a_{k}, a parallel argument can be given to show that the right side of (H_{k−1}(k)) equals the right side of (H_{k}(k)). This completes the proof of subsubsubsublemma 1.2.1.2.4.

Subsubsubsublemma 1.2.1.2.5: (H4) in the statement of subsubsublemma 1.2.1.2 holds.

This completes the proof of subsubsublemma 1.2.1.2.

Subsubsublemma 1.2.1.3: Let k ≥ 1 and for any vector of integers a = (a_{1}, …, a_{k}), define the partial difference operator P^{(a)} by:

P^{(a)}(A_{1}, …, A_{k}) := ∏_{{i|a_{i}−a_{i+1}>0}}(I − A_{i}^{−1})  ,

where we declare that a_{k+1} = 0. There is a unique sequence of discrete functions Y_{k}(n; a_{1}, …, a_{k}), defined on \overline{Land Of Gog_{k}} that satisfies the following partial recurrence

P^{(a)}(A_{1}, …, A_{k})Y_{k}(n; a_{1}, …, a_{k})
= Y_{k}(n − 1 ; a_{1} , min(a_{1} − 1, a_{2}) , …, min(a_{k−1} − 1, a_{k}))  ,  (P ΔE(Y_{k}))

valid for n > k and for (n; a_{1}, …, a_{k}) ∈ Land Of Gog_{k}, and the following initial/boundary conditions for (n; a_{1} , …, a_{k}) ∈ \overline{Land Of Gog_{k}}:

Y_{k}(n; a_{1}, …, a_{k}) = 0 on a_{i} = k − i  ,  (Y 1_{i})
Y_{k}(n; n + 1, a_{2}, …, a_{k}) = 0 ,  (Y 2)
Y_{k}(k; k, a_{2}, …, a_{k}) = Y_{k−1}(k; a_{2}, …, a_{k})  ,  (Y 3)

and, finally the “Adam” condition

Y_{1}(1 ; 1) = 1  .  (Y 4)

[ Type ‘S1213(k,n):’ in ROBBINS, for specific k and n.]

Proof: Eq. P ΔE(Y_{k}) can be rewritten such that Y_{k}(n; a_{1}, …, a_{k}) remains on the left side, and all the rest goes to the right side. The right side involves either points (n; b_{1}, …, b_{k}) that belong to \overline{Land Of Gog}, with b_{1} + … + b_{k} < a_{1} + a_{2} + … + a_{k}, so they were already computed before, or points that belong to the boundary, for which the boundary conditions are used. Note that the reason that it was possible to impose the extra restriction that n = k = a_{1} ⇒ a_{2} < k, in the definition of \overline{Land Of Gog_{k}} , was that when we use the local recurrence (P ΔE(M̃_{k})) to compute M̃_{k}, starting with n = k + 1, the right hand side of (P ΔE(M̃_{k})) only requires knowledge of M̃_{k}, when n = k = a_{1}, for those a’s for which a_{2} < k, since even if a_{2} = k on the left side, the evaluation at the right is at M̃_{k}(k; k, min(k − 1, k), …) = M̃_{k}(k; k, k − 1, …,). This completes the proof of subsubsublemma 1.2.1.3. .

Combining subsubsublemmas 1.2.1.1 − 3 yields subsublemma 1.2.1. .

Going back to the proof of sublemma 1.2, note that m_{k}(n), the total number of n×k-Gog trapezoids, equals M̃_{k}(n + 1; n + 1 , n + 1 , …, n + 1), as follows directly from the definition (M̃_{k}) of M̃_{k}. By subsublemma 1.2.1, this equals H_{k}(n + 1; n + 1 , n + 1 , …, n + 1) which coincides with the right side of (GogT otal). This completes the proof of sublemma 1.2. .

INTERACT

We have now established constant term expressions both for b_{k}(n), the number of n × k Magog trapezoids, given by (MagogT otal) in sublemma 1.1 , and for m_{k}(n), the number of n × k Gog trapezoids, given by (GogT otal) in sublemma 1.2. It would have been nice if the constant-termands were the same. Unfortunately, they are not. In order to prove that the constant terms are, we have to resort to the omnipotent Stanton-Stembridge trick once again, only now w.r.t. to the action of the group of signed permutations, W (B_{k}). Justifying its use, however, will require many more pages. It would be necessary first to convert the constant-term expressions to “residue” expressions.

Sublemma 1.1’: The total number of n × k− Magog trapezoids, b_{k}(n), is given by the following iterated-residue expression:

b_{k}(n) = Res_{x_{1},...,x_{k}} \{\frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{n+k−i}(x̄_{i})^{n+k+1} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})}\} ,  (MagogT otal′)

where,

Δ_{k}(x_{1}, ..., x_{k}) := ∏_{i=1}^{k}(1 − 2x_{i}) ∏_{1≤i<j≤k}(x_{j} − x_{i})(x_{j} + x_{i} − 1)  .  (Delta)

Sublemma 1.2’: The total number of n × k− Gog trapezoids, m_{k}(n), is given by the following iterated-residue expression:

m_{k}(n) = Res_{x_{1},...,x_{k}} [\frac{Φ_{k}(x_{1}, …, x_{k})}{\{∏_{i=1}^{k} x_{i}^{n+1}(x̄_{i})^{n+i+1}\} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})}] ,

(GogT otal′)

where the polynomial Φ_{k}(x_{1}, …, x_{k}) is defined by:

Φ_{k}(x_{1}, …, x_{k}) = (−1)^{k} ∑_{g∈W (B_{k})} sgn(g) · g [∏_{i=1}^{k} x̄_{i}^{k−i}x_{i}^{k} ∏_{1≤i<j≤k}(1 − x_{i}x̄_{j})(1 − x̄_{i}x̄_{j})]  . (Gog_{1})

Proof of Sublemmas 1.1’ and 1.2’: Use Crucial fact ℵ_{6}.

Act III. (MagogTotal’) IS UNFAZED BY THE SIGNED PERMUTATIONS’ ACTION

Talk no more so exceeding proudly; let not arrogancy come out of your mouth: for

the Lord is a God of knowledge, and by him actions are weighed. —(Samuel II,3)

Sublemma 1.3 : Let n ≥ k ≥ 1 and let f_{n,k}(x) = f_{n,k}(x_{1}, …, x_{k}) be the residuand of (MagogT otal′):

f_{n,k}(x_{1}, …, x_{k}) := \frac{Δ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k}(x̄_{i})^{n+k+1}x_{i}^{n+k−i} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})} ,

where Δ_{k}(x_{1}, …, x_{k}) is the polynomial defined in (Delta) (in the statement of sublemma 1.2). Let g = (π, ε) be any signed permutation in W (B_{k}); then

Res_{x_{1},...,x_{k}}[gf_{n,k}(x)] = Res_{x_{1},...,x_{k}}[f_{n,k}(x)] (= b_{k}(n)) .

[ Type ‘S13(k,n):’ in ROBBINS, for specific k and n.]

Proof: Recall that a signed permutation g = (π, ε) acts on any rational function f(x) of x = (x_{1}, …, x_{k}), by gf(x) = f(ε(π(x))). By renaming the variables, and replacing π^{−1} by π, one finds that the statement of sublemma 1.3 is equivalent to:

Sublemma 1.3’ : Let f_{n,k}(x) = f_{n,k}(x_{1}, …, x_{k}) be the residuand of (MagogT otal′), reproduced just above. Let π be any permutation of {1, …, k}, and let ε = (ε_{1}, …, ε_{k}) be any sign-assignment, then

Res_{x_{π(1)},...,x_{π(k)}}[f_{n,k}(ε_{1}(x_{1}), …, ε_{k}(x_{k}))] = Res_{x_{1},...,x_{k}}[f_{n,k}(x_{1}, …, x_{k})] .  (1.3′)

The proof will be by induction on the number of ε_{i}’s that are equal to −1. If there are no −1’s in ε, then 1.3′ follows immediately from crucial fact ℵ′_{4}, since then the residuand f_{n,k}(x_{1}, …, x_{k}) has a Laurent series. Otherwise, let u be the smallest integer i, (1 ≤ i ≤ k) such that ε_{π(i)} = −1. The inductive step is provided by the following subsublemma, that asserts that it is permissible to change ε_{π(u)} from −1 to +1 inside the residuand of the iterated residue on the left side of (1.3′), without affecting its value.

Subsublemma 1.3.1: Let f_{n,k}(x_{1}, …, x_{k}) (where, as always, n ≥ k ≥ 1,) be the residuand of (MagogT otal′), let π be any permutation of {1, …, k}, and let ε = (ε_{1}, …, ε_{k}) be any signassignment with at least one ε_{i} equal to −1. Let u be the smallest i (1 ≤ i ≤ k) such that ε_{π(i)} = −1. (i.e., we have ε_{π(1)} = … = ε_{π(u−1)} = +1, and ε_{π(u)} = −1.) Then:

Res_{x_{π(1)},...,x_{π(k)}}[f_{n,k}(ε_{1}(x_{1}), …, x_{π(u)}, …, ε_{k}(x_{k}))] = Res_{x_{π(1)},...,x_{π(k)}}[f_{n,k}(ε_{1}(x_{1}), …, x̄_{π(u)}, …, ε_{k}(x_{k}))] .

[ Type ‘S131(k,n):’ in ROBBINS, for specific k and n.]

Proof: Let’s abbreviate R := π(u), and z_{i} := ε_{i}(x_{i}) ( 1 ≤ i ≤ k, i ≠ R.) Recall that this means that z_{i} = x_{i} if ε_{i} = +1, and z_{i} = x̄_{i} = 1 − x_{i} if ε_{i} = −1. By the W (B_{k})-antisymmetry of Δ_{k}(x), we have

f_{n,k}(ε_{1}(x_{1}), …, x_{R}, …, ε_{k}(x_{k})) = \frac{1}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} ∏_{{j=1 \atop j≠R}}^{k} \frac{1}{z_{j}^{n+k−j}z̄_{j}^{n+k+1}} ∏_{{1≤r<s≤k \atop r,s≠R}} \frac{1}{(1 − z_{r}z_{s})}·\{\frac{±Δ_{k}(x_{1}, …, x_{k})}{∏k_{{i=1 \atop i≠R}} (1 − z_{i}x_{R})}\} .

(Jane)

The next step is to perform a partial-fraction decomposition, with respect to the variable x_{R}, of the fraction inside (Jane)’s braces.

Subsubsublemma 1.3.1.1:

\frac{±Δ_{k}(x_{1}, …, x_{k})}{∏k_{{i=1 \atop i≠R}} (1 − z_{i}x_{R})} = P_{R} + ∑_{{i=1 \atop i≠R}}^{k} \frac{B_{i}}{1 − z_{i}x_{R}} ,  (T amar)

where P_{R} is a polynomial of degree k in x_{R}, with coefficients that are rational functions of the other variables (x_{1}, …, x_{R−1}, x_{R+1}, …, x_{k}), and

B_{i} = \frac{±(z_{i} − 2)(1 − 2z_{i})(1 − z_{i}^{2})(1 − z_{i}z̄_{i})Δ_{k−2}(x_{1}, …, x̂_{i}, …, x̂_{R}, …, x_{k})}{z_{i}^{k+1}}·

\{ ∏_{{j=1 \atop j≠i,R}}^{k}(1 − z_{i}z_{j})(1 − z_{i}z̄_{j})(z_{j} + z_{i} − 1)\} .  (Bi)

[ Type ‘S1311(k,R):’ in ROBBINS, for specific k and R.]

Proof: By Freshman Calculus (or rather the algebraic part of it), we know that the left side of (T amar), when viewed as a rational function of x_{R}, can be written as on its right side, for some polynomial P_{R}, and constants (in the present context, i.e. quantities not involving x_{R}) B_{i}. The degree of Δ_{k}, in x_{R} (or for that matter, in any variable), from its definition in (Delta), is 2k − 1, and the degree of the denominator of the left side of (T amar) is (k − 1). Hence the degree of P_{R}, in x_{R} is (2k − 1) − (k − 1) = k. The coefficients of P_{R}, as a polynomial of x_{R}, are certain rational functions of the remaining variables whose exact form does not interest us. The exact form of the B_{i}’s should interest us, since it is used heavily in the proof. So let’s brace ourselves and embark on partial-fractioning.

Multiplying both sides of (T amar) by the denominator of its left side yields the equation:

±Δ_{k}(x_{1}, …, x_{k}) = \{ ∏_{{j=1 \atop j≠R}}^{k}(1 − z_{j}x_{R})\} P_{R} + ∑_{{i=1 \atop i≠R}}^{k} \{ ∏_{{j=1 \atop j≠R,i}}^{k}(1 − z_{j}x_{R})\} B_{i} .  (T amar′)

To decipher B_{i} (1 ≤ i ≤ k, i ≠ R), we plug in x_{R} = 1/z_{i} on both sides of (T amar′) to get:

B_{i} = \frac{±Δ_{k}(x_{1}, …, x_{k})|_{x_{R}=1/z_{i}}}{\{∏k_{{j=1 \atop j≠R,i}} (1 − z_{j}/z_{i})\}} = \frac{±z_{i}^{k−2}Δ_{k}(x_{1}, …, x_{k})|_{x_{R}=1/z_{i}}}{\{∏k_{{j=1 \atop j≠R,i}} (z_{i} − z_{j})\}} .  (P P 1)

the electronic journal of combinatorics 3 (2) (1996), #R13 39

Subsubsubsublemma 1.3.1.1.1:

Δ_{k}(x_{1}, x_{2}, …, x_{k})|_{x_{R}=1/z_{i}} = ±\frac{(z_{i} − 2)(1 − 2z_{i})(1 − z_{i}^{2})(1 − z_{i}z̄_{i}) · Δ_{k−2}(x_{1}, x_{2}, x_{3}, …, x̂_{i}, …, x̂_{R}, …, x_{k})}{z_{i}^{2k−1}}·

∏_{{j=1 \atop j≠i,R}}^{k}\{(1 − z_{i}z_{j})(1 − z_{i}z̄_{j})(z_{j} − z_{i})(z_{j} + z_{i} − 1)\} .  (1.3.1.1.1)

[ Type ‘S13111(k,R,i):’ in ROBBINS, for specific k,R and i.]

Proof: This follows routinely from the definition (Delta) of Δ_{k}. . Plugging (1.3.1.1.1) into (P P 1), and cancelling out ∏k_{{j=1 \atop j≠i,R}} (z_{j} − z_{i}) from top and bottom, finishes up the proof of (sub)^{3}lemma 1.3.1.1. For the rest of the proof of (sub)^{2}lemma 1.3.1, we need some notation. Let P OL stand for “some polynomial of (x_{1}, …, x_{k})”, and let RAT stand for “some rational function of (x_{1}, …, x_{k})”. P OL(x̂_{R}) stands for such a polynomial that does not involve x_{R}. P OLRAT (x_{R}; x_{1}, …, x̂_{R}, …, x_{k}), or P OLRAT (x_{R} ; …) for short, stands for a polynomial in x_{R} with coefficients that are rational functions of the rest of the variables. P OLRAT (x_{i}; x̂_{R}) stands for a polynomial in x_{i} with coefficients that are rational function of the remaining variables and that does not involve x_{R}. Inserting (T amar)(in the statement of 1.3.1.1) into (Jane) is going to yield the following (sub)^{3}lemma: Subsubsublemma 1.3.1.2:

f_{n,k}(epsilon_{1}(x_{1}), …, x_{R}, …, ε_{k}(x_{k})) = \frac{P̃_{R}}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} + ∑_{{i=1 \atop i≠R}}^{k} \frac{B̃_{i}}{1 − z_{i}x_{R}} ,  (Celia)

where P̃_{R} is a polynomial of degree k in x_{R}, with coefficients that are rational functions of the rest of the variables, and B̃_{i} can be written as follows.

B̃_{i} = \frac{P OL(x̂_{R})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}z_{i}^{n+2k−i+1}z̄_{i}^{n+k+1}} · ∏_{{j=1 \atop j≠i,R}}^{k} \frac{1}{z_{j}^{n+k−j}z̄_{j}^{n+k+1}} · ∏_{{1≤r<s≤k \atop r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})}

= \frac{P OLRAT (x_{i}; x̂_{R})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}z_{i}^{n+2k−i+1}z̄_{i}^{n+k+1}} .  (B̃i)

Proof: Insert (T amar) into (Jane), bringing the quantity in front of the sum inside, and for each B_{i} split the double product:

∏_{{1≤r<s≤k \atop r,s≠R}} \frac{1}{(1 − z_{r}z_{s})} = ∏_{{1≤r<s≤k \atop r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})} · ∏_{{j=1 \atop j≠i,R}}^{k} \frac{1}{(1 − z_{j}z_{i})} ,  (Split)

[ Type ‘S1312(k,n,eps,R):’ in ROBBINS, for specific k,n, eps and R.]

and cancel out ∏k_{{j=1 \atop j≠i,R}} (1 − z_{j}z_{i}) on the top and bottom. This completes the proof of (sub)^{3}lemma 1.3.1.2.

We will say that a rational function h = h(x_{1}, …, x_{k}) has property (Hadas) if:

Res_{x_{π(1)},...,x_{π(k)}}[h] = Res_{x_{π(1)},...,x_{π(k)}}[h(x_{R} → x̄_{R})] ,  (Hadas)

where h(x_{R} → x̄_{R}) is the rational function obtained from h by replacing the variable x_{R} by x̄_{R} (= 1 − x_{R}.)

The statement of subsublemma 1.3.1 is equivalent to saying that

f_{n,k}(ε_{1}(x_{1}), …, x_{R}, …, ε_{k}(x_{k}))

has property (Hadas). Property (Hadas) is obviously additive (since the action of taking residue, and performing x_{R} → x̄_{R} are), so in order to complete the proof of 1.3.1 (and hence of 1.3), it would suffice to show that each term in (Celia) has property (Hadas). This will be accomplished by the following two subsubsublemmas (1.3.1.3 − 4.)

Subsubsublemma 1.3.1.3: Let P̃_{R} be as in the statement of 1.3.1.2, i.e. a polynomial of degree k in x_{R} with coefficients that are rational functions of the remaining variables. Then \frac{_{P_{R}}}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} has property (Hadas):

Res_{x_{π(1)},...,x_{π(k)}} [\frac{P̃_{R}}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} ] = Res_{x_{π(1)},...,x_{π(k)}} [\frac{P̃_{R}}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} (x_{R} → x̄_{R})] . (Hadas_{1})

[ Type ‘S1313(k,n):’ in ROBBINS, for specific k and n.]

Proof: Recall that R = π(u). Since P̃_{R} is a P OLRAT (x_{R}; x_{π(1)}, …, x̂_{R}, …, x_{k}), we have that

Res_{x_{π(u+1)},...,x_{π(k)}} [\frac{P̃_{R}}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} ] = Res_{x_{π(u+1)},...,x_{π(k)}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x̂_{R}, x_{π(u+1)}, …, x_{π(k)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}}]

= \frac{P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} = \frac{x_{R}^{R+1} · P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+k+1}x̄_{R}^{n+k+1}} .

Since the degree of x_{R}^{R+1}P OLRAT (x_{R} ; …), in x_{R}, is ≤ (R + 1) + k ≤ 2(n + k), it follows from crucial fact ℵ′_{5} that

Res_{x_{R}} [\frac{P OLRAT (x_{R} ; …)}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}}] = Res_{x_{R}} [\frac{P OLRAT (x_{R} ; …)}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}}(x_{R} → x̄_{R})] .

Applying Res_{x_{π(1)},...,x_{π(u−1)}} to both sides of the above equation establishes that \frac{_{P_{R}}}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} indeed has property (Hadas), so that (Hadas_{1}) holds. This completes the proof of subsubsublemma 1.3.1.3.

the electronic journal of combinatorics 3 (2) (1996), #R13 41

Subsubsublemma 1.3.1.4: Let B̃_{i} be as in the statement of 1.3.1.2, i.e. given by (B̃i). Let π be a permutation, R an integer in [1, k]\{i}, and u := π^{−1}(R). Then:

Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z_{i}x_{R}} ] = Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z_{i}x_{R}} (x_{R} → x̄_{R})] .  (Hadas_{2})

[ Type ‘S1314(k,n):’ in ROBBINS, for specific k and n.]

Proof: Case I: i ∈ {π(u + 1), …, π(k)} . Let v := π^{−1}(i), so that i = π(v), and v > u. We have that:

\frac{B̃_{i}}{1 − z_{i}x_{R}} = \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}, x_{π(v+1)}, …, x_{π(k)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}z_{i}^{n+2k−i+1}z̄_{i}^{n+k+1}(1 − z_{i}x_{R})} .

Applying Res_{x_{π(v+1)},...,x_{π(k)}} to it, gets rid of the dependence on (x_{π(v+1)}, …, x_{π(k)}):

Res_{x_{π(v+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z_{i}x_{R}} ] = \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}z_{i}^{n+2k−i+1}z̄_{i}^{n+k+1}(1 − z_{i}x_{R})} .

Applying Res_{x_{i}} to the above gives:

Res_{x_{i},x_{π(v+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z_{i}x_{R}} ] = Res_{x_{i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}z_{i}^{n+2k−i+1}z̄_{i}^{n+k+1}(1 − z_{i}x_{R})}]

= \frac{1}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} · Res_{x_{i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{z_{i}^{n+2k−i+1}z̄_{i}^{n+k+1}(1 − z_{i}x_{R})}] .  (Doron)

We now distinguish two subcases: Subcase Ia: ε_{i} = +1, that is: z_{i} = x_{i}. In this subcase, the right side of (Doron) equals:

\frac{1}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} · Coeff_{x_{i}^{n+2k−i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x̄_{i}^{n+k+1}(1 − x_{i}x_{R})}] .  (Gil)

Expanding everything involving x_{i} as a power series in x_{i}:

P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}) = ∑_{t=0}^{degree} RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})x_{i}^{t} ,

\frac{1}{x̄_{i}^{n+k+1}} = ∑_{t=0}^{∞} NUMBER_{t} · x_{i}^{t} ,

and, most importantly:

(1 − x_{i}x_{R})^{−1} = ∑_{t=0}^{∞} x_{R}^{t}x_{i}^{t} .

Multiplying out, and collecting the coefficient of x_{i}^{n+2k−i}, gives that Coeff_{x_{i}^{n+2k−i}} in (Gil) is a certain polynomial in x_{R}, of degree ≤ n + 2k − i, with coefficients that are rational functions of (x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}). In other words it is a P OLRAT (x_{R}; x_{π(1)}, …, x_{π(v−1)}) with deg_{x_{R}} ≤ n + 2k − i. Hence,

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(v−1)}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}}] ,

(Gil′)

where the P OLRAT in (Gil′) has degree ≤ n + 2k − i in x_{R}. Applying Res_{x_{π(u+1)},...,x_{π(v−1)}} to the residuand of (Gil′) gets rid of the dependence on (x_{π(u+1)}, …, x_{π(v−1)}), so we have:

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}}] ,  (Gil′′)

where P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)}) has degree ≤ n + 2k − i in x_{R}. But, the right of (Gil′′) can be rewritten as:

Res_{x_{R}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}}] = Res_{x_{R}} [\frac{x_{R}^{R+1} · P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+k+1}x̄_{R}^{n+k+1}}] .

(Gil′′′)

By crucial fact ℵ′_{5}, since (R + 1) + (n + 2k − i) ≤ 2(n + k) (recall that always n ≥ k ≥ 1, R ≤ k, and i ≥ 1), we can perform x_{R} → x̄_{R} in the residuand of (Gil′′′), so

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x_{i}x_{R}} (x_{R} → x̄_{R})] .

Applying Res_{x_{π(1)},...,x_{π(u−1)}} to both sides of the above equation finishes up subcase Ia of the proof of (sub)^{3}lemma 1.3.1.4.

Subcase Ib: ε_{i} = −1, that is: z_{i} = x̄_{i}.

In this subcase, the right side of (Doron) equals:

\frac{1}{x_{R}^{n+k−R}x̄_{R}^{n+k+1}} · Coeff_{x_{i}^{n+k}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x̄_{i}^{n+2k−i+1}(1 − x̄_{i}x_{R})}] .  (Gil)

Expanding everything involving x_{i} as a power series in x_{i}:

P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}) = ∑_{t=0}^{degree} RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})x_{i}^{t} ,

\frac{1}{x̄_{i}^{n+2k−i+1}} = ∑_{t=0}^{∞} NUMBER_{t} · x_{i}^{t} ,

and, most importantly:

(1 − x̄_{i}x_{R})^{−1} = (1 − x_{R} + x_{i}x_{R})^{−1} = (x̄_{R} + x_{i}x_{R})^{−1} = ∑_{t=0}^{∞}(−1)^{t} \frac{x_{R}^{t}}{x̄_{R}^{t+1}} x_{i}^{t} ,

multiplying out, and collecting the coefficient of x_{i}^{n+k}, gives that Coeff_{x_{i}^{n+k}} in (Gil) is a certain sum of terms of the form

RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})\frac{x_{R}^{t}}{x̄_{R}^{t+1}} , (t ≥ 0) .

Hence,

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ]

is a sum of terms of the forms

Res_{x_{R},x_{π(u+1)},...,x_{π(v−1)}} [\frac{x_{R}^{t} · RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+t+2}}] , (t ≥ 0) .  (Gil′)

Applying Res_{x_{π(u+1)},...,x_{π(v−1)}} to the residuand of (Gil′) gets rid of the dependence on (x_{π(u+1)}, …, x_{π(v−1)}), so we have that

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ]

is a sum of terms of the form

Res_{x_{R}} [\frac{x_{R}^{t}RAT_{t}(x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+k−R}x̄_{R}^{n+k+t+2}}] , (t ≥ 0) .  (Gil′′)

But, each such term can be written as

RAT_{t}(x_{π(1)}, …, x_{π(u−1)})Res_{x_{R}} [\frac{x_{R}^{R+2t+2}}{x_{R}^{n+k+t+2}x̄_{R}^{n+k+t+2}} ] , (t ≥ 0) .  (Gil′′′)

By crucial fact ℵ′_{5}, since R + 2t + 2 ≤ 2(n + k + t + 1), we can perform x_{R} → x̄_{R} in the residuand of (Gil′′′), so

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} (x_{R} → x̄_{R})] .

Applying Res_{x_{π(1)},...,x_{π(u−1)}} to both sides of the above equation finishes up subcase Ib of the proof of subsubsublemma 1.3.1.4.

Case II: i ∈ {π(1), …, π(u − 1)} .

The proof is identical to Case II of (sub)^{4}lemma 1.4.1.4 proved in act IV (except that the form of B̃_{i} is slightly more complicated there, but the argument that reduces it to Case Ia goes verbatim). This completes the proof of (sub)^{3}lemma 1.3.1.4. .

Going back to the proof of (sub)^{2}lemma 1.3.1, we know by the two (sub)^{3}lemmas (1.3.1.3 − 4) that each part of (Celia), in the statement of (sub)^{3}lemma 1.3.1.2, has property (Hadas), and by the additivity of this property, so does the whole f_{n,k}(ε_{1}(x_{1}), …, x_{R}, …, ε_{k}(x_{k})). But this is precisely what (sub)^{2}lemma 1.3.1 is saying. This completes the proof of (sub)^{2}lemma 1.3.1.

As we noted at the very beginning of the proof of sublemma 1.3, subsublemma 1.3.1, read from right to left, can be used repeatedly to ‘unbar’ x_{i}’s, until we get that

Res_{x_{π(1)},...,x_{π(k)}}[f_{n,k}(ε_{1}(x_{1}), …, ε_{k}(x_{k}))] = Res_{x_{π(1)},...,x_{π(k)}}[f_{n,k}(x_{1}, …, x_{k})] .  (Ktsat)

Since f_{n,k}(x_{1}, …, x_{k}) has a genuine Laurent expansion, crucial fact ℵ′_{4} assures us that we can unscramble the order of residue-taking on the right side of (Ktsat):

Res_{x_{π(1)},...,x_{π(k)}}[f_{n,k}(x_{1}, …, x_{k})] = Res_{x_{1},...,x_{k}}[f_{n,k}(x_{1}, …, x_{k})] .  (Nimas)

Combining (Ktsat) with (Nimas) yields (1.3′), which we noted was equivalent to the statement of sublemma 1.3. This completes the proof of sublemma 1.3.

Act IV. (GogTotal’) IS UNFAZED BY THE SIGNED PERMUTATIONS’ ACTION

… signed …– (Daniel VI, 10)

Sublemma 1.4 : Let F_{n,k}(x) = F_{n,k}(x_{1}, …, x_{k}) be the residuand of (GogT otal′) , that is,

F_{n,k}(x_{1}, …, x_{k}) := \frac{Φ_{k}(x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{n+1}x̄_{i}^{n+i+1} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})} ,

where Φ_{k}(x_{1}, …, x_{k}) is the polynomial defined in (Gog_{1}). Let g be any signed permutation in W (B_{k}), then

Res_{x_{1},...,x_{k}}[gF_{n,k}(x)] = Res_{x_{1},...,x_{k}}[F_{n,k}(x)] (= m_{k}(n)) .

[ Type ‘S14(k,n):’ in ROBBINS, for specific k and n.]

Proof: As in the proof of 1.3, by renaming the variables, the statement of sublemma 1.4 is equivalent to

Sublemma 1.4’ : Let F_{n,k}(x) = F_{n,k}(x_{1}, …, x_{k}) be the residuand of (GogT otal′), reproduced just above. Let π be any permutation of {1, …, k}, and let ε = (ε_{1}, …, ε_{k}) be any sign-assignment. Then

Res_{x_{π(1)},...,x_{π(k)}}[F_{n,k}(ε_{1}(x_{1}), …, ε_{k}(x_{k}))] = Res_{x_{1},...,x_{k}}[F_{n,k}(x_{1}, …, x_{k})] .  (1.4′)

The proof will be by induction on the number of ε_{i}’s that are equal to −1. If there are no −1’s in ε, then 1.4′ follows immediately from crucial fact ℵ_{4}, since then the residuand F_{n,k}(x_{1}, …, x_{k}) has a Laurent series. Otherwise, let u be the smallest integer i (1 ≤ i ≤ k) such that ε_{π(i)} = −1. The inductive step is provided by the following subsublemma, that asserts that it is permissible to change ε_{π(u)} from −1 to +1 inside the residuand of the iterated residue on the left side of (1.4′) without affecting its value.

Subsublemma 1.4.1: Let F_{n,k}(x_{1}, …, x_{k}) be the residuand of (GogT otal′), let π be any permutation of {1, …, k}, and let ε = (ε_{1}, …, ε_{k}) be any sign-assignment with at least one ε_{i} equal to −1. Let u be the smallest i (1 ≤ i ≤ k) such that ε_{π(i)} = −1. (i.e., we have ε_{π(1)} = … = ε_{π(u−1)} = +1, and ε_{π(u)} = −1). Then:

Res_{x_{π(1)},...,x_{π(k)}}[F_{n,k}(ε_{1}(x_{1}), …, x_{π(u)}, …, ε_{k}(x_{k}))] = Res_{x_{π(1)},...,x_{π(k)}}[F_{n,k}(ε_{1}(x_{1}), …, x̄_{π(u)}, …, ε_{k}(x_{k}))] .

[ Type ‘S141(k,n):’ in ROBBINS, for specific k and n.]

Proof: Let’s abbreviate R := π(u), and z_{i} := ε_{i}(x_{i}) ( 1 ≤ i ≤ k, i ≠ R). Recall that this means that z_{i} = x_{i} if ε_{i} = +1, and z_{i} = x̄_{i} = 1−x_{i} if ε_{i} = −1. Also put z_{R} = x_{R}. By the W (B_{k})-antisymmetry of Φ_{k}(x), we have

F_{n,k}(ε_{1}(x_{1}), …, x_{R}, …, ε_{k}(x_{k})) = \frac{±Φ_{k}(x_{1}, …, x_{k})}{x_{R}^{n+1}x̄_{R}^{n+R+1} ∏k_{{j=1 \atop j≠R}} z_{j}^{n+1}z̄_{j}^{n+j+1} ∏_{1≤i<j≤k}(1 − z_{i}z_{j})(1 − z̄_{i}z_{j})}

= \frac{1}{x_{R}^{n+1}x̄_{R}^{n+R+1}} ∏_{{j=1 \atop j≠R}}^{k} \frac{1}{z_{j}^{n+1}z̄_{j}^{n+j+1}} ∏_{{1≤r<s≤k \atop r,s≠R}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})}·

\{\frac{±Φ_{k}(x_{1}, …, x_{k})}{∏k_{{i=1 \atop i≠R}} (1 − z_{i}x_{R}) ∏_{i=1}^{R−1}(1 − z̄_{i}x_{R}) ∏_{i=R+1}^{k}(1 − z_{i}x̄_{R})}\} .  (Jane)

The next step is to perform a partial-fraction decomposition, with respect to the variable x_{R}, of the fraction inside (Jane)’s braces.

Subsubsublemma 1.4.1.1:

\frac{±Φ_{k}(x_{1}, …, x_{k})}{∏k_{{i=1 \atop i≠R}} (1 − z_{i}x_{R}) ∏_{i=1}^{R−1}(1 − z̄_{i}x_{R}) ∏_{i=R+1}^{k}(1 − z_{i}x̄_{R})}

= P_{R} + ∑_{{i=1 \atop i≠R}}^{k} \frac{A_{i}}{1 − z_{i}x_{R}} + ∑_{i=1}^{R−1} \frac{B_{i}}{1 − z̄_{i}x_{R}} + ∑_{i=R+1}^{k} \frac{B_{i}}{1 − z_{i}x̄_{R}} ,  (T amar)

where P_{R} is a polynomial of degree ≤ 2k − 1 in x_{R}, with coefficients that are rational functions of the other variables (x_{1}, …, x_{R−1}, x_{R+1}, …, x_{k}), and the A_{i}’s and B_{i}’s are as follows.

When 1 ≤ i < R,

A_{i} = \frac{±(z_{i} − 2)(1 − z_{i}^{2})(1 − z_{i}z̄_{i})Φ_{k−2}(x_{1}, …, x̂_{i}, …, x̂_{R}, …, x_{k})}{z_{i}^{k}}·

\{ ∏_{{j=1 \atop j≠i,R}}^{k}(1 − z_{i}z_{j})(1 − z̄_{i}z_{j})(1 − z_{i}z̄_{j})\} ∏_{j=R+1}^{k}(z_{j} + z_{i} − 1) ∏_{{j=1 \atop j≠i}}^{R−1}(1 − z̄_{i}z̄_{j}) .  (Ai1)

When R < i ≤ k, we have:

A_{i} = \frac{±(1 − 2z_{i})(1 − z_{i}^{2})(1 − z_{i}z̄_{i})Φ_{k−2}(x_{1}, …, x̂_{R}, …, x̂_{i}, …, x_{k})}{z_{i}^{k+1}}·

\{ ∏_{{j=1 \atop j≠i,R}}^{k}(1 − z_{i}z_{j})(1 − z̄_{i}z_{j})(1 − z_{i}z̄_{j})\} ∏_{{j=R+1 \atop j≠i}}^{k}(z_{j} + z_{i} − 1) ∏_{j=1}^{R−1}(1 − z̄_{i}z̄_{j}) .  (Ai2)

As for the B_{i}, when 1 ≤ i < R, we have

B_{i} = \frac{±(z̄_{i} − 2)(1 − z̄_{i}^{2})(1 − z_{i}z̄_{i})Φ_{k−2}(x_{1}, …, x̂_{i}, …, x̂_{R}, …, x_{k})}{z̄_{i}^{k}}·

\{ ∏_{{j=1 \atop j≠i,R}}^{k}(1 − z_{i}z_{j})(1 − z̄_{i}z_{j})(1 − z̄_{i}z̄_{j})\} ∏_{j=R+1}^{k}(z_{j} − z_{i}) ∏_{{j=1 \atop j≠i}}^{R−1}(1 − z_{i}z̄_{j}) .  (Bi1)

Finally, when R < i ≤ k, we have:

B_{i} = \frac{±(1 − 2z_{i})(1 − z_{i}^{2})(1 − z_{i}z̄_{i})Φ_{k−2}(x_{1}, …, x̂_{R}, …, x̂_{i}, …, x_{k})}{z_{i}^{k+1}}·

\{ ∏_{{j=1 \atop j≠i,R}}^{k}(1 − z_{i}z_{j})(1 − z_{i}z̄_{j})(z_{i} + z_{j} − 1)\} ∏_{{j=R+1 \atop j≠i}}^{k}(1 − z̄_{i}z_{j}) ∏_{j=1}^{R−1}(z_{i} − z_{j}) .  (Bi2)

[ Type ‘S1411(k,R):’ in ROBBINS, for specific k and R.]

Proof: By Freshman Calculus (or rather the algebraic part of it), we know that the left side of (T amar), when viewed as a rational function of x_{R}, can be written as on its right side, for some polynomial P_{R}, and constants (in the present context, i.e. quantities not involving x_{R}) A_{i}, B_{i}. The degree of Φ_{k}, in x_{R} (or for that matter, in any variable), from its definition in (Gog_{1}), is ≤ 4k − 3, and the degree of the denominator of the left side of (T amar) is exactly 2(k − 1). Hence the degree of P_{R}, in x_{R}, is ≤ (4k − 3) − (2k − 2) = 2k − 1. The coefficients of P_{R} are certain rational functions of the remaining variables whose exact form does not interest us. The exact forms of A_{i} and B_{i} should interest us, since they are used heavily in the proof. So let’s brace ourselves and embark on partial-fractioning.

Multiplying both sides of (T amar) by the denominator of its left side yields the equation:

±Φ_{k}(x_{1}, …, x_{k}) = \{ ∏_{{j=1 \atop j≠R}}^{k}(1 − z_{j}x_{R}) ∏_{j=1}^{R−1}(1 − z̄_{j}x_{R}) ∏_{j=R+1}^{k}(1 − z_{j}x̄_{R})\} P_{R}

+ ∑_{{i=1 \atop i≠R}}^{k} \{ ∏_{{j=1 \atop j≠R,i}}^{k}(1 − z_{j}x_{R}) ∏_{j=1}^{R−1}(1 − z̄_{j}x_{R}) ∏_{j=R+1}^{k}(1 − z_{j}x̄_{R})\} A_{i}

+ ∑_{i=1}^{R−1} \{ ∏_{{j=1 \atop j≠R}}^{k}(1 − z_{j}x_{R}) ∏_{{j=1 \atop j≠i}}^{R−1}(1 − z̄_{j}x_{R}) ∏_{j=R+1}^{k}(1 − z_{j}x̄_{R})\} B_{i}

+ ∑_{i=R+1}^{k} \{ ∏_{{j=1 \atop j≠R}}^{k}(1 − z_{j}x_{R}) ∏_{j=1}^{R−1}(1 − z̄_{j}x_{R}) ∏_{{j=R+1 \atop j≠i}}^{k}(1 − z_{j}x̄_{R})\} B_{i} .  (T amar′)

To decipher A_{i} (1 ≤ i ≤ k, i ≠ R), we plug in x_{R} = 1/z_{i} on both sides of (T amar′) to get:

A_{i} = \frac{±Φ_{k}(x_{1}, …, x_{k})|_{x_{R}=1/z_{i}}}{\{∏k_{{j=1 \atop j≠R,i}} (1 − z_{j}/z_{i}) ∏_{j=1}^{R−1}(1 − z̄_{j}/z_{i}) ∏_{j=R+1}^{k}(1 − z_{j}(1 − 1/z_{i}))\}}

= \frac{±z_{i}^{2k−3}Φ_{k}(x_{1}, …, x_{k})|_{x_{R}=1/z_{i}}}{\{∏k_{{j=1 \atop j≠R,i}} (z_{i} − z_{j}) ∏_{j=1}^{R−1}(z_{i} − z̄_{j}) ∏_{j=R+1}^{k}(1 − z̄_{i}z̄_{j})\}} .  (P P 1)

To decipher B_{i} (1 ≤ i < R ), we plug in x_{R} = 1/z̄_{i} on both sides of (T amar′) to get:

B_{i} = \frac{±Φ_{k}(x_{1}, …, x_{k})|_{x_{R}=1/z̄_{i}}}{\{∏k_{{j=1 \atop j≠R}} (1 − z_{j}/z̄_{i}) ∏R−1_{{j=1 \atop j≠i}}(1 − z̄_{j}/z̄_{i}) ∏_{j=R+1}^{k}(1 − z_{j}(1 − 1/z̄_{i}))\}}

= \frac{±z̄_{i}^{2k−3}Φ_{k}(x_{1}, …, x_{k})|_{x_{R}=1/z̄_{i}}}{\{∏k_{{j=1 \atop j≠R}} (z̄_{i} − z_{j}) ∏R−1_{{j=1 \atop j≠i}}(z̄_{i} − z̄_{j}) ∏_{j=R+1}^{k}(1 − z_{i}z̄_{j})\}}  (1 ≤ i < R) .  (P P 2)

To decipher B_{i} (R < i ≤ k ), we plug in x̄_{R} = 1/z_{i}, i.e. x_{R} = 1 − 1/z_{i} = −z̄_{i}/z_{i}, on both sides of (T amar′) to get:

B_{i} = \frac{±Φ_{k}(x_{1}, …, x_{k})|_{x̄_{R}=1/z_{i}}}{\{∏k_{{j=1 \atop j≠R}} (1 + z_{j}z̄_{i}/z_{i}) ∏_{j=1}^{R−1}(1 + z̄_{j}z̄_{i}/z_{i}) ∏k_{{j=R+1 \atop j≠i}} (1 − z_{j}/z_{i})\}}

= \frac{±z_{i}^{2k−3}Φ_{k}(x_{1}, …, x_{k})|_{x̄_{R}=1/z_{i}}}{\{∏k_{{j=1 \atop j≠R}} (1 − z̄_{i}z̄_{j}) ∏_{j=1}^{R−1}(1 − z̄_{i}z_{j}) ∏k_{{j=R+1 \atop j≠i}} (z_{i} − z_{j})\}}  (R < i ≤ k) .  (P P 3)

We now need:

Subsubsubsublemma 1.4.1.1.1: For 1 ≤ R ≠ i ≤ k:

Φ_{k}(x_{1}, x_{2}, …, x_{k})|_{x_{R}=1/z_{i}} = ±\frac{(z_{i} − 2)(1 − 2z_{i})(1 − z_{i}^{2})(1 − z_{i}z̄_{i}) · Φ_{k−2}(x_{1}, …, x̂_{i}, …, x̂_{R}, …, x_{k})}{z_{i}^{3k−3}}·

∏_{{j=1 \atop j≠i,R}}^{k}\{(1 − z_{i}z_{j})(1 − z̄_{i}z_{j})(1 − z_{i}z̄_{j})(1 − z̄_{i}z̄_{j})(z_{j} − z_{i})(z_{j} + z_{i} − 1)\} .  (1.4.1.1.1)

[ Type ‘S14111(k,R,i):’ in ROBBINS, for specific k,R, and i.]

Proof: By the anti-symmetry of Φ_{k} with respect to the symmetric group, it suffices to consider R = 1. By its anti-symmetry w.r.t. the sign-action, it suffices to consider the case z_{i} = x_{i} (i.e. ε_{i} = +1). But this follows from multiplying the respective sides of the identities of (sub)^{4}lemma 1.3.1.1.1 (proved above) and subsublemma 1.5.2 (proved below). This completes the proof of (sub)^{4}lemma 1.4.1.1.1. .

Substituting (1.4.1.1.1) into (P P 1), (P P 2), and (P P 3), and cancelling out whenever possible, finishes up the proof of (sub)^{3}lemma 1.4.1.1. For (P P 3) we must note that Φ_{k} remains the same, except for a sign change, when one replaces x_{R} by x̄_{R}, so we can also apply 1.4.1.1.1 with x_{R} replaced by x̄_{R}. This completes the proof of (sub)^{3}lemma 1.4.1.1.

For the rest of the proof of (sub)^{2}lemma 1.4.1, we need some new notation. Let P OL stand for “some polynomial of (x_{1}, …, x_{k})”, and let RAT stand for “some rational function of (x_{1}, …, x_{k})”. P OL(x̂_{R}) stands for such a polynomial that does not involve x_{R}. P OLRAT (x_{R}; x_{1}, …, x̂_{R}, …, x_{k}), or P OLRAT (x_{R} ; …) for short, stands for a polynomial in x_{R} with coefficients that are rational

the electronic journal of combinatorics 3 (2) (1996), #R13 49

functions of the rest of the variables. P OLRAT (x_{i}; x̂_{R}) stands for a polynomial in x_{i} with coefficients that are rational functions of the remaining variables and that do not involve x_{R}. Inserting (T amar)(in the statement of 1.4.1.1) into (Jane) is going to yield the following (sub)^{3}lemma: Subsubsublemma 1.4.1.2:

F_{n,k}(ε_{1}(x_{1}), …, x_{R}, …, ε_{k}(x_{k}))
= \frac{P̃_{R}}{x_{R}^{n+1}x̄_{R}^{n+R+1}} + ∑_{{i=1 \atop i≠R}}^{k} \frac{Ã_{i}}{1 − z_{i}x_{R}} + ∑_{i=1}^{R−1} \frac{B̃_{i}}{1 − z̄_{i}x_{R}} + ∑_{i=R+1}^{k} \frac{B̃_{i}}{1 − z_{i}x̄_{R}} ,  (Celia)

where P̃_{R} is a polynomial of degree ≤ 2k − 1 in x_{R}, with coefficients that are rational functions of the rest of the variables, and Ã_{i}, and B̃_{i} can be written as follows. For 1 ≤ i < R, we have

Ã_{i} = \frac{P OL(x̂_{R})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+1}z̄_{i}^{n+i+1}} · ∏_{{j=1 \atop j≠i,R}}^{k} \frac{1}{z_{j}^{n+1}z̄_{j}^{n+j+1}} · ∏_{{1≤r<s≤k \atop r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})}

= \frac{P OLRAT (x_{i}; x̂_{R})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+1}z̄_{i}^{n+i+1}}  .  (Ãi1)

For R < i ≤ k, we have

Ã_{i} = \frac{P OL(x̂_{R})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+2}z̄_{i}^{n+i+1}} · ∏_{{j=1 \atop j≠i,R}}^{k} \frac{1}{z_{j}^{n+1}z̄_{j}^{n+j+1}} · ∏_{{1≤r<s≤k \atop r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})}

= \frac{P OLRAT (x_{i}; x̂_{R})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+2}z̄_{i}^{n+i+1}}  .  (Ãi2)

For 1 ≤ i < R, we have

B̃_{i} = \frac{P OL(x̂_{R})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+1}z̄_{i}^{n+i+k+1}} · ∏_{{j=1 \atop j≠i,R}}^{k} \frac{1}{z_{j}^{n+1}z̄_{j}^{n+j+1}} · ∏_{{1≤r<s≤k \atop r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})}

= \frac{P OLRAT (x_{i}; x̂_{R})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+1}z̄_{i}^{n+i+k+1}} .  (B̃i1)

Finally, for R < i ≤ k, we have

B̃_{i} = \frac{P OL(x̂_{R})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+2}z̄_{i}^{n+i+1}} · ∏_{{j=1 \atop j≠i,R}}^{k} \frac{1}{z_{j}^{n+1}z̄_{j}^{n+j+1}} · ∏_{{1≤r<s≤k \atop r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})}

= \frac{P OLRAT (x_{i}; x̂_{R})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+2}z̄_{i}^{n+i+1}} .  (B̃i2)

Furthermore, all the P OLRAT S are of degree ≤ 2k + 1 in x_{i} (we actually only use this fact for the P OLRAT of (B̃i1)).

[ Type ‘S1412(k,n,eps,R):’ in ROBBINS, for specific k,n,eps, and R.]

Proof: Insert (T amar) into (Jane), bringing the quantity in front of the sums inside, and for each A_{i} and B_{i}, split the double product:

∏_{{1≤r<s≤k \atop r,s≠R}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})} = ∏_{{1≤r<s≤k \atop r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})}· ∏_{{j=1 \atop j≠R}}^{i−1} \frac{1}{(1 − z_{j}z_{i})(1 − z̄_{j}z_{i})} ∏_{{j=i+1 \atop j≠R}}^{k} \frac{1}{(1 − z_{i}z_{j})(1 − z̄_{i}z_{j})},

(Split)

where the condition j ≠ R is vacuous in exactly one of the two last products according to whether i < R or i > R. Finally perform all possible cancellations. This completes the proof of (sub)^{3}lemma 1.4.1.2.

We will say that a rational function h = h(x_{1}, …, x_{k}) has property (Hadas) if:

Res_{x_{π(1)},...,x_{π(k)}}[h] = Res_{x_{π(1)},...,x_{π(k)}}[h(x_{R} → x̄_{R})] ,  (Hadas)

where h(x_{R} → x̄_{R}) is the rational function obtained from h by replacing the variable x_{R} by x̄_{R} (= 1 − x_{R}.)

The statement of subsublemma 1.4.1 is equivalent to saying that

F_{n,k}(ε_{1}(x_{1}), …, x_{R}, …, ε_{k}(x_{k}))

has property (Hadas). Property (Hadas) is obviously additive (since the action of taking residue, and performing x_{R} → x̄_{R} are), so in order to complete the proof of 1.4.1 (and hence of 1.4), it would suffice to show that each term in (Celia) has property (Hadas). This will be accomplished by the following series of subsubsublemmas (1.4.1.3 − 6.)

Subsubsublemma 1.4.1.3: Let P̃_{R} be as in the statement of 1.4.1.2, i.e. a polynomial of degree ≤ 2k − 1 in x_{R} with coefficients that are rational functions of the remaining variables. Then

\frac{_{P_{R}}}{x_{R}^{n+1}x̄_{R}^{n+R+1}} has property (Hadas):

Res_{x_{π(1)},...,x_{π(k)}} [\frac{P̃_{R}}{x_{R}^{n+1}x̄_{R}^{n+R+1}} ] = Res_{x_{π(1)},...,x_{π(k)}} [\frac{P̃_{R}}{x_{R}^{n+1}x̄_{R}^{n+R+1}} (x_{R} → x̄_{R})] . (Hadas_{1})

[ Type ‘S1413(k,n):’ in ROBBINS, for specific k and n.]

Proof: Recall that R = π(u). Since P̃_{R} is a P OLRAT (x_{R}; x_{1}, …, x̂_{R}, …, x_{k}), we have that

Res_{x_{π(u+1)},...,x_{π(k)}} [\frac{P̃_{R}}{x_{R}^{n+1}x̄_{R}^{n+R+1}} ] = Res_{x_{π(u+1)},...,x_{π(k)}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x̂_{R}, x_{π(u+1)}, …, x_{π(k)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}}]

= \frac{P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}} = \frac{x_{R}^{R} · P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+R+1}x̄_{R}^{n+R+1}} .

Since the degree of x_{R}^{R}P OLRAT (x_{R} ; …), in x_{R}, is ≤ R + (2k − 1) ≤ 2(n + R), it follows from crucial fact ℵ′_{5} that

Res_{x_{R}} [\frac{P OLRAT (x_{R} ; …)}{x_{R}^{n+1}x̄_{R}^{n+R+1}}] = Res_{x_{R}} [\frac{P OLRAT (x_{R} ; …)}{x_{R}^{n+1}x̄_{R}^{n+R+1}}(x_{R} → x̄_{R})] .

Applying Res_{x_{π(1)},...,x_{π(u−1)}} to both sides of the above equation establishes that \frac{_{P_{R}}}{x_{R}^{n+1}x̄_{R}^{n+R+1}} indeed has property (Hadas), so that (Hadas_{1}) holds. This completes the proof of subsubsublemma 1.4.1.3.

Subsubsublemma 1.4.1.4: Let Ã_{i} be as in the statement of 1.4.1.2, i.e. given by (Ãi1) and (Ãi2) according to whether i < R or i > R respectively. Then:

Res_{x_{π(1)},...,x_{π(k)}}[\frac{Ã_{i}}{1 − z_{i}x_{R}}] = Res_{x_{π(1)},...,x_{π(k)}}[\frac{Ã_{i}}{1 − z_{i}x_{R}} (x_{R} → x̄_{R})] .  (Hadas_{2})

[ Type ‘S1414(k,n):’ in ROBBINS, for specific k and n.]

Proof: Recall that u = π^{−1}(R). (Ãi1) that gives Ã_{i} for i < R, and (Ãi2) that gives Ã_{i} for i > R are of the same form, except that the power of z_{i} in the denominator of (Ãi2) is 1 more (namely n + k + 2) than its counterpart (n + k + 1) in (Ãi1). Multiplying top and bottom of (Ãi1) by z_{i} makes them exactly of the same form.

Case I: i ∈ {π(u + 1), …, π(k)} .

Let v := π^{−1}(i), so that i = π(v), and v > u.

We have that:

\frac{Ã_{i}}{1 − z_{i}x_{R}} = \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}, x_{π(v+1)}, …, x_{π(k)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+2}z̄_{i}^{n+i+1}(1 − z_{i}x_{R})} .

Applying Res_{x_{π(v+1)},...,x_{π(k)}} to it gives:

Res_{x_{π(v+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − z_{i}x_{R}} ] = \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+2}z̄_{i}^{n+i+1}(1 − z_{i}x_{R})} .

Applying Res_{x_{i}} to the above gives:

Res_{x_{i},x_{π(v+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − z_{i}x_{R}} ] = Res_{x_{i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+k+2}z̄_{i}^{n+i+1}(1 − z_{i}x_{R})}]

= \frac{1}{x_{R}^{n+1}x̄_{R}^{n+R+1}} · Res_{x_{i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{z_{i}^{n+k+2}z̄_{i}^{n+i+1}(1 − z_{i}x_{R})}] .  (Doron)

We now distinguish two subcases:

Subcase Ia: ε_{i} = +1, that is: z_{i} = x_{i}.

In this subcase, the right side of (Doron) equals:

\frac{1}{x_{R}^{n+1}x̄_{R}^{n+R+1}} · Coeff_{x_{i}^{n+k+1}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x̄_{i}^{n+i+1}(1 − x_{i}x_{R})}] .  (Gil)

Expanding everything involving x_{i} as a power series in x_{i}:

P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}) = ∑_{t=0}^{degree} RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})x_{i}^{t} ,

\frac{1}{x̄_{i}^{n+i+1}} = ∑_{t=0}^{∞} NUMBER_{t} · x_{i}^{t} ,

and, most importantly:

(1 − x_{i}x_{R})^{−1} = ∑_{t=0}^{∞} x_{R}^{t}x_{i}^{t} .

Multiplying out, and collecting the coefficient of x_{i}^{n+k+1}, gives that Coeff_{x_{i}^{n+k+1}} in (Gil) is a certain polynomial in x_{R}, of degree ≤ n + k + 1, with coefficients that are rational functions of (x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}). In other words it is a P OLRAT (x_{R}; x_{π(1)}, …, x_{π(v−1)}) with deg_{x_{R}} ≤ n + k + 1. Hence,

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(v−1)}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}}] ,

(Gil′)

where the P OLRAT in (Gil′) has degree ≤ n + k + 1 in x_{R}. Applying Res_{x_{π(u+1)},...,x_{π(v−1)}} to the residuand of (Gil′) gets rid of the dependence on (x_{π(u+1)}, …, x_{π(v−1)}), so we have:

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}}] ,  (Gil′′)

where P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)}) has degree ≤ n + k + 1 in x_{R}.

But, the right of (Gil′′) can be rewritten as:

Res_{x_{R}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}}] = Res_{x_{R}} [\frac{x_{R}^{R} · P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+R+1}x̄_{R}^{n+R+1}}] .

(Gil′′′)

By crucial fact ℵ′_{5}, since R + (n + k + 1) ≤ 2(n + R) (recall that always n ≥ k and R ≥ 1), we can perform x_{R} → x̄_{R} in the residuand of (Gil′′′), so

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} (x_{R} → x̄_{R})] .

Applying Res_{x_{π(1)},...,x_{π(u−1)}} to both sides of the above equation finishes up subcase Ia of the proof of (sub)^{3}lemma 1.4.1.4.

Subcase Ib: ε_{i} = −1, that is: z_{i} = x̄_{i}.

In this subcase, the right side of (Doron) equals:

\frac{1}{x_{R}^{n+1}x̄_{R}^{n+R+1}} · Coeff_{x_{i}^{n+i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x̄_{i}^{n+k+2}(1 − x̄_{i}x_{R})}] .  (Gil)

Expanding everything involving x_{i} as a power series in x_{i}:

P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}) = ∑_{t=0}^{degree} RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})x_{i}^{t} ,

\frac{1}{x̄_{i}^{n+k+2}} = ∑_{t=0}^{∞} NUMBER_{t} · x_{i}^{t} ,

and, most importantly:

(1 − x̄_{i}x_{R})^{−1} = (1 − x_{R} + x_{i}x_{R})^{−1} = (x̄_{R} + x_{i}x_{R})^{−1} = ∑_{t=0}^{∞}(−1)^{t} \frac{x_{R}^{t}}{x̄_{R}^{t+1}} x_{i}^{t} ,

multiplying out, and collecting the coefficient of x_{i}^{n+i}, gives that Coeff_{x_{i}^{n+i}} in (Gil) is a certain sum of terms of the form

RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})\frac{x_{R}^{t}}{x̄_{R}^{t+1}} , (t ≥ 0) .

Hence,

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x̄_{i}x_{R}} ]

is a sum of terms of the forms

Res_{x_{R},x_{π(u+1)},...,x_{π(v−1)}} [\frac{x_{R}^{t} · RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+t+2}}] , (t ≥ 0) .  (Gil′)

Applying Res_{x_{π(u+1)},...,x_{π(v−1)}} to the residuand of (Gil′) gets rid of the dependence on (x_{π(u+1)}, …, x_{π(v−1)}), so we have that

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x̄_{i}x_{R}} ]

the electronic journal of combinatorics 3 (2) (1996), #R13 54

is a sum of terms of the form

Res_{x_{R}} [\frac{x_{R}^{t}RAT_{t}(x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+t+2}}] , (t ≥ 0) .  (Gil′′)

But, each such term can be written as

RAT_{t}(x_{π(1)}, …, x_{π(u−1)})Res_{x_{R}} [\frac{x_{R}^{R+2t+1}}{x_{R}^{n+R+t+2}x̄_{R}^{n+R+t+2}} ] , (t ≥ 0) .  (Gil′′′)

By crucial fact ℵ′_{5}, since R + 2t + 1 ≤ 2(n + R + t + 1), we can perform x_{R} → x̄_{R} in the residuand of (Gil′′′), so

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x̄_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x̄_{i}x_{R}} (x_{R} → x̄_{R})] .

Applying Res_{x_{π(1)},...,x_{π(u−1)}} to both sides of the above equation finishes up subcase Ib of the proof of subsubsublemma 1.4.1.4. Case II: i ∈ {π(1), …, π(u − 1)} . Let v := π^{−1}(i), so that i = π(v), and v < u. By the definition of u, ε_{i} must be equal to +1, so that z_{i} = x_{i}. The left side of (Hadas_{2}) (in the statement of (sub)^{3}lemma 1.4.1.4, which we are currently proving,) can be written as:

Res_{x_{π(1)},...,x_{π(k)}}[\frac{Ã_{i}}{1 − x_{i}x_{R}}] = Res_{x_{π(1)},...,x_{π(v−1)},x_{i},x_{π(v+1)},...,x_{π(u−1)},x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ] .

(Ruthie)

The next (sub)^{4}lemma assures us that, on the right side of (Ruthie), in the order of residue taking Res_{x_{π(1)},...,x_{π(k)}}, it is permissible to transpose x_{i} and x_{R}, without affecting its value, and likewise when the residuand is replaced by \frac{_{A_{i}}}{1−x_{i}x_{R}} (x_{R} → x̄_{R}). Subsubsubsublemma 1.4.1.4.1:

Res_{x_{π(1)},...,x_{π(v−1)},x_{i},x_{π(v+1)},...,x_{π(u−1)},x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ]

= Res_{x_{π(1)},...,x_{π(v−1)},x_{R},x_{π(v+1)},...,x_{π(u−1)},x_{i},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ] ,  (Noam)

and

Res_{x_{π(1)},...,x_{π(v−1)},x_{i},x_{π(v+1)},...,x_{π(u−1)},x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} (x_{R} → x̄_{R})]

= Res_{x_{π(1)},...,x_{π(v−1)},x_{R},x_{π(v+1)},...,x_{π(u−1)},x_{i},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} (x_{R} → x̄_{R})] . (\overline{Noam})

We will only prove (Noam), since the proof of (\overline{Noam}) goes verbatim. Changing the order of residue-taking from Res_{x_{π(1)},...,x_{i},...,x_{R},...,x_{π(k)}} to Res_{x_{π(1)},...,x_{R},...,x_{i},...,x_{π(k)}} is permitted by crucial fact ℵ_{4}, provided the residuand of Res_{x_{π(1)},...,x_{i},...,x_{R}} on the left side of (Noam), namely,

Res_{x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ] ,

possesses a bona fide Laurent expansion in its variables (x_{π(1)}, …, x_{i}, …, x_{π(u−1)}, x_{R}), i.e. that it is a rational function whose denominator is a monomial times a polynomial with a non-zero constant term.

This fact would follow, by invoking the case w = u, from the following (sub)^{5}lemma.

Subsubsubsubsublemma 1.4.1.4.1.1 : Let u ≤ w ≤ k, and π^{−1}(i) < u, then

Res_{x_{π(w+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ]

can be expressed as a sum of terms of the form

\frac{P OL(x_{π(1)}, …, x̂_{R}, …, x_{π(w)})}{1 − x_{i}x_{R}} · ∏_{j=1}^{w} \frac{1}{z_{π(j)}^{α_{j}}z̄_{π(j)}^{β_{j}}} · ∏_{{r,s∈\{π(1),...,π(w)\} \atop r<s;r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})} .

Proof: The proof is by decreasing induction on w. When w = k then this follows tautologically from (Ãi1) and (Ãi2). Suppose the statement of the (sub)^{5}lemma is true when w is replaced by w + 1, and let’s deduce from it that it is true for w proper.

By the inductive hypothesis, the quantity of interest is a sum of terms of the form

Res_{x_{π(w+1)}} [\frac{P OL(x_{π(1)}, …, x̂_{R}, …, x_{π(w)}, x_{π(w+1)})}{1 − x_{i}x_{R}} · ∏_{j=1}^{w+1} \frac{1}{z_{π(j)}^{α_{j}}z̄_{π(j)}^{β_{j}}} · ∏_{{r,s∈\{π(1),...,π(w+1)\} \atop r<s;r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})}] .

Let’s abbreviate π(w + 1) to S, α_{w+1} to α and β_{w+1} to β. Then the above can be rewritten as:

\frac{1}{1 − x_{i}x_{R}} ∏_{j=1}^{w} \frac{1}{z_{π(j)}^{α_{j}}z̄_{π(j)}^{β_{j}}} · ∏_{{r,s∈\{π(1),...,π(w)\} \atop r<s;r,s≠R,i}} \frac{1}{(1 − z_{r}z_{s})(1 − z̄_{r}z_{s})} · Res_{x_{S}}[

\frac{P OL(x_{π(1)}, …, x̂_{R}, …, x_{π(w)}, x_{S})}{z_{S}^{α}z̄_{S}^{β}} ∏_{{r∈\{π(1),...,π(w)\} \atop r≠S,R,i}} \frac{1}{1 − z_{r}z_{S}} ∏_{{r∈\{π(1),...,π(w)\} \atop r<S;r≠R,i}} \frac{1}{1 − z̄_{r}z_{S}} ∏_{{r∈\{π(1),...,π(w)\} \atop r>S;r≠R,i}} \frac{1}{1 − z̄_{S}z_{r}}].

Res_{x_{S}}[…] above can be rewritten as:

Coeff_{x_{S}^{(α or β)−1}}

[\frac{P OL(x_{π(1)}, …, x̂_{R}, …, x_{π(w)}, x_{S})}{x̄_{S}^{(β or α)}} ∏_{{r∈\{π(1),...,π(w)\} \atop r≠S,R,i}} \frac{1}{1 − z_{r}z_{S}} ∏_{{r∈\{π(1),...,π(w)\} \atop r<S;r≠R,i}} \frac{1}{1 − z̄_{r}z_{S}} ∏_{{r∈\{π(1),...,π(w)\} \atop r>S;r≠R,i}} \frac{1}{1 − z̄_{S}z_{r}} ] .
(Danny)

Expanding everything in powers of x_{S}, using

P OL(x_{π(1)}, …, x̂_{R}, …, x_{π(w)}, x_{S}) = ∑_{t=0}^{finite} P OL_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(w)})x_{S}^{t} ,

\frac{1}{1 − x_{S}z_{r}} = ∑_{t=0}^{∞} z_{r}^{t}x_{S}^{t} , \frac{1}{1 − x_{S}z̄_{r}} = ∑_{t=0}^{∞} z̄_{r}^{t}x_{S}^{t} ,

and/or

\frac{1}{1 − x̄_{S}z_{r}} = \frac{1}{z̄_{r} + z_{r}x_{S}} = ∑_{t=0}^{∞} \frac{(−1)^{t}z_{r}^{t}}{z̄_{r}^{t+1}} x_{S}^{t} , \frac{1}{1 − x̄_{S}z̄_{r}} = \frac{1}{z_{r} + z̄_{r}x_{S}} = ∑_{t=0}^{∞} \frac{(−1)^{t}z̄_{r}^{t}}{z_{r}^{t+1}} x_{S}^{t} ,

for r ∈ {π(1), …, π(w)} \ {i, R}, as well as,

\frac{1}{x̄_{S}^{number}} = ∑_{t=0}^{∞} NUMBER_{t} · x_{S}^{t}

multiplying out, and then taking the appropriate coefficient of x_{S} in (Danny), shows that indeed the statement of the (sub)^{5}lemma also holds with w, except that the previous sum (in the case w + 1) has been replaced by a much larger, but still finite, sum. This completes the proof of (sub)^{5}lemma 1.4.1.4.1.1.

Going back to the proof of (sub)^{4}lemma 1.4.1.4.1, we employ the above (sub)^{5}lemma with its lowest case, w = u. By the definition of u, ε_{π(1)} = …, ε_{π(u−1)} = +1, so that z_{π(1)} = x_{π(1)}, …, z_{π(u−1)} = x_{π(u−1)}, and we see that

Res_{x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ]

can be expressed as a sum of terms of the form

\frac{P OL(x_{π(1)}, …, x_{π(u−1)})}{1 − x_{R}x_{i}} · ∏_{j=1}^{u} \frac{1}{x_{π(j)}^{α_{j}}x̄_{π(j)}^{β_{j}}} · ∏_{{r,s∈\{π(1),...,π(u−1)\} \atop r<s;r,s≠i}} \frac{1}{(1 − x_{r}x_{s})(1 − x̄_{r}x_{s})} ,

each of which possesses a genuine Laurent series in its arguments (x_{π(1)}, …, x_{π(u)}), so for each of these, by ℵ′_{4}, applying Res_{...,x_{i},...,x_{R}} to them is the same as applying Res_{...,x_{R},...,x_{i}}, and this finishes up the proof of (sub)^{4}lemma 1.4.1.4.1. .

the electronic journal of combinatorics 3 (2) (1996), #R13 57

Going back to the proof of Case II of (sub)^{3}lemma 1.4.1.4 , we use (sub)^{4}lemma 1.4.1.4.1 to change the right side of (Ruthie) to:

Res_{x_{π(1)},...,x_{π(v−1)},x_{R},x_{π(v+1)},...,x_{π(u−1)},x_{i},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} ] .  (Ruthie′)

But this is identical to the form treated by subcase Ia, which says that this is the same as:

Res_{x_{π(1)},...,x_{π(v−1)},x_{R},x_{π(v+1)},...,x_{π(u−1)},x_{i},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} (x_{R} → x̄_{R})] .  (Ruthie′′)

Now, we use the second part of (sub)^{4}lemma 1.4.1.4.1, i.e. (\overline{Noam}) (whose proof was omitted since it was identical to that of (Noam)), to change this into

Res_{x_{π(1)},...,x_{π(v−1)},x_{i},x_{π(v+1)},...,x_{π(u−1)},x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{Ã_{i}}{1 − x_{i}x_{R}} (x_{R} → x̄_{R})] ,

which was exactly what we had to show in order to complete the proof of Case II of (sub)^{3}lemma 1.4.1.4. This completes the proof of (sub)^{3}lemma 1.4.1.4. . Subsubsublemma 1.4.1.5: Let B̃_{i}, (1 ≤ i < R), be as in the statement of 1.4.1.2, i.e. given by (B̃i1). Then

Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z̄_{i}x_{R}} ] = Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z̄_{i}x_{R}} (x_{R} → x̄_{R})] .  (Hadas_{3})

[ Type ‘S1415(k,n):’ in ROBBINS, for specific k and n.]

Proof: Case I: i ∈ {π(u + 1), …, π(k)} . Let v := π^{−1}(i), so that i = π(v), and v > u. We have that:

\frac{B̃_{i}}{1 − z̄_{i}x_{R}} = \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}, x_{π(v+1)}, …, x_{π(k)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+1}z̄_{i}^{n+i+k+1}(1 − z̄_{i}x_{R})} .

Applying Res_{x_{π(v+1)},...,x_{π(k)}} to it gives:

Res_{x_{π(v+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z̄_{i}x_{R}} ] = \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+1}z̄_{i}^{n+i+k+1}(1 − z̄_{i}x_{R})} .

Applying Res_{x_{i}} to the above gives:

Res_{x_{i},x_{π(v+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z̄_{i}x_{R}} ] = Res_{x_{i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}z_{i}^{n+1}z̄_{i}^{n+i+k+1}(1 − z̄_{i}x_{R})}]

= \frac{1}{x_{R}^{n+1}x̄_{R}^{n+R+1}} · Res_{x_{i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{z_{i}^{n+1}z̄_{i}^{n+i+k+1}(1 − z̄_{i}x_{R})}] .  (Doron)

We now distinguish two subcases:

Subcase Ia: ε_{i} = −1, that is: z̄_{i} = x_{i} (i.e. z_{i} = x̄_{i}).

In this subcase, the right side of (Doron) equals:

\frac{1}{x_{R}^{n+1}x̄_{R}^{n+R+1}} · Coeff_{x_{i}^{n+i+k}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x̄_{i}^{n+1}(1 − x_{i}x_{R})}] .  (Gil)

Expanding everything involving x_{i} as a power series in x_{i}:

P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}) = ∑_{t=0}^{degree} RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})x_{i}^{t} ,

\frac{1}{x̄_{i}^{n+1}} = ∑_{t=0}^{∞} NUMBER_{t} · x_{i}^{t} ,

and, most importantly:

(1 − x_{i}x_{R})^{−1} = ∑_{t=0}^{∞} x_{R}^{t}x_{i}^{t} ,

multiplying out, and collecting the coefficient of x_{i}^{n+i+k}, gives that Coeff_{x_{i}^{n+i+k}} in (Gil) is a certain polynomial in x_{R}, of degree ≤ n + i + k, with coefficients that are rational functions of (x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}). In other words it is a P OLRAT (x_{R}; x_{π(1)}, …, x_{π(v−1)}) with deg_{x_{R}} ≤ n + i + k. Hence,

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(v−1)}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}}] ,

(Gil′)

where the P OLRAT in (Gil′) has degree ≤ n + i + k in x_{R}. Applying Res_{x_{π(u+1)},...,x_{π(v−1)}} to the residuand of (Gil′) gets rid of the dependence on (x_{π(u+1)}, …, x_{π(v−1)}), so we have:

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R}} [\frac{P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}}] ,  (Gil′′)

where P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)}) has degree ≤ n + i + k in x_{R}.

But, the right of (Gil′′) can be rewritten as:

Res_{x_{R}} [\frac{x_{R}^{R} · P OLRAT (x_{R}; x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+R+1}x̄_{R}^{n+R+1}}] .  (Gil′′′)

By crucial fact ℵ′_{5}, since R + (n + i + k) ≤ 2(n + R) (recall that always n ≥ k and i < R), we can perform x_{R} → x̄_{R} in the residuand of (Gil′′′), so

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x_{i}x_{R}} (x_{R} → x̄_{R})] .

Applying Res_{x_{π(1)},...,x_{π(u−1)}} to both sides of the above equation finishes up subcase Ia of the proof of subsublemma 1.4.1.5.

Subcase Ib: ε_{i} = 1, that is: z̄_{i} = x̄_{i} (i.e. z_{i} = x_{i}).

In this subcase, the right side of (Doron) equals:

\frac{1}{x_{R}^{n+1}x̄_{R}^{n+R+1}} · Coeff_{x_{i}^{n}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x̄_{i}^{n+i+k+1}(1 − x̄_{i}x_{R})}] .  (Gil)

Expanding everything involving x_{i} as a power series in x_{i}:

P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}) = ∑_{t=0}^{degree} RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})x_{i}^{t} ,

\frac{1}{x̄_{i}^{n+i+k+1}} = ∑_{t=0}^{∞} NUMBER_{t} · x_{i}^{t} ,

and, most importantly:

(1 − x̄_{i}x_{R})^{−1} = (1 − x_{R} + x_{i}x_{R})^{−1} = (x̄_{R} + x_{i}x_{R})^{−1} = ∑_{t=0}^{∞}(−1)^{t} \frac{x_{R}^{t}}{x̄_{R}^{t+1}} x_{i}^{t} ,

multiplying out, and collecting the coefficient of x_{i}^{n}, gives that Coeff_{x_{i}^{n}} in (Gil) is a certain sum of terms of the form

RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})\frac{x_{R}^{t}}{x̄_{R}^{t+1}} , (t ≥ 0) .

Hence,

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ]

is a sum of terms of the forms

Res_{x_{R},x_{π(u+1)},...,x_{π(v−1)}} [\frac{x_{R}^{t} · RAT_{t}(x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+t+2}}] , (t ≥ 0) .  (Gil′)

Applying Res_{x_{π(u+1)},...,x_{π(v−1)}} to the residuand of (Gil′) gets rid of the dependence on (x_{π(u+1)}, …, x_{π(v−1)}), so we have that

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ]

the electronic journal of combinatorics 3 (2) (1996), #R13 60

is a sum of terms of the form

Res_{x_{R}} [\frac{x_{R}^{t}RAT_{t}(x_{π(1)}, …, x_{π(u−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+t+2}}] , (t ≥ 0) .  (Gil′′)

But, each such term can be written as

RAT_{t}(x_{π(1)}, …, x_{π(u−1)}) · Res_{x_{R}} [\frac{x_{R}^{R+2t+1}}{x_{R}^{n+R+t+2}x̄_{R}^{n+R+t+2}} ] , (t ≥ 0) .  (Gil′′′)

By crucial fact ℵ′_{5}, since R + 2t + 1 ≤ 2(n + R + t + 1), we can perform x_{R} → x̄_{R} in the residuand of (Gil′′′), so

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ] = Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} (x_{R} → x̄_{R})] .

Applying Res_{x_{π(1)},...,x_{π(u−1)}} to both sides of the above equation finishes up subcase Ib of the proof of subsubsublemma 1.4.1.5. Case II: i ∈ {π(1), …, π(u − 1)} . Let v := π^{−1}(i), so that i = π(v), and v < u. By the definition of u, ε_{i} must be equal to +1, so that z_{i} = x_{i}. The left side of (Hadas_{3}) can be written as:

Res_{x_{π(1)},...,x_{π(k)}}[\frac{B̃_{i}}{1 − x̄_{i}x_{R}}] = Res_{x_{π(1)},...,x_{π(v−1)},x_{i},x_{π(v+1)},...,x_{π(u−1)},x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ] .

(Ruthie)

The first step is to ‘unbar’ the x_{i} in (Ruthie). Subsubsubsublemma 1.4.1.5.1: Let B̃_{i}, (1 ≤ i < R), be as in the statement of 1.4.1.2, i.e. given by (B̃i1). (Recall that π is an arbitrary permutation, π(u) = R, π(v) = i and v < u.) Then

Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}(x_{i} → x̄_{i})}{1 − x_{i}x_{R}}] = Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ] .  (Michal)
Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}(x_{i} → x̄_{i}, x_{R} → x̄_{R})}{1 − x_{i}x̄_{R}}] = Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}(x_{R} → x̄_{R})}{1 − x̄_{i}x̄_{R}}] . (Michal′)

Proof: The proof of (Michal) and (Michal′) are very similar to subcases Ia and Ib respectively, except that the roles of i and R are reversed. We will only prove (Michal), since (Michal′) is almost identical to the proof of subcase Ib (with i and R interchanged.)

We have that:

\frac{B̃_{i}(x_{i} → x̄_{i})}{1 − x_{i}x_{R}} = \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{R}, …, x_{π(v−1)}, x_{π(v+1)}, …, x_{π(k)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}x̄_{i}^{n+1}x_{i}^{n+i+k+1}(1 − x_{i}x_{R})} .

Applying Res_{x_{π(u+1)},...,x_{π(k)}} to it gives:

Res_{x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}(x_{i} → x̄_{i})}{1 − x_{i}x_{R}}] = \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{i}, …, x_{π(u−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}x̄_{i}^{n+1}x_{i}^{n+i+k+1}(1 − x_{i}x_{R})} .

Applying Res_{x_{R}} to the above gives:

Res_{x_{R},x_{π(u+1)},...,x_{π(k)}} [\frac{B̃_{i}(x_{i} → x̄_{i})}{1 − x_{i}x_{R}}] = Res_{x_{R}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{i}, …, x_{π(u−1)})}{x_{R}^{n+1}x̄_{R}^{n+R+1}x̄_{i}^{n+1}x_{i}^{n+i+k+1}(1 − x_{i}x_{R})}]

= \frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{i}, …, x_{π(u−1)})}{x_{i}^{n+i+k+1}x̄_{i}^{n+1}} · Res_{x_{R}} [\frac{1}{x_{R}^{n+1}x̄_{R}^{n+R+1}(1 − x_{i}x_{R})}] .  (Herb)

The right side of (Herb) equals:

\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{i}, …, x_{π(u−1)})}{x_{i}^{n+i+k+1}x̄_{i}^{n+1}} · Coeff_{x_{R}^{n}} [\frac{1}{x̄_{R}^{n+R+1}(1 − x_{i}x_{R})}] .  (David)

Expanding the two quantities involving x_{R} above as a power series in x_{R}:

\frac{1}{x̄_{R}^{n+R+1}} = ∑_{t=0}^{∞} NUMBER_{t} · x_{R}^{t} ,

and, more importantly:

(1 − x_{i}x_{R})^{−1} = ∑_{t=0}^{∞} x_{i}^{t}x_{R}^{t} ,

multiplying out, and collecting the coefficient of x_{R}^{n}, gives that Coeff_{x_{R}^{n}} in (David) is a certain polynomial in x_{i}, of degree ≤ n. Combined with the P OLRAT in the front of (David) (whose degree in x_{i} is ≤ 2k + 1, by the last sentence of the statement of (sub)^{3}lemma 1.4.1.2) we have a P OLRAT in x_{i} of degree ≤ n + 2k + 1 in x_{i}.

Hence,

Res_{x_{i},x_{π(v+1)},...,x_{π(k)}} [\frac{B̃_{i}(x_{i} → x̄_{i})}{1 − x_{i}x_{R}}] = Res_{x_{i},x_{π(v+1)},...,x_{π(u−1)}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x̂_{i}, …, x_{π(u−1)})}{x_{i}^{n+i+k+1}x̄_{i}^{n+1}}] ,

(David′)

where the P OLRAT in (David′) has degree ≤ n + 2k + 1 in x_{i}. Applying Res_{x_{π(v+1)},...,x_{π(u−1)}} to the residuand of the right side of (David′) gets rid of the dependence on (x_{π(v+1)}, …, x_{π(u−1)}), so we have:

Res_{x_{i},x_{π(v+1)},...,x_{π(k)}} [\frac{B̃_{i}(x_{i} → x̄_{i})}{1 − x_{i}x_{R}}] = Res_{x_{i}} [\frac{P OLRAT (x_{i}; x_{π(1)}, …, x_{π(v−1)})}{x_{i}^{n+i+k+1}x̄_{i}^{n+1}}] , (David′′)

where P OLRAT (x_{i}; x_{π(1)}, …, x_{π(v−1)}) has degree ≤ n + 2k + 1 in x_{i}.

But, the right of (David′′) can be rewritten as:

Res_{x_{i}} [\frac{x̄_{i}^{i+k} · P OLRAT (x_{i}; x_{π(1)}, …, x_{π(v−1)})}{x_{i}^{n+i+k+1}x̄_{i}^{n+i+k+1}}] .  (David′′′)

By crucial fact ℵ′_{5}, since (i + k) + n + (2k + 1) ≤ 2(n + i + k) (recall that always n ≥ k and i ≥ 1), we can perform x_{i} → x̄_{i} in the residuand of (David′′′), so

Res_{x_{i},x_{π(v+1)},...,x_{π(k)}} [\frac{B̃_{i}(x_{i} → x̄_{i})}{1 − x_{i}x_{R}}] = Res_{x_{i},x_{π(v+1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − x̄_{i}x_{R}} ] .

Applying Res_{x_{π(1)},...,x_{π(v−1)}} to both sides of the above equation finishes up the proof of (Michal). As we said, the proof of (Michal′) is left to the reader. This finishes the proof of (sub)^{4}lemma 1.4.1.5.1.

Going back to the proof of case II of (sub)^{3}lemma 1.4.1.5, we have to prove that the right sides of (Michal) and (Michal′) are equal to each other. By the above (sub)^{4}lemma, this would follow from their left sides being equal to each other. But the proof of this is exactly as that of case II of (sub)^{3}lemma 1.4.1.4: one proves the analog of (Noam) and (\overline{Noam}), which reduce the statements to that of subcase Ia. This completes the proof of (sub)^{3}lemma 1.4.1.5.

We have one more (sub)^{3}lemma to go before we can complete the proof of (sub)^{2}lemma 1.4.1, which is to show that the last sum on the right side of (Celia) (in the statement of (sub)^{3}lemma 1.4.1.2, also has property (Hadas).)

Subsubsublemma 1.4.1.6: Let B̃_{i}, (R < i ≤ k), be as in the statement of 1.4.1.2, i.e. given by (B̃i2). Then

Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z_{i}x̄_{R}} ] = Res_{x_{π(1)},...,x_{π(k)}} [\frac{B̃_{i}}{1 − z_{i}x̄_{R}} (x_{R} → x̄_{R})] .  (Hadas_{4})

[ Type ‘S1416(k,n):’ in ROBBINS, for specific k and n.]

Proof: The form of B̃_{i}, for R < i ≤ k, given by (B̃i2) is identical to that of Ã_{i}, for R < i ≤ k, given by (Ãi2). The only difference between the statement of (sub)^{3}lemma 1.4.1.4 and that of 1.4.1.6 is that the x_{R} in the denominator of \frac{_{A_{i}}}{1−z_{i}x_{R}} is changed into x̄_{R} : \frac{_{B_{i}}}{1−z_{i}x̄_{R}}. The proof goes verbatim. This completes the proof of (sub)^{3}lemma 1.4.1.6.

Going back to the proof of (sub)^{2}lemma 1.4.1, we know by (sub)^{3}lemmas (1.4.1.3−6) that each part of (Celia), in the statement of (sub)^{3}lemma 1.4.1.2, has property (Hadas), and by the additivity of this property, so does the whole F_{n,k}(ε_{1}(x_{1}), …, x_{R}, …, ε_{k}(x_{k})). But for the latter to have property (Hadas) is precisely what (sub)^{2}lemma 1.4.1 is saying. This completes the proof of (sub)^{2}lemma 1.4.1.

As we noted at the very beginning of the proof of sublemma 1.4, subsublemma 1.4.1, read from right to left, can be used repeatedly to ‘unbar’ x_{i}’s, until we get that

Res_{x_{π(1)},...,x_{π(k)}}[F_{n,k}(ε_{1}(x_{1}), …, ε_{k}(x_{k}))] = Res_{x_{π(1)},...,x_{π(k)}}[F_{n,k}(x_{1}, …, x_{k})] .  (SofT ov)

Since F_{n,k}(x_{1}, …, x_{k}) has a genuine Laurent expansion, crucial fact ℵ′_{4} reassures us that we can unscramble the order of residue-taking on the right side of (SofT ov):

Res_{x_{π(1)},...,x_{π(k)}}[F_{n,k}(x_{1}, …, x_{k})] = Res_{x_{1},...,x_{k}}[F_{n,k}(x_{1}, …, x_{k})] .  (HakolT ov)

Combining (SofT ov) with (HakolT ov) yields (1.4′), which we noted was equivalent to the statement of sublemma 1.4. This completes the proof of sublemma 1.4.

INTERACT, Part II

At this juncture, we have to introduce the rational function T_{k,n}(x) = T_{k,n}(x_{1}, …, x_{k}) defined by:

T_{k,n}(x) := ∏_{i=1}^{k} \frac{1}{(x̄_{i}x_{i})^{n+k+1}} ∏_{1≤i<j≤k} \frac{1}{(1 − x_{i}x_{j})(1 − x̄_{i}x_{j})(1 − x_{i}x̄_{j})(1 − x̄_{i}x̄_{j})} .

We can rewrite Sublemmas 1.1’ and 1.2’ more compactly as follows.

Sublemma 1.1” The total number of n × k-Magog trapezoids, b_{k}(n), is given by:

Res_{x_{1},...,x_{k}} [Δ_{k}(x) T_{k,n}(x) ∏_{i=1}^{k} x_{i}^{i+1} ∏_{1≤i<j≤k}(1 − x̄_{i}x_{j})(1 − x_{i}x̄_{j})(1 − x̄_{i}x̄_{j})]  . (MagogT otal′′)

Proof: .

Sublemma 1.2”: The total number of n × k− Gog trapezoids, m_{k}(n), is given by:

Res_{x_{1},...,x_{k}} [Φ_{k}(x)T_{k,n}(x) ∏_{i=1}^{k}(x̄_{i})^{k−i}x_{i}^{k} ∏_{1≤i<j≤k}(1 − x_{i}x̄_{j})(1 − x̄_{i}x̄_{j})]  ,  (GogT otal′′)

the electronic journal of combinatorics 3 (2) (1996), #R13 64

where Φ_{k}(x) = Φ_{k}(x_{1}, …, x_{k}) is the polynomial defined in (Gog_{1}). Proof: . Using sublemmas 1.3 and 1.4, and the fact that T_{k,n}(x) is symmetric while Δ_{k} and Φ_{k} are antisymmetric with respect to the action of the group of signed permutations W (B_{k}), we can average Sublemmas 1.1” and 1.2”, to get yet other residue expressions for the desired quantities b_{k}(n) and m_{k}(n), as follows. Sublemma 1.1”’: The total number of n × k-Magog trapezoids, b_{k}(n), is given by:

\frac{1}{2^{k}k!}Res_{x_{1},...,x_{k}} \{T_{k,n}(x) Δ_{k}(x) · ∑_{g∈W (B_{k})} sgn(g) · g [∏_{i=1}^{k} x_{i}^{i+1} ∏_{1≤i<j≤k}(1 − x̄_{i}x_{j})(1 − x_{i}x̄_{j})(1 − x̄_{i}x̄_{j})] \} .

(MagogT otal′′′)

Proof: . Sublemma 1.2”’: The total number of n × k-Gog trapezoids, m_{k}(n), is given by ,

\frac{(−1)^{k}}{2^{k}k!} Res_{x_{1},...,x_{k}} [T_{k,n}(x)Φ_{k}(x)^{2}] , (GogT otal′′′)

where Φ_{k}(x) = Φ_{k}(x_{1}, …, x_{k}) is the polynomial defined by (Gog_{1}), in the statement of sublemma 1.2. Proof: See the definition of Φ_{k}(x) given in (Gog_{1}) .

Act V. GOG=MAGOG

… Gog and Magog, to gather them together to battle: the number of whom is as the sand of the sea. —(Revelations XX,8)

We have one more sublemma to go, that asserts that not only are the iterated-residues expressing b_{k}(n) and m_{k}(n), as given in (MagogT otal′′′) and (GogT otal′′′) respectively, equal to each other, but the actual residue-ands are.

Sublemma 1.5: Let Φ_{k}(x) = Φ_{k}(x_{1}, …, x_{k}) and Δ_{k}(x) = Δ_{k}(x_{1}, …, x_{k}) be defined as above, i.e. by

Φ_{k}(x_{1}, …, x_{k}) := (−1)^{k} ∑_{g∈W (B_{k})} sgn(g) · g [∏_{i=1}^{k} x̄_{i}^{k−i}x_{i}^{k} ∏_{1≤i<j≤k}(1 − x_{i}x̄_{j})(1 − x̄_{i}x̄_{j})]  , (Gog_{1})

Δ_{k}(x_{1}, …, x_{k}) := ∏_{i=1}^{k}(1 − 2x_{i}) ∏_{1≤i<j≤k}(x_{j} − x_{i})(x_{j} + x_{i} − 1)  .  (Delta)

The following identity holds:

Δ_{k}(x_{1}, …, x_{k}) ∑_{g∈W (B_{k})} sgn(g)·g [∏_{i=1}^{k} x_{i}^{i+1} ∏_{1≤i<j≤k}(1 − \overline{x}_{i}x_{j})(1 − x_{i}\overline{x}_{j})(1 − \overline{x}_{i}\overline{x}_{j})] = (−1)^{k} Φ_{k}(x_{1}, …, x_{k})^{2} .

(Gog = Magog)

[ Type ‘S15(k):’ in ROBBINS, for specific k.]

Proof: Since Φ_{k}(x) is W (B_{k})-antisymmetric, it can be written as Φ_{k}(x) = Δ_{k}(x)Ω_{k}(x), for some polynomial Ω_{k}(x) = Ω_{k}(x_{1}, …, x_{k}) that is symmetric with respect to W (B_{k}). This means that Ω_{k}(x) is a symmetric polynomial in (x_{1}\overline{x}_{1}, …, x_{k}\overline{x}_{k}). Since the degree of Φ_{k}(x), viewed as a polynomial in x_{1}, is ≤ (2k − 1) + 2(k − 1), and that of Δ_{k}(x) is 1 + 2(k − 1), it follows that the degree of Ω_{k}(x), as a polynomial in x_{1} is ≤ 2k − 2, and hence as a polynomial in x_{1}\overline{x}_{1} is ≤ k − 1. Similarly, the left side of (Gog=Magog) can be written as (−1)^{k}Δ_{k}(x)^{2}L_{k}(x), for some polynomial L_{k}(x), that is symmetric in (x_{1}\overline{x}_{1}, …, x_{k}\overline{x}_{k}). The degree of L_{k}, as a polynomial in x_{1}, is ≤ (k + 1) + 3(k − 1) − (1 + 2(k − 1)) = 2k − 1, and hence its degree in x_{1}\overline{x}_{1} is ≤ k − 1. We have to prove that L_{k} − Ω_{k}^{2} is identically zero. Since L_{k} − Ω_{k}^{2} is a polynomial of degree ≤ 2k − 2 in x_{1}\overline{x}_{1}, it suffices to prove that it is zero at 2k − 1 distinct values of x_{1}\overline{x}_{1}. This will follow by induction on k from the following two subsublemmas.

Subsublemma 1.5.1: Let L_{k}(x) be the left side of (Gog=Magog) divided by Δ_{k}(x)^{2}. We have

L_{k}(x_{1}, …, x_{k})|_{x_{1}=x_{i}^{−1}} = (∏_{{j=2 \atop j≠i}}^{k} \frac{(1 − \overline{x}_{i}x_{j})(1 − \overline{x}_{i}\overline{x}_{j})}{x_{i}} )^{2} L_{k−2}(x_{2}, …, x̂_{i}, …, x_{k}) , (i = 2, …, k)

(1.5.1a)

L_{k}(x_{1}, …, x_{k})|_{x_{1}=\overline{x}_{i}^{−1}} = (∏_{{j=2 \atop j≠i}}^{k} \frac{(1 − x_{i}x_{j})(1 − x_{i}\overline{x}_{j})}{\overline{x}_{i}} )^{2} L_{k−2}(x_{2}, …, x̂_{i}, …, x_{k}) , (i = 2, …, k)

(1.5.1b)
L_{k}(x_{1}, …, x_{k})|_{x_{1}=0} = L_{k−1}(x_{2}, …, x_{k}) .  (1.5.1c)

[ Type ‘S151(k):’ in ROBBINS, for specific k.]

Proof: By definition, L_{k}(x) is the left side of (Gog=Magog) divided by Δ_{k}(x)^{2}. By using the definition (Delta) of Δ_{k}(x), as well as its W (B_{k})-antisymmetry, we get,

L_{k}(x_{1}, …, x_{k}) = ∑_{g∈W (B_{k})} g [∏_{i=1}^{k} \frac{x_{i}^{i+1}}{(1 − 2x_{i})} ∏_{1≤i<j≤k} \frac{(1 − \overline{x}_{i}x_{j})(1 − x_{i}\overline{x}_{j})(1 − \overline{x}_{i}\overline{x}_{j})}{(x_{j} − x_{i})(x_{j} + x_{i} − 1)}] =

∑_{ε∈\{+1,−1\}^{k}} ε \{ ∑_{π∈S_{k}} π [∏_{i=1}^{k} \frac{x_{i}^{i+1}}{(1 − 2x_{i})} ∏_{1≤i<j≤k} \frac{(1 − \overline{x}_{i}x_{j})(1 − x_{i}\overline{x}_{j})(1 − \overline{x}_{i}\overline{x}_{j})}{(x_{j} − x_{i})(x_{j} + x_{i} − 1)}]\} .

Since the argument of π is antisymmetric w.r.t. to S_{k}, except for ∏_{i=1}^{k} x_{i}^{i+1} = ∏_{i=1}^{k} x_{i}^{2} ∏_{i=1}^{k} x_{i}^{i−1}, it follows, by Vandermonde’s determinant identity (see “Crucial Facts”), that

L_{k}(x_{1}, …, x_{k}) = ∑_{ε∈\{+1,−1\}^{k}} ε \{∏_{i=1}^{k} \frac{x_{i}^{2}}{(1 − 2x_{i})} ∏_{1≤i<j≤k} \frac{(1 − \overline{x}_{i}x_{j})(1 − x_{i}\overline{x}_{j})(1 − \overline{x}_{i}\overline{x}_{j})}{(x_{j} + x_{i} − 1)}\} .

(1.5.1d)

To prove (1.5.1a) for i = 2, …, k, it suffices, by symmetry, to consider i = 2. This would also imply, by the symmetry x ↔ \overline{x}, built into W (B_{k}), that (1.5.1b) is true. So let’s plug in x_{1} = x_{2}^{−1} in (1.5.1d). The only way that ε[(1 − \overline{x}_{1}x_{2})(1 − x_{1}\overline{x}_{2})(1 − \overline{x}_{1}\overline{x}_{2})] cannot be zero then, is for ε_{1} and ε_{2} to be both +1. Hence the 2^{k}-summand sum (1.5.1d) shrinks to a 2^{k−2}-summand sum:

\frac{(x_{2}^{−1})^{2}}{(1 − 2x_{2}^{−1})} \frac{(x_{2})^{2}}{(1 − 2x_{2})} \frac{(1 − \overline{x_{2}^{−1}}x_{2})(1 − x_{2}^{−1}\overline{x}_{2})(1 − \overline{x_{2}^{−1}}\overline{x}_{2})}{x_{2} + x_{2}^{−1} − 1} ∑_{{ε∈\{+1,−1\}^{k} \atop ε_{1}=1,ε_{2}=1}} ε[∏_{j=3}^{k}(\frac{(1 − \overline{x_{2}^{−1}}x_{j})(1 − x_{2}^{−1}\overline{x}_{j})(1 − \overline{x_{2}^{−1}}\overline{x}_{j})}{x_{j} + x_{2}^{−1} − 1}·

\frac{(1 − \overline{x_{2}}x_{j})(1 − x_{2}\overline{x}_{j})(1 − \overline{x}_{2}\overline{x}_{j})}{x_{j} + x_{2} − 1}) ∏_{j=3}^{k} \frac{x_{j}^{2}}{1 − 2x_{j}} ∏_{3≤i<j≤k} \frac{(1 − \overline{x}_{i}x_{j})(1 − x_{i}\overline{x}_{j})(1 − \overline{x}_{i}\overline{x}_{j})}{(x_{j} + x_{i} − 1)}] . (1.5.1e)

We now need the following utterly trivial subsubsublemmas.

Subsubsublemma 1.5.1.1:

\frac{(1 − \overline{x_{2}^{−1}}t)(1 − x_{2}^{−1}\overline{t})(1 − \overline{x_{2}^{−1}}\overline{t})}{t + x_{2}^{−1} − 1} · \frac{(1 − \overline{x_{2}}t)(1 − x_{2}\overline{t})(1 − \overline{x}_{2}\overline{t})}{t + x_{2} − 1} = (\frac{(1 − \overline{x}_{2}\overline{t})(1 − \overline{x}_{2}t)}{x_{2}})^{2} .

(1.5.1.1)

the electronic journal of combinatorics 3 (2) (1996), #R13 67 [ Type ‘S1511():’ in ROBBINS, to get a rigorous proof.]

Proof: . Subsubsublemma 1.5.1.2:

\frac{(x_{2}^{−1})^{2}}{(1 − 2x_{2}^{−1})} \frac{(x_{2})^{2}}{(1 − 2x_{2})} \frac{(1 − \overline{x_{2}^{−1}}x_{2})(1 − x_{2}^{−1}\overline{x}_{2})(1 − \overline{x_{2}^{−1}}\overline{x}_{2})}{x_{2} + x_{2}^{−1} − 1} = 1  .  (1.5.1.2)

[ Type ‘S1512():’ in ROBBINS, to get a rigorous proof.]

Proof: . Substituting (1.5.1.1) and (1.5.1.2) into (1.5.1e) yields:

L_{k}(x_{2}^{−1}, x_{2}, x_{3}, …, x_{k}) = ∑_{{ε∈\{+1,−1\}^{k} \atop ε_{1}=1,ε_{2}=1}} ε[∏_{j=3}^{k} (\frac{(1 − \overline{x}_{2}\overline{x}_{j})(1 − \overline{x}_{2}x_{j})}{x_{2}})^{2} ·

∏_{j=3}^{k} \frac{x_{j}^{2}}{2x_{j} − 1} ∏_{3≤i<j≤k} \frac{(1 − \overline{x}_{i}x_{j})(1 − x_{i}\overline{x}_{j})(1 − \overline{x}_{i}\overline{x}_{j})}{(x_{j} + x_{i} − 1)}] = (∏_{j=3}^{k} \frac{(1 − \overline{x}_{2}\overline{x}_{j})(1 − \overline{x}_{2}x_{j})}{x_{2}} )^{2} L_{k−2}(x_{3}, …, x_{k}) .

(1.5.1f)

This completes the proof of (1.5.1a) and (1.5.1b). To prove (1.5.1c), note that when x_{1} = 0, the only non-zero summands of (1.5.1d) are those for which ε_{1} = −1. The 2^{k}-summand sum (1.5.1d) collapses then to a 2^{k−1}-summand sum as follows:

∑_{{ε∈\{+1,−1\}^{k} \atop ε_{1}=−1}} ε (∏_{i=2}^{k} \frac{x_{i}^{2}}{1 − 2x_{i}} ∏_{j=2}^{k} \frac{(1 − \overline{x}_{j})}{x_{j}} ∏_{2≤i<j≤k} \frac{(1 − \overline{x}_{i}x_{j})(1 − x_{i}\overline{x}_{j})(1 − \overline{x}_{i}\overline{x}_{j})}{(x_{j} + x_{i} − 1)}) = L_{k−1}(x_{2}, …, x_{k}) .

This completes the proof of subsublemma 1.5.1 . Subsublemma 1.5.2: Ω_{k}(x) := Φ_{k}(x)/Δ_{k}(x) (see (Gog_{1}) and (Delta), in the statement of sublemma 1.5 for definitions), satisfies

Ω_{k}(x_{1}, …, x_{k})|_{x_{1}=x_{i}^{−1}} = (∏_{{j=2 \atop j≠i}}^{k} \frac{(1 − \overline{x}_{i}x_{j})(1 − \overline{x}_{i}\overline{x}_{j})}{x_{i}} ) Ω_{k−2}(x_{2}, …, x̂_{i}, …, x_{k}) , (i = 2, …, k)

(1.5.2a)

Ω_{k}(x_{1}, …, x_{k})|_{x_{1}=\overline{x}_{i}^{−1}} = (∏_{{j=2 \atop j≠i}}^{k} \frac{(1 − x_{i}x_{j})(1 − x_{i}\overline{x}_{j})}{\overline{x}_{i}} ) Ω_{k−2}(x_{2}, …, x̂_{i}, …, x_{k}) , (i = 2, …, k)

(1.5.2b)

Ω_{k}(x_{1}, …, x_{k})|_{x_{1}=0} = Ω_{k−1}(x_{2}, …, x_{k})  .  (1.5.2c)

[ Type ‘S152(k):’ in ROBBINS, for specific k.]

Proof: By W (B_{k}) symmetry, it is enough to prove (1.5.2a) for x_{1} = x_{2}^{−1}, which also implies (1.5.2b). To wit, we have to prove that:

x_{2}^{k−2}Ω_{k}(x_{1}, …, x_{k})|_{x_{1}=x_{2}^{−1}} = (∏_{j=3}^{k} (1 − \overline{x}_{2}x_{j})(1 − \overline{x}_{2}\overline{x}_{j})) Ω_{k−2}(x_{3}, …, x_{k}) . (Dominique)

We now need:

Subsubsublemma 1.5.2.1: Let Ω_{k}(x) := Φ_{k}(x)/Δ_{k}(x) be as in the statement of subsublemma 1.5.2, then

Ω_{k}(x_{1}, …, x_{k})|_{x_{1}=x_{2}^{−1}}

is a Laurent polynomial in x_{2} of degree ≤ (k − 2) and of low-degree ≥ −(k − 2).

[The low-degree, in x, of a Laurent polynomial f(x) is the degree of f(x^{−1}).]

[ Type ‘S1521(k):’ in ROBBINS, for specific k.]

Proof: It is readily checked that Δ_{k}(x_{1}, …, x_{k})|_{x_{1}=x_{2}^{−1}} is a Laurent polynomial in x_{2} of degree (2k − 1) and low-degree −(2k − 1), the statement of the (sub)^{3}lemma is equivalent to the statement that Φ_{k}(x_{1}, …, x_{k})|_{x_{1}=x_{2}^{−1}} is a Laurent polynomial in x_{2} of degree ≤ 3k − 3 and low-degree ≥ −(3k − 3). We will prove that this is even true for each and every single term in the defining sum (Gog_{1}) of Φ_{k}. Let g = (π, ε) be a typical signed permutation. Let α := π^{−1}(1) and β := π^{−1}(2), so that π(α) = 1 and π(β) = 2. Without loss of generality we can assume that α < β, since in the opposite case we can exchange x_{1} and x_{2}. Let P OL(x̂_{1}, x̂_{2}) denote a polynomial in (x_{3}, …, x_{k}). Let z_{i} := ε_{i}(x_{i}) (i.e. z_{i} = x_{i} if ε_{i} = 1 and z_{i} = x̄_{i}(= 1 − x_{i}) if ε_{i} = −1.)

The typical term corresponding to g = (π, ε) in the definition (Gog_{1}) of Φ_{k} can be written as follows:

g [∏_{i=1}^{k} x̄_{i}^{k−i}x_{i}^{k} ∏_{1≤i<j≤k}(1 − x_{i}x̄_{j})(1 − x̄_{i}x̄_{j})] = ∏_{i=1}^{k} z̄_{π(i)}^{k−i}z_{π(i)}^{k} ∏_{1≤i<j≤k}(1 − z_{π(i)}z̄_{π(j)})(1 − z̄_{π(i)}z̄_{π(j)})

= P OL(x̂_{1}, x̂_{2})·(z̄_{1}^{k−α}z_{1}^{k})·(z̄_{2}^{k−β}z_{2}^{k})(1−z_{1}z̄_{2})(1−z̄_{1}z̄_{2}) ∏_{i=1}^{α−1}(1−z_{π(i)}z̄_{1})(1−z̄_{π(i)}z̄_{1}) ∏_{{j=α+1 \atop j≠β}}^{k}(1−z_{1}z̄_{π(j)})(1−z̄_{1}z̄_{π(j)})·

∏_{{i=1 \atop i≠α}}^{β−1}(1 − z_{π(i)}z̄_{2})(1 − z̄_{π(i)}z̄_{2}) ∏_{j=β+1}^{k}(1 − z_{2}z̄_{π(j)})(1 − z̄_{2}z̄_{π(j)}) .

If ε_{2} = −1, i.e. z_{2} = x̄_{2}, the above term must vanish when x_{1}x_{2} = 1, because of (1−z_{1}z̄_{2})(1−z̄_{1}z̄_{2}). So we can assume that ε_{2} = +1, and so z_{2} = x_{2}. We now distinguish two cases:

Case I: ε_{1} = +1, i.e. z_{1} = x_{1}, then the term is

P OL(x̂_{1}, x̂_{2})·(x̄_{1}^{k−α}x_{1}^{k})·(x̄_{2}^{k−β}x_{2}^{k})(1−x_{1}x̄_{2})(1−x̄_{1}x̄_{2}) ∏_{i=1}^{α−1}(1−z_{π(i)}x̄_{1})(1−z̄_{π(i)}x̄_{1}) ∏_{{j=α+1 \atop j≠β}}^{k}(1−x_{1}z̄_{π(j)})(1−x̄_{1}z̄_{π(j)})·

∏_{{i=1 \atop i≠α}}^{β−1}(1 − z_{π(i)}x̄_{2})(1 − z̄_{π(i)}x̄_{2}) ∏_{j=β+1}^{k}(1 − x_{2}z̄_{π(j)})(1 − x̄_{2}z̄_{π(j)}) .

Now plug in x_{1} = x_{2}^{−1}. The product of the four products above times (1 − x_{2}^{−1}x̄_{2})(1 − \overline{x_{2}^{−1}}x̄_{2}) ((1−x_{1}x̄_{2})(1−x̄_{1}x̄_{2}) evaluated at x_{1} = x_{2}^{−1}) is a Laurent polynomial in x_{2} of degree ≤ 2(k−2)+2 = 2k − 2 and low-degree ≥ −(2k − 2). On the other hand (1 − x_{2}^{−1})^{k−α}(1 − x_{2})^{k−β} has degree ≤ k − β ≤ k − 1 and low-degree ≥ −(k − α) ≥ −(k − 1). So the degree in x_{2} of the whole term is ≤ 2k − 2 + k − 1 ≤ 3k − 3, and its low-degree is ≥ −[(2k − 2) + k − 1] ≥ −(3k − 3). This completes case I of subsubsublemma 1.5.2.1.

Case II: ε_{1} = −1, i.e. z_{1} = x̄_{1}, then the term is

P OL(x̂_{1}, x̂_{2})·(x_{1}^{k−α}x̄_{1}^{k})·(x̄_{2}^{k−β}x_{2}^{k})(1−x̄_{1}x̄_{2})(1−x_{1}x̄_{2}) ∏_{i=1}^{α−1}(1−z_{π(i)}x_{1})(1−z̄_{π(i)}x_{1}) ∏_{{j=α+1 \atop j≠β}}^{k}(1−x̄_{1}z̄_{π(j)})(1−x_{1}z̄_{π(j)})·

∏_{{i=1 \atop i≠α}}^{β−1}(1 − z_{π(i)}x̄_{2})(1 − z̄_{π(i)}x̄_{2}) ∏_{j=β+1}^{k}(1 − x_{2}z̄_{π(j)})(1 − x̄_{2}z̄_{π(j)}) .

Plugging in x_{1} = x_{2}^{−1} above yields a Laurent polynomial in x_{2} of degree ≤ 2(k − 2) + 2 = 2k − 2 and low-degree ≥ −(2k − 2), times

(x_{1}^{k−α}x̄_{1}^{k}) · (x̄_{2}^{k−β}x_{2}^{k}) = (x_{1}x_{2})^{k−α}x̄_{1}^{k}x̄_{2}^{k−β}x_{2}^{α} = (1 − x_{2}^{−1})^{k}(1 − x_{2})^{k−β}x_{2}^{α} .

But (1−x_{2}^{−1})^{k}(1−x_{2})^{k−β}x_{2}^{α} has degree ≤ k −β +α ≤ k −1 and low-degree ≥ −(k −α) ≥ −(k −1). So the degree in x_{2} of the whole term is ≤ 2k − 2 + k − 1 ≤ 3k − 3, and its low-degree is ≥ −[(2k − 2) + k − 1] ≥ −(3k − 3). This completes the proof of subsubsublemma 1.5.2.1.

Going back to the proof of subsublemma 1.5.2, both sides of (Dominique) are polynomials of degree ≤ 2(k − 2) in \overline{x}_{2}. (By subsubsublemma 1.5.2.1, The left side is a polynomial in x_{2} of degree ≤ 2(k − 2), and hence also in x̄_{2}, since x_{2} = 1 − x̄_{2} .) The right side vanishes at the 2(k − 2) values \overline{x}_{2} = x_{j}^{−1}, \overline{x}_{2} = \overline{x}_{j}^{−1}, j = 3, …, k. The next subsubsublemma asserts that this is true as well for the left side of (Dominique).

Subsubsublemma 1.5.2.2: The left side of (Dominique),

x_{2}^{k−2}Ω_{k}(x_{1}, …, x_{k})|_{x_{1}=x_{2}^{−1}} ,

when viewed as a polynomial in x̄_{2}, vanishes at the 2(k − 2) values x̄_{2} = x_{j}^{−1}, x̄_{2} = x̄_{j}^{−1}, for j = 3, …, k.

[ Type ‘S1522(k):’ in ROBBINS, for specific k>2.]

Proof: By the W (B_{k})-symmetry of Ω_{k}(x_{1}, …, x_{k}), it suffices to prove that the left side of (Dominique) vanishes when x̄_{2} = x_{3}^{−1}. This is equivalent to proving that Ω_{k}(x_{1}, …, x_{k}) vanishes whenever both 1 − x_{1}x_{2} = 0 and 1 − x̄_{2}x_{3} = 0. Note that these two last conditions also imply that 1 − x̄_{1}x̄_{3} = 0. Since Δ_{k}(x) does not vanish there, it suffices to prove that Φ_{k}(x) vanishes when these relations hold. Putting z_{i} := ε_{i}(x_{i}), Φ_{k}(x_{1}, …, x_{k}) can be written as:

Φ_{k}(x_{1}, …, x_{k}) = (−1)^{k} ∑_{ε∈{−1,+1}^{k}} ∑_{π∈S_{k}} sgn(ε) sgn(π) ∏_{i=1}^{k} z̄_{π(i)}^{k−i}z_{π(i)}^{k} ∏_{1≤i<j≤k}(1−z_{π(i)}z̄_{π(j)})(1−z̄_{π(i)}z̄_{π(j)}) .

(Bruce)

We will prove that each and every term of (Bruce) vanishes when 1 − x_{1}x_{2} = 0 and 1 − x̄_{2}x_{3} = 0. We now split the sum in (Bruce) as follows:

∑_{ε∈\{−1,+1\}^{k}} ∑_{1≤α<β<γ≤k} ∑_{{π∈S_{k} \atop \{π(α),π(β),π(γ)\}=\{1,2,3\}}} sgn(ε) sgn(π) ∏_{i=1}^{k} z̄_{π(i)}^{k−i}z_{π(i)}^{k} ∏_{{1≤i<j≤k \atop i,j∉\{α,β,γ\}}}(1−z_{π(i)}z̄_{π(j)})(1−z̄_{π(i)}z̄_{π(j)})·

(1 − z_{π(α)}z̄_{π(β)})(1 − z̄_{π(α)}z̄_{π(β)})(1 − z_{π(α)}z̄_{π(γ)})(1 − z̄_{π(α)}z̄_{π(γ)})(1 − z_{π(β)}z̄_{π(γ)})(1 − z̄_{π(β)}z̄_{π(γ)}) . (Bruce′)

For each such term in (Bruce′), let σ ∈ S_{3} be defined by σ(1) = π(α), σ(2) = π(β), and σ(3) = π(γ). Also let ε′ be the first three components of ε: i.e. ε′(1) = ε(1), ε′(2) = ε(2) and ε′(3) = ε(3). The fact that each and every single term in (Bruce′) vanishes when 1 − x_{1}x_{2} = 0 and 1 − x̄_{2}x_{3} = 0 follows from the next (sub)^{4} lemma:

Subsubsubsublemma 1.5.2.2.1: For each signed permutation (σ, ε′) of W (B_{3}),

(σ, ε′)[(1 − x_{1}x̄_{2})(1 − x̄_{1}x̄_{2})(1 − x_{1}x̄_{3})(1 − x̄_{1}x̄_{3})(1 − x_{2}x̄_{3})(1 − x̄_{2}x̄_{3})]

vanishes when x_{3} = (x̄_{2})^{−1} and x_{1} = (x_{2})^{−1}.

[ Type ‘S15221():’ in ROBBINS, to get a rigorous proof.]

Proof: .

It follows that indeed each and every single term of (Bruce′) vanishes when x_{3} = (x̄_{2})^{−1} and x_{1} = (x_{2})^{−1}, and since (2^{k}k!) · 0 = 0, the whole thing vanishes as well. This completes the proof of subsubsublemma 1.5.2.2.

Going back to the proof of subsublemma 1.5.2, in order to complete the proof of (Dominique), we need to compare at one more value of x̄_{2}. The value to pick is x̄_{2} = 0, which implies x_{1} = x_{2} = 1. And, indeed Ω_{k}(1, 1, x_{3}, …, x_{k}) = Ω_{k−2}(x_{3}, …, x_{k}), as follows from (\overline{W alt}) in subsublemma 1.5.2.3 below, applied twice.

Since both sides of (Dominique) are polynomials of degree ≤ 2(k − 2) in x̄_{2}, that agree in 2k − 3 distinct values of x̄_{2}, they must be identically equal. This completes the proof of (Dominique) and hence of (1.5.2a − b).

the electronic journal of combinatorics 3 (2) (1996), #R13 71

By symmetry, the statement of (1.5.2c) is equivalent to (W alt) in the following subsubsublemma. Subsubsublemma 1.5.2.3: Ω_{k}(x) = Φ_{k}(x)/Δ_{k}(x) (k ≥ 1) satisfies:

Ω_{k}(x_{1}, …, x_{k−1}, 0) = Ω_{k−1}(x_{1}, …, x_{k−1}) .  (W alt)
Ω_{k}(x_{1}, …, x_{k−1}, 1) = Ω_{k−1}(x_{1}, …, x_{k−1}) .  (\overline{W alt})

[ Type ‘S1523(k):’ in ROBBINS, for specific k.]

Proof: By the W (B_{k})-symmetry of Ω_{k} it suffices to prove (W alt). When x_{k} = 0 all the summands, in the definition (Gog_{1}) of Φ_{k}(x), vanish except those coming from (π, ε) for which π(k) = k, ε_{k} = −1. Thus the sum reduces to a sum over W (B_{k−1}) that is easily seen to be equal to

\frac{Δ_{k}(x_{1}, …, x_{k−1}, 0)}{Δ_{k−1}(x_{1}, …, x_{k−1})}Φ_{k−1}(x_{1}, …, x_{k−1}) .

This completes the proof of subsubsublemma 1.5.2.3. This completes the proof of subsublemma 1.5.2 . . Combining subsublemmas 1.5.1 and 1.5.2, and using induction on k, we see that indeed L_{k}(x) = Ω_{k}(x)^{2}, for any k ≥ 2, since this is true for k = 0, 1. This completes the proof of sublemma 1.5. Combining Sublemmas 1.1”’, 1.2”’ , and 1.5 finishes the proof of Lemma 1. .

the electronic journal of combinatorics 3 (2) (1996), #R13 72

REFERENCES

[A1] G.E. Andrews, Plane Partitions III: the weak Macdonald conjecture , Invent. Math. 53(1979), 193-225.

[A2] G.E. Andrews, Plane Partitions V: the T.S.S.C.P.P conjecture , J. Combin. Theory Ser. A, 66(1994), 28-39.

[D] R.J. Duffin, Basic properties of discrete analytic functions, Duke Math. J. 23(1956), 335-363.

[G] I. Gessel, Tournaments and Vandermonde’s determinant , J. Graph Theory 3(1979), 305-307.

[Ma] I.G. Macdonald, SYMMETRIC FUNCTIONS AND HALL POLYNOMIALS , Oxford University Press, Oxford, 1979.

[MRR1] W.H. Mills, D.P. Robbins, and H.Rumsey, Proof of the Macdonald conjecture , Invent. Math. 66(1982), 73-87.

[MRR2] W.H. Mills, D.P. Robbins, and H.Rumsey, Alternating sign matrices and descending plane partitions, J. Combin. Theo. Ser. A, 34(1983), 340-359.

[MRR3] W.H. Mills, D.P. Robbins, and H.Rumsey, Self complementary totally symmetric plane partitions , J. Combin. Theory Ser. A 42(1986), 277-292.

[PS] G. Pólya and G. Szëgo, PROBLEMS AND THEOREMS IN ANALYSIS[1], Springer, 1976.

[R] D.P. Robbins, The story of 1, 2, 7, 42, 429, 7436, ... , Math. Intell v.13, #2(Spring 1991), 12-19.

[RR] D.P. Robbins and H. Rumsey, Jr., Determinants and alternating sign matrices, Advances in Mathematics 62(1986), 169-184.

[Stanl] R.P. Stanley A baker’s dozen of conjectures concerning plane partitions , in: COMBINA-TOIRE ENUMERATIVE, ed. by G. Labelle and P. Leroux, Lecture Notes in Mathematics 1234, Springer, Berlin, 1986.

[Stant] D. Stanton, Sign variations of the Macdonald identities, SIAM J. Math. Anal. 17(1986), 1454-1460.

[Ste] J. Stembridge, A short proof of Macdonald’s conjecture for the root system of type A, Proc. Amer. Math. Soc. 102(1988), 777-786.

[WZ] H.S. Wilf and D. Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math. 108(1992), 575-633.

[Z1] D. Zeilberger, The algebra of linear partial difference operators and its applications , SIAM J.

the electronic journal of combinatorics 3 (2) (1996), #R13 73

Math. Anal. 11(1980) , 919-934.

[Z2] D. Zeilberger Partial difference equations in m_{1} ≥ ... ≥ m_{n} ≥ 0 and their applications to combinatorics , Discrete Math 31(1980) , 65-77.

[Z3] D. Zeilberger, A constant term identity featuring the ubiquitous (and mysterious) Andrews-Mills-Robbins-Rumsey numbers {1, 2, 7, 42, 429, ...} , J. Combin. Theory Ser. A 66(1994), 17-27.

[Z4] D. Zeilberger, A unified approach to Macdonald’s root-system conjectures , SIAM J. Math. Anal. 19(1988), 987-1013.

[Z5] D. Zeilberger, A Stembridge-Stanton style proof of the Habsieger-Kadell q-Morris identity , Discrete Math. 79(1989/90) , 313-322.

[ZB] D. Zeilberger and D.M. Bressoud, A proof of Andrews’ q-Dyson conjecture , Discrete Math. 54(1985) , 201-224. Original Version: Kislev 5753; This Version: Nisan 5755.

the electronic journal of combinatorics 3 (2) (1996), #R13 74

EXODION The Skeleton of the Proof with Checkers’ Names

A person’s name after the appropriate (sub)^{i}lemma (0 ≤ i ≤ 6), means that she or he has checked that its proof is formally correct, provided that all the direct descendent-sublemmas are correct. They assume no responsibility whatsoever to the actual correctness of the offsprings of the (sub)^{i}lemma that they have been charged with, that lies solely with their subcheckers. 1 (G. Andrews, D. Foata, W. Johnson)

1.1 (N. Alon, H. Wilf)

1.1.1 (A. Björner) 1.1.1.1 (C. Orr) 1.1.1.2 (D. Bar-Natan)

1.1.1.2.1 (J. Noonan) 1.1.1.2.2 (J. Majewicz)

1.1.1.3 (S. Cooper)

1.1.2 (V. Kann) 1.1.3 (R. Stanley)

1.2 (X.Y. Sun)

1.2.1 (B. Salvy) 1.2.1.1 (D. Stanton) 1.2.1.2 (Anon., J. Legrange) 1.2.1.2.1 (N. Bergeron)

1.2.1.2.1.1 (R. Simion, R.J. Simpson) 1.2.1.2.1.1.1 (R. Howe, R. Graham) 1.2.1.2.1.1.2 (J. Borwein, D.E. Knuth)

1.2.1.2.2 (D. Robbins) 1.2.1.2.3 (L. Zhang)

the electronic journal of combinatorics 3 (2) (1996), #R13 75

1.2.1.2.3.1 (M. Bousquet-Mélou)

1.2.1.2.3.1.1 (L. Habsieger) (also requires 1.4.1.1)

1.2.1.2.4 (F. Brenti)

1.2.1.2.5 (L. Ehrenpreis, S.B. Ekhad, G. -C. Rota) 1.2.1.3 (F. Bergeron, M. Wachs)

1.3 (M. Knopp, S. Parnes)

1.3.1 (M. Knopp)

1.3.1.1 (R. Canfield)

1.3.1.1.1 (W. Chen) 1.3.1.2 (J. Noonan) 1.3.1.3 (K. Ding) 1.3.1.4 (P. Zimmermann)

Case I (C. Dunkl, R. Ehrenborg)

Subcase Ia (C. Dunkl)

Subcase Ib (C. Dunkl, K. Eriksson, R. Sulanke)

Case II (M. Werman)

1.4 (O. Foda)

1.4.1 (J. Haglund)

1.4.1.1 (M. Readdy, N. Takayama)

1.4.1.1.1 (A. Fraenkel, J. Labelle) (also requires section 1.5.2) 1.4.1.2 (J. Friedman) 1.4.1.3 (S. Okada, Chu W.) 1.4.1.4 (F. Garvan, G. Gasper)

Case I (V. Strehl)

Subcase Ia (A. Granville)

the electronic journal of combinatorics 3 (2) (1996), #R13 76

Subcase Ib (E. Grinberg)

Case II (G. Kalai, I. Sheftel) 1.4.1.4.1 (C. Krattenthaler)

1.4.1.4.1.1 (G. Labelle)

1.4.1.5 (G. Almkvist, D. Loeb, V. Strehl)

Case I (P. Leroux, V. Strehl)

Subcase Ia (E. Lewis, V. Strehl) Subcase Ib (D. Loeb, V. Strehl)

Case II (V. Strehl) 1.4.1.5.1 (G. Bhatnagar, S. Milne, V. Strehl)

1.4.1.6 (F. Garvan)

1.5 (R. Supper)

1.5.1 (Han G.-N., P. Paule, A. Ram) 1.5.1.1 (S. B. Ekhad, C. Zeilberger) 1.5.1.2 (S. B. Ekhad, T. Zeilberger)

1.5.2 (A. Regev, J. Remmel)

1.5.2.1 (C. Reutenauer, B. Reznick) Case I (B. Reznick) Case II (B. Reznick, C. Rousseau)

1.5.2.2 (B. Sagan)

1.5.2.2.1 (S.B. Ekhad, H. Zeilberger) 1.5.2.3 (W. Stromquist, X.G. Viennot)

The Checkers

The sublemmas checked by each of the checkers is given inside the square bracket at the end of each entry, where the periods were dropped. Thus [123456] would stand (if it existed) for 1.2.3.4.5.6. If the person also contributed general comments about the rest of the paper, this is indicated by ‘GC’. Persons who are only credited with ‘GC’ contributed important general comments, but did not check the formal correctness of any statement.

The following abbreviations were used: AcM:=‘Acta Math.’, AdM:=‘Advances in Math’, AMM:=‘Amer. Math. Monthly’, BAMS:=‘Bulletin of the Amer. Math. Soc’, CM:=‘Contemporary Math.’, CR:=‘Comptes Rendus’, DM:=‘Discrete Math.’, JCT(A):=‘J. of Comb. Theory (Ser. A)’, ICM:=‘Inter. Congress of Mathematicians’, JSC:=‘J. for Symbolic Comp.’, LNM:=‘Lecture Notes in Math’(Springer), MI:=‘Math. Intell.’, PNAS:=‘Proc. Nat. Acad. Sci.’, PAMS:=‘Proc. Amer. Math. Soc.’, Inv:=‘Inventionae Math.’, SB:=‘Seminaire Bourbaki’,. Sloane’s abbreviated citing scheme has been followed: [volume first page year].

Gert Almkvist, Lund, gert@maths.lth.se, is the ‘guy who generalized a mistake of Bourbaki’ (CM 143 609 93), which lead to important work in algebraic K-theory. Now he became a wizard in asymptotic number theory (CM 143 21 93). [1415]

Noga Alon, Tel-Aviv, noga@math.tau.ac.il , is one of the most powerful combinatorialists, graph-theorists, and complexity-ists in the world, who developed and applied innovative algebraic techniques. His many honors include ICM 90’, and being granted a permanent-member-size office when he was member of IAS in 93-94. [11]

George Andrews, Penn State, andrews@math.psu.edu, is the king of q-theory, who pioneered computer-assisted research that lead to astounding results in combinatorics, number theory, and physics (e.g. CBMS #66,AMS.) [1]

Richard Askey, Wisconsin, askey@math.wisc.edu, is the king of special functions, of Askey-Gasper inequality (AcM 154 137 85) and Askey-Wilson polynomials fame. [GC]

Dror Bar-Natan, Harvard, dror@math.harvard.edu, has done ground-breaking work in topological Quantum Field theory, and has a novel approach to Vassiliev invariants. His beautiful papers can be anonymously ftp-ed from math.harvard.edu, and once he moves to Jerusalem (Sept. 1995), from math.huji.ac.il. [1112]

Bernard Beauzamy, Paris VII and Inst. Calc. Math., beauzamy@mathp7.jussieu.fr , is a leading Banach spacer who has also made significant contributions to computer algebra (JSC 13 463 92.)[GC]

Francois Bergeron, UQAM, bergeron@catalan.math.uqam.ca, is a leading Species-ist who has also made beautiful work on card shuffling and the descent algebra. [1213]

Nantel Bergeron, Harvard, nantel@math.harvard.edu, contributed significantly to card-shuffling, knot theory (with Bar-Natan), the descent algebra, and Schubert polynomials.[12121]

Gaurav Bhatnagar, Ohio-State, gaurav@math.ohio-state.edu, is completing a deep and important thesis under Steve Milne. [14151]

Anders Björner, Stockholm, bjorner@math.kth.se, is a leading algebraic combinatorialist (e.g. ICM 86), who has applied the arcane Möbuius function to mundane, but important, computational complexity problems. [111]

Jonathan Borwein, Simon Fraser, jborwein@cecm.sfu.ca, The Borwein brothers showed the world (with the Chudnowsky brothers) that computing π to zillion digits involves very beautiful and deep mathematics. Their paper (with Dilcher) (AMM 100 274 93), according to Andrews(MI 16#4 16 94), is a prime example of why humans will never be replaceable by machines. [1212112]

Mireille Bousquest-Mélou, bousquet@labri.u-bordeaux.fr, has come a long way since she was the ‘first woman to have ever ranked first in the concourse to the ‘great’ schools of France.’ She has used Viennot’s heaps, as well as the DSV methodology, to find very deep, and elegant, results in polyomino-enumeration. (Publ. LACIM (UQAM), #8). [121231]

Francesco Brenti, Perugia and IAS, brenti@math.ias.edu, applied total positivity to prove deep combinatorial inequalities. Currently he is studying the Kazhdan-Lusztig polynomials from a combinatorial point of view. [12124]

David M. Bressoud, Macalister, dvb@math.psu.edu, is a leading q-ist (JNT 12 87 80) and combinatorialist(DM 38 313 82), who is also a master expositor(‘Second Year Calculus’, ‘Radical Calculus’.) [So far everything except for 13 and 14 and their descendents.]

E. Rodney Canfield, Georgia, erc@csun1.cs.uga.edu , disproved the Rota conjecture (AdM 29 1 79), and did many more things since, especially in asymptotic combinatorics. [1311]

William Chen, LANL, chen@monsoon.c3.lanl.gov , did breathtaking work on bijections(PNAS 87 9635 90), formal grammars, permutation statistics and many other things. [13111]

Chu Wenchang, Rome, wenchang@mat.uniroma1.it, has done beautiful work in systematizing and explaining combinatorial identities. [1413]

Shaun Cooper, Wisconsin, scooper@math.wisc.edu, is currently completing his thesis under Dick Askey, and has proved a conjecture of P. Forrester (DM, to appear.) [1113]

Kequan Ding, IAS and Illinois, ding@math.ias.edu has done beautiful work on the crossroads of combinatorics, geometry, and topology. His approach to the Rook polynomials is wonderful. [1313]

Charles Dunkl, Virginia, cfd5z@virginia.edu, is of ‘Dunkl operators’ fame, without which Cherednick would not have been able to prove Macdonald’s constant term conjecture. [1314, case I, and descendents]

Richard Ehrenborg, ehrenborg@mipsmath.math.uqam.ca, is both a great juggling mathematician and a great mathematical juggler.[1314, case I, and descendents]

Leon Ehrenpreis, Temple, leon@math.temple.edu, did work on partial differential equations that Halmos et. al. (AMM 83 503 76) consider to be one of the crowning achievements of American mathematics since 1940. He is listed by Dieudonné (‘Panorama of Pure Math’, p. 70,) along with Laplace, Fourier, and 13 others, as one of the originators of the general theory of linear partial differential equations. [12125,GC] Shalosh B. Ekhad, Temple, ekhad@math.temple.edu, has written more than fifteen papers, and intends to write many more. [12125,1511,1512,15221]

Kimmo Eriksson, KTH, kimmo@math.kth.se has done beautiful work on Coxeter groups, the Number game, and Fulton’s essential set. He is also a great speaker. [1314, subcase Ib]

Dominique Foata, Strasbourg, foata@math.u-strasbg.fr , has revolutionized combinatorics at least twice (LNM #85 and JCT(A) 24 250 78 (see also ICM 83)). The first time it also revolutionized theoretical computer science, and the second time it also revolutionized special functions. [1]

Omar Foda, Melbroune, foda@maths.mu.OZ.AU, is a leading mathematical physicist and quantum group-ist, who has proved far-reaching Rogers-Ramanujan-type identities.[14]

Aviezri Fraenkel, Weizmann Inst., MAFRAENKEL@WEIZMANN.WEIZMANN.AC.IL, has both Erdös number 1, and Einstein number 2 (via his advisor Ernst Strauss.) He is a leader in games, combinatorial number theory, complexity, and many other things. His uncle is Abraham H. of Zermelo-F. fame. [14111]

Jane Friedman, janef@teetot.acusd.edu, has made lasting contributions to Rogers-Ramanujan theory (Temple thesis, 90), to the generalized Odlyzko conjecture (PAMS 118 1013 93), and to lattice path counting. [1412]

Frank Garvan, Florida, frank@math.ufl.edu, cracked a 1944-conjecture of Dyson by cranking out a new ‘crank’ for partitions (Dyson, in: ‘Ramanujan Revisited’). He also did many other things, including the first proof of the F4-Macdonald root system conjecture (BAMS 24 343 91). [1416]

George Gasper, Northwestern, george@math.nwu.edu, is of the fame of the Askey-Gasper inequality and of the Gasper-Rahman classic on ‘Basic Hypergeometric Series’. He is the most serious candidate for proving an inequality that was shown by Jensen to imply RH. [1414]

Bill Gosper, Independent, rwg@NEWTON.macsyma.com, is a 20th-century Ramanujan. His Gosper algorithm (PNAS 75 40 78) changed summation theory for ever. [GC]

Ron Graham, Bell, rlg@research.att.com, (∈NAS), is present and former president of AMS and AJA resp. Both his technical contributions and charismatic personality (e.g. DLS II, Univ. Videos) has helped make combinatorics a house-hold name. [1212111]

Andrew Granville, Georgia, andrew@sophie.math.uga.edu , proved the Carmichael conjecture (with Pomerance)(ICM 94), need I say more? [1414, subcase Ia]

Eric Grinberg, Temple, grinberg@math.temple.edu , has done important work on the Radon transform, and on the Bussman-Petit problem. [1414, subcase Ib]

Laurent Habsieger, Bordeaux, habsieger@geocub.greco-prog.fr, proved, in his brilliant thesis, Askey’s conjectured extension of Selberg’s integral (also done by Kadell), and the G2 case of Macdonald’s constant term conjecture (CR 303 211 86), (also done by Zeilberger.) He has since diversified, and did beautiful work in number theory. Most recently he improved bounds in the notorious ‘football(soccer) pool’ problem. [1212311] Jim Haglund , Illinois (starting 8/95), until 8/95: jhaglund@kscmail.Kennesaw.edu, has written a brilliant thesis under Rodney Canfield, that contains lots of beautiful and deep results about rook polynomials, KOH-type identities, and the Simon Newcomb problem. Lately he is studying the combinatorics of the Riemann zeta function. [1414, case I]

Han Guo-Niu, Strasbourg, han@math.u-strasbg.fr , is the world’s greatest expert on the Denert statistics, and is a very powerful bijectionist and word-enumerator. [151]

Roger Howe, Yale, howe@math.yale.edu, (∈NAS), is not only one of the deepest and most influential Lie theorists of our day, but also a great lecturer and expositor (AMM 90 353 83 (L. Ford 84’ award.)) [1212111]

Warren Johnsnon, Penn State, johnson@math.psu.edu, has done deep and elegant work both on the q-Bell numbers and q-Abel identities. [1,GC]

Gil Kalai, Jerusalem, kalai@cs.huji.ac.il, revolutionized convexity and polytope theory with his ‘algebraic shifting’ (ICM 94). With Jeff Kahn, he finished off (negatively) the famous Borsuk problem (that resisted the attacks of at least one Fields-medalist). [1414, case II]

Viggo Kann, KTH, viggo@nada.kth.se, wrote a brilliant thesis on approximate algorithms. His computer, Sol Tre, is a co-author of S.B. Ekhad. [112]

Marvin Knopp, Temple, Never had e-mail (and never will), wrote the classic ‘Modular Functions’ (Chelsea), started the notion of ‘rational period function’ and developed a deep theory of Eichler cohomology. [13,131]

Don Knuth, Stanford, No more e-mail, (∈ NAS), is both the Diderot (Art of Comp. Prog.), and Gutenberg(TeX) of the computer age. He is the unique element of TURING ∩ HOPPER. [1212112,GC]

Christian Krattenthaler, Vienna, kratt@pap.univie.ac.at , is a Maestro in piano playing, lattice-path combinatorics, hypergeometric series, and computer algebra. [14141]

Gilbert Labelle,UQAM, gilbert@mipsmath.math.uqam.ca , of Species-fame, has the nicest proof ever, of the Largange inversion formula (AdM 42 217 81.) [141411]

Jacques Labelle,UQAM, jacques@mipsmath.math.uqam.ca , is a master chess player, species-ist and combinatorialist. [14111]

Jeff Lagarias, Bell, jcl@research.att.com , is not only a high-powered researcher in number theory, cryptology and complexity theory, but is also a master expositor (AMM 92 3 85, L. Ford award 86’), with a deep sense of history. With Shor he disproved a long-standing conjecture of Keller about tiling (BAMS 27 279 92). This leads me to believe that perhaps the Jacobian conjecture (also posed by Keller) is false as well, at least in high dimensions. [GC]

Jane Legrange, Bell, jdl@allwise.att.com , is a Member of Technical Staff in the Display Research Department, at AT&T Bell Labs, Murray Hill, NJ. Thanks to people like her, very soon we won’t need paper or printers. In 1992-1993, she was Visiting Associate Professor at Princeton University, as a recipient of the coveted VPW NSF grant.

She published extensively on liquid crystals and DNA, in numerous journals, including Physical Review Letters and Nature. [1212, GC]

Pierre Leroux, UQAM, leroux@mipsmath.math.uqam.ca, did beautiful work both on species and (with Viennot) on the combinatorics of differential equations. With Foata, he has met Askey’s challenge: to find a combinatorial proof to the generating function for Jacobi polynomials. (PAMS 87 47 83.) [1415, case I]

Ethan Lewis, Haverford, e1lewis@haverford.edu, proved a long-standing conjecture on infinite covering systems, and extended the Cartier-Foata method. [1415, subcase Ia]

Daniel Loeb, Bordeaux, labri@u-bordeaux.fr, has (in part with Rota) largely extended the scope of the Umbral Calculus, to include formal power series of logarithmic type. He is a master of ‘negative thinking’ and has started a new era in the umbral calculus [1415,subcase Ib]

John Majewicz, Temple, jmaj@math.temple.edu, is currently studying for his Ph.D. under D. Zeilberger. He has extended the WZ method to Abel-type sums. His papers can be anon. ftp-ed from ftp.math.temple.edu, directory pub/jmaj. [11121][11122]

Steve Milne, Ohio-State, milne@function.mps.ohio-state.edu, does extremely deep research in multivariate hypergeometric series. One of Gelfand’s dreams is to relate his geometro-combinatorial approach to hypergeometric functions with Milne’s (and Gustafson’s) work. [14151]

John Noonan, Temple, noonan@math.temple.edu, is currently studying for his Ph.D. under D. Zeilberger. He studies permutations that sin a prescribed number of times. His great programs and papers can be downloaded from

http://www.math.temple.edu/~  noonan. [11121]

Andrew Odlyzko, Bell, amo@research.att.com. Contrary to what Herb Wilf (and probably many others) used to believe, ODLYZKO is not a collective name (like Bourbaki) for a team of brilliant mathematicians, but consists of a singleton. His many contributions include work on small discriminants, the disproof of the Mertens conjecture, and vastly extending the empirical evidence for RH (ICM 86). [GC]

Kathy O’Hara, Independent (formerly Iowa),ohara@math.uiowa.edu, has astounded the combinatorial world with her injective proof of the unimodality of the Gaussian polynomials (AMM 96 590 89.) [1212111,GC]

Soichi Okada, Nagoya,okada@nagoya-u.ac.jp, is one of the world’s greatest determinant and pfaffian evaluators, and an all-around algebraic combinatorialist. [1413]

Craig Orr, Miami, craig@paris-gw.cs.miami.edu , has completed a brilliant thesis under D. Zeilberger. [1111]

Sheldon Parnes, Simon Fraser, sparnes@cecm.sfu.ca , completed last year a brilliant thesis under D. Zeilberger. [13]

Peter Paule, RISC-Linz, ppaule@risc.uni-linz.ac.at, is at the cutting edge between combinatorics and computer algebra. He contributed significantly to the Bailey chain, developed a general theory of summation, and found short and sweet computer proofs (much shorter then the original ones by Ekhad and Tre) of the Rogers-Ramanujan identities (ElJC 1 R10.) [151, 152, and their descendents]

Bob Proctor, North Carolina, rap@math.unc.edu, interfaces the combinatorics of tableaux with representation theory very elegantly. His beautiful exposition (AMM 89 721 82) of Stanley’s brilliant proof of the Erdös-Moser conjecture, stripped it of its inessential (and intimidating) high-brow components, and exposed its bare beauty for the rest of us to savor. [13111]

Arun Ram, Wisconsin, ram@math.wisc.edu, has a very healthy schizophrenia between combinatorics and representation theory, that helped both very much. He is also a brilliant lecturer. [151]

Marge Readdy, readdy@catalan.math.uqam.ca, is one of the most brilliant academic grandchildren of Richard Stanley. She is a very versatile posetist. [1411, GC]

Jeff Remmel, UCSD, jremmel@math.ucsd.edu , has done elegant and deep work on tableaux, permutations, and many other combinatorial objects. The Garsia-Remmel rook polynomials attracted great attention. [152]

Amitai Regev, Penn State and Weizmann Inst., regev@math.psu.edu, proved, in his thesis, that the tensor product of PI rings is yet another one. He is of ‘Regev theory’ fame (see Rowan’s book) that uses tableaux to study PI algebras. [152]

Christoph Reutenauer, UQAM, christo@catalan.math.uqam.ca , has a way with words and plays freely with Lie algebras. Read all about it in the proc. of FPSAC VI. [1521]

Bruce Reznick, Illinois, reznick@math.uiuc.edu, is one of the greatest 19th-century algebraists alive. By the periodicity of mathematical fashions, he is also a great 21st-century mathematician. Hilbert, would have loved his work. [1521]

Don Richards, Virginia, dsr2j@virginia.edu, is a leader on complex functions of matrix arguments. With Ken Gross, he is developing a deep theory of hypergeometric functions on complex matrix space (BAMS 24 349 91.) [GC]

Dave Robbins, IDA-CRD, robbins%idacrd@princeton.edu, is responsible (with WM and HR), to my spending (wasting(?)) a big chunk of my life proving (which was fun) and then debugging (which was no fun!) the ASM conjecture. Before coming up with his notorious conjectures, he proved his mettle by proving the ‘most interesting open problem in enumeration’ (Stanley): Macdonald’s formula for CSPPs (ref. [MRR1].) [12122]

Gian-Carlo Rota, MIT, rota@math.mit.edu, (∈ NAS), has laid the foundation to Combinatorial Theory (see ‘Classic Papers in Comb.’, ed. by Gessel and Rota.) [12125]

Cecil Rousseau, Memphis State, rousseau@hermes.msci.memst.edu is a great graph theorist and problem solver. He served as coach of the US math Olympic team for many years. [1521, case II]

Bruce Sagan, Michigan State, sagan@nsf1.mth.msu.edu , is a great bijectionist and master expositor (‘The symmetric group’). [1522] Bruno Salvy , INRIA, Bruno.Salvy@inria.fr , is pioneering the use of computer algebra for combinatorics and theoretical computer science. With Paul Zimermann, he has developed the versatile Maple package gfun for handling generating functions.[121]

Isabel Sheftel, Jerusalem, sheftel@cs.huji.ac.il, is writing a thesis under the direction of Gil Kalai. [1414, case II]

Rodica Simion, George Washington, simion@gwuvm.gwu.edu, has done very original and seminal work both on bijections, posets, enumeration, and (multi-q) theory. [121211]

R. Jamie Simpson, Curtin, TSIMPSONR@cc.curtin.edu.au, is one to the leaders in covering sequences. He had a beautiful (and hence elementary) proof (found independently by Berger, Felzenbaum, and Fraenkel) that the top moduli of an exact covering set must be equal. [121211]

Richard Stanley, MIT, rstan@math.mit.edu, is perhaps more responsible than anyone else to the creation of a new AMS classification (05E.) The totality of his influence is even more than the sum of its parts, which include having so many brilliant academic offsprings, some of whom are listed here. [113]

Dennis Stanton, Minnesota, stanton@s2.math.umn.edu , is equally comfortable with block designs (from a fancy, ‘algebraic’ point of view.), bijections (‘Constructive combinatorics’, with D. White), and hypergeometric analysis, to all of which he contributed deeply. Last but not least he is co-responsible for the ‘Stanton-Stembridge trick’. [1211]

Volker Strehl, strehl@immd1.informatik.uni-erlangen.de , has carried the Foata approach to special functions to breathtaking heights. His Habilitationschrift is a true classic, that I hope would be published as a book. [1414, case I; 1415 and its descendents]

Walt Stromquist, Wagner Assoc., 74730.2425@compuserve.com, was, for a few months in 1975, the holder of the record for the minimal number of countries needed for a planar map not to be four-colorable. He retains this title, to this day, amongst humans. Since then he did a lot of things, including instructions on how to divide a cake fairly. [1523]

Bob Sulanke, Boise State, sulanke@math.idbsu.edu, did beautiful and elegant work on the combinatorics of lattice paths. He is a master of elegant bijections. [1314, subcase Ib]

X.Y.Sun, Temple, xysun@math.temple.edu, hopes to start his dissertation work soon, under D. Zeilberger. He is a true Maple whiz. [12]

Sheila Sundaram, Miami, sheila@paris-gw.cs.miami.edu, is a leading symplectic tableau-ist and plethysm-ist. See FPSAC VI. [GC]

Raphaële Supper, Strasbourg, c/o avanissian@math.u-strasbg.fr, is a very promising young analyst, who has already contributed significantly to the theory of entire arithmetic functions (CR 312 781 91,) and to harmonic functions of exponential type. [15]

Nobuki Takayama, Kobe, taka@math.s.kobe-u.ac.jp, is one of the greatest Gröbner bases algorithmicians in the world, as applied to special functions. He developed the package KAN. [1411]

Xavier G. Viennot, Bordeaux, viennot@geocub.greco-prog.fr revolutionized combinatorial statistical physics (SB, Ex. # 626). His charismatic research and lecture-persona (‘Viennotique’= transparency wizardry,) helped make combinatorics mainstream, even in (formerly) snobbish France. He won a CNRS silver medal. [1523,GC]

Michelle Wachs, Miami, wachs@math.miami.edu , is a leading algebraic combinatorialist. She worked on posets, permutation statistics, and vastly extended the scope of shellabilty, that, according to Gil Kalai, should from now on be called michelle-ability. [1213]

Michael Werman, Jerusalem, werman@cs.huji.ac.il, is a master (mathematical-) imager (e.g. PRL 5 87 207). [1314, case II]

Herb Wilf, Penn, wilf@central.cis.upenn.edu, went through the three analyses: numerical, mathematical, and (happily ever after,) combinatorial. With Nijenhuis and Greene he designed the best mathematical proof ever. He was a pioneer in combinatorial algorithms, in particular for random selection and listings of combinatorial objects. (See CBMS #55, SIAM.) [11]

Celia Zeilberger, 71324.3565@compuserve.com, attends sixth grade at John Witherspoon Middle School, Princeton, NJ. [1511]

Hadas Zeilberger, 71324.3565@compuserve.com, attends ‘A-class’ at the U-NOW Day Nursery, Princeton, that is located on the same street (a couple of blocks away) from the residence of the (tentative) prover of FLT. [15221]

Tamar Zeilberger, 71324.3565@compuserve.com, attends third grade at Johnson Park Elementary School, Princeton, NJ. [1512]

Li Zhang, Temple, lzhang@math.temple.edu, is working towards his dissertation, under D. Zeilberger. He is a great Maple whiz. [12123]

Paul Zimmermann , INRIA, Paul.Zimmermann@inria.fr , is one of the pioneers in the use of computer alegbra for combinatorics and theoretical computer science. See also under Salvy.[1314]