Project Description

Summary of Results from Previous NSF Support: DMS-8901610 and DMS-9123836

1.The current NSF award number is DMS-9123836 for the period 1992-95, totaling roughly $61000/year .

2. Its title was: “Computer-Generated and Computer-Assisted Research in Combinatorics and Special Functions”

3. Summary of the results of the completed work.

(The numbered references apply to the list of papers written with the NSF support of the above grants, given at the end of this section. The lettered references are to papers given at the end of the section “Proposed Research”.)

The Alternating Sign Matrix Conjecture

I am especially proud of the proof of the alternating sign matrix conjecture[37]. This was one of the problems proposed in my previous proposal, and two of the reviewers criticized the problem as “too hard”.

The proof indeed turned out to be harder (or at least longer) than I first thought. The first version was distributed electronically in the early spring of 1993, and submitted to the J. of the AMS. A few months later the referees found some gaps. I am happy to announce that they have all been fixed. The new version was carefully checked by Dave Bressoud. The current version (as well as other current papers and software) is available via anonymous ftp to ftp.math.temple.edu (In

directories pub/zeilberger/papers and pub/zeilberger/programs.)

My other work can be roughly grouped as follows (the lists of papers following each heading is not disjoint, since some papers belong to more than one category.)

Computerized Proofs of Identities: ([2-6][8][9][15-17][19][21-23] [26][32][39].)

This work (in part joint with Herb Wilf) received considerable attention. It is the subject of a new section (the only change from the first edition) in the recently released second edition of Concrete Mathematics by Graham, Patashnik, and Knuth[GKP], and of a long expository article by Pierre Cartier[Ca] in the famous Bourbaki seminar. It is also covered in the chapter on asymptotic methods in combinatorics written by Andrew Odlyzko[O] for the “Handbook of Combinatorics” to be published by Van Nostrand.

Herb Wilf, Marko Petkovsek, and I, are currently writing a book on the subject that will also contain new material.

Maple programs implementing the algorithms for proving hypergeometric and other identities, as well as other programs of combinatorial interest, are available by anonymous ftp to the abovementioned site.

Enumerative and Algebraic Combinatorics:([1][7][13][14] [10][25][28][31][36][38][40].)

This work includes the ongoing collaboration with Dominique Foata([7][10][28][40]). Paper[7], on the new permutation statistics den introduced by Marleen Denert (and named by us), lead to interesting farther work, both by Foata’s student G.N.Han and by Dennis Stanton, Rodica Simion, Anne de Medicis, and G. Xavier Viennot[MV].

Paper [28] (that has the distinction of being the first paper to be published in the newly created Electronic J. of Combinatorics launched by Herb Wilf and on which both Foata and I serve of the editorial board,) gives a combinatorial proof of the Capelli and Turnbull identities, that complement the insightful representation-theoretic proofs of Howe[Ho]. We are still thinking how to extend our approach to the proof of the recent anti-symmetric analogs of Howe-Umeda-Kostand-Sahi([HoU],[KS]).

Paper [40] is the beginning of an attempted general theory of permutation statistics, which will form part of the present proposal.

Dominique Foata served as a consultant to the expired grant. It would be very helpful to retain him.

Constant Term Identities and related work:([20][25][26][27]) The methodology of constant term, using the seminal method of John Stembridge and Dennis Stanton[Ste][Sta][Zx], proved useful again. It would be intriguing to combine it with the WZ theory.

Combinatorial Number Theory:[11]. This was joint work with Jamie Simpson on Distinct Covering Sequences, trying to nibble at Erdos’s famous conjecture that none exists with all odd moduli. Using the elegant approach of Berger, Felzenbaum, and Fraenkel[BFF], we considerably improved the lower bound for the number of primes that should participate there.

Exposition:([18][19][21][23][34].) Paper [23], speculates on the future of mathematics,using the WZ proof theory as a parable. It arose some controversy (see George Andrews’ critiques [An1][An2] and Richard Askey[As1]’s Math Review of [23].)

General Hypergeometric Theory: In [12] I prove that Gauss’ classical evaluation of_{2}F_{1}(a, b; c; 1) cannot be extended to _{2}F_{1}(a, b; c; x). The method seems to have wider applicability.

None of the above:([29][30][35][39].) Paper[29] shows how a very important inequality due to Bombieri, follows from the classical Chu-Vandermonde binomial coefficient identity, via remarkable identities of Beauzamy and Degot[BG] and Bruce Reznick[Re].

4. List of Publications resulting from the NSF award.

1. A bijection from ordered trees to binary trees that sends the pruning order to the Strahler number, Discrete Math. 82, 89-92 (1990).

2. A Holonomic systems approach to special functions identities, J. of Computational and Applied Math. 32, 321-368 (1990).

3. (With Shalosh B. Ekhad) A 21^{st} century proof of Dougall’s hypergeometric identity, J. Math. Anal. Appl., 147 610-611 (1990). 4.A Fast Algorithm for proving terminating hypergeometric identities, Discrete Math 80, 207-211, (1990).

5. (With H. S. Wilf) Rational functions certify combinatorial identities, J. Amer. Math. Soc. 3, 147-158 (1990).

6. (With G. Almkvist) The method of differentiating under the integral sign, J. Symbolic Computation 10, 571-591 (1990).

7. (With D. Foata) Denert’s permutation statistic is indeed Euler-Mahonian, Studies in Applied Math 83, 31-59 (1990).

8. (With H. S. Wilf) Towards computerized proofs of identities, Bulletin of the Amer. Math. Soc. 23, 77-83 (1990).

9. The method of creative telescoping, J. Symbolic Computation 11, 195-204 (1991).

10. (With D. Foata) Multibasic Eulerian polynomials, Trans. Amer. Math. Soc. 328, 843-862 (1991).

11. (With R. J. Simpson) Necessary conditions for distinct covering systems with square-free moduli, Acta Arithmetica 59, 59-70 (1991).

12. Gauss’s _{2}F_{1}(1) cannot be generalized to _{2}F_{1}(x), J. Comp. Appl. Math. 39, 379-382 (1992).

13. (With I. Gessel) Random Walk in a Weyl chamber, Proc. Amer. Math. Soc. 115, 27-31 (1992).

14. A proof of Julian West’s conjecture that the number of 2-stack-sortable permutations of length n is 2(3n)!/((2n + 1)!(n + 1)!), Discrete Math. 102, 85-93 (1992).

15. (with H.S. Wilf) An algorithmic proof theory for hypergeometric (ordinary and ”q”) multisum/integral identities, Invent. Math. 108, 575-633 (1992).

16. (With H. S. Wilf) Rational function certification of hypergeometric multi-integral/sum/”q” identities, Bulletin of the Amer. Math. Soc. 27 148-153 (1992).

17. Closed Form (pun intended!), in: ”Special volume in memory of Emil Grosswald”, M. Knopp and M. Sheingorn, eds., Contemporary Mathematics 143 579-607, AMS, Providence (1993).

18. Gert Almkvist’s generalization of a mistake of Bourbaki, in:”Special volume in memory of Emil Grosswald”, M. Knopp, ed., Contemporary Mathematics 143 609-612, AMS, Providence (1993).

19. Three recitations on Holonomic Systems and Hypergeometric Series, Proceeding of the Séminaire Lotharingien de combinatoire 24,5-37, IRMA, Strasbourg. (1993) (To be reprinted in Journal Symbolic Computation.)

20. (With Jane Friedman) A generalization of Odlyzko’s conjecture: the coefficients of (1−q)^{j}/((1− q^{2n})...(1 − q^{2n+2j})) alternate in sign, Proc. Amer. Math. Soc. 118, 1013 (1993).

21. Identities in search of identity, J. The. Comp. Sci., 117, 23-38 (1993).

22. (With G.E. Andrews and S.B. Ekhad), A short proof of Jacobi’s formula for the number of representations of an integer as a sum of four squares, Amer. Math. Monthly, 100, 274-276 (1993).

23. Theorems for a price: Tomorrow’s semi-rigorous mathematical culture, Notices of the Amer. Math. Soc. 40 # 8, 978-981 (Oct. 1993). [Reprinted in Math. Intell. 16 # 4, 11-14 (Fall 1994).]

24. On an identity of Daubechies, Amer. Math. Monthly 100, 487 (1993).

25. A constant term identity featuring the ubiquitous (and mysterious) Andrews-Mills-Robbins-Rumsey numbers {1, 2, 7, 42, 429, ...}, J. Combinatorial Theory (ser. A) 66, 17-27(1994).

26. Towards a WZ proof of Mehta’s integral, SIAM J. Math. Anal. 25 , 812-814 (1994).

27.Proof of q-analog of a constant term identity conjectured by Forrester, J. Combinatorial Theory 66 311-312 (1994).

28. (With D. Foata) Combinatorial Proofs of Cappelli’s and Turnbull’s Identities from Classical Invariant Theory, Electronic J. of Combinatorics, 1, Research paper 1 (1994). [For the Mosaic(WWW) and Gopher addresses of the El.J.C. one may finger Herb Wilf at wilf@central.cis.upenn.edu.]

29. Chu’s 1303 identity implies Bombieri’s 1990 norm-inequality [Via an identity of Beauzamy and Dégot], Amer. Math. Monthly, 101 ,xxx-xxx (Nov. 1994).

30. (With L. Ehrenpreis) Two EZ proofs of sin^{2} z + cos^{2} z = 1, Amer Math. Monthly 101, 691 (1994).

31.(with Jane Friedman and Ira Gessel) Talmudic lattice path counting, J. Comb. Theory (Ser. A), to appear.

32. (with Shalosh B. Ekhad) A short and elementary, “formal calculus” proof of the Bieberbach conjecture (after L. Weinstein), Contemporary Math xxx , to appear.

34. How Joe Gillis discovered Combinatorial Special Function Theory, Math. Intell., to appear.

35. (with C.Orr), A computer algebra approach to the discrete Dirichlet problem, J. Symbolic Computation, to appear.

36. Self avoiding walks, the language of science, and Fibonacci numbers, J. Stat. Planning and Inference (Special issue dedicated to Lattice Path combinatorics, proceedings, India 1994’, S.G. Mohanty, editor), to appear.

37. Proof of the alternating sign matrix conjecture, accepted for publication in J. Amer. Math. Soc. subject to revision and filling in the details of the minor gaps. [The current version was carefully checked, and approved, by Dave Bressoud. It is available by anon. ftp to ftp.math.temple.edu

as file zeilberger/pub/papers/asm.tex.]

38. A combinatorist’s view of the lace expansion, in preparation. (Based on a talk given in the Combinatorics Seminar of the Inst. for Advanced Study, Nov. 1993.)

39. A rigorous foundation to semi-rigorous combinatorics, in preperation. (Based on an invited talk given in the 3rd Ann Arbor conference on algebra and combinatorics, June 1994.)

40. (with Dominique Foata)The graphical major index, in preparetion.

5. In addition to Maple programs for proving identities, I have developed a Maple package, SCHÜTZENBERGER, for handling formal power series and other combinatorial objects. It is also vailable by anon. ftp to ftp.math.temple.edu.

6. A large part of the proposed research is a direct continuation of the previous research, but there are also new directions, in which the commection is less obvious.

7. Education and Human Resources Statement.

My first Ph.D. student, Sheldon Parnes, graduated in the summer of 1993, and is currently a postdoctoral fellow at the Institute of Computational Mathematics directed by the Borwein brothers, in Simon Fraser University.

My second Ph.D. student, Ethan Lewis, finished in the spring of 1994, from the neighboring University of Pennsylvania. He is currently a visiting lecturer at Haverford college.

My third Ph.D. student, Craig Orr, finished in the fall of 1994, and is currently visiting lecturer at the University of Miami.

All these three theses combined experimental mathematics with more theoretical investigations and used computer algebra heavily.

Currently I have 3 Ph.D. candidates under my supervision: Li Zhang, John Noonan, and John Majewicz.

My recently expired grant supported a graduate student. It would be nice to be able to retain it, so that each of these students can get one year off from TAing, in order to free them to dedicate more time to the current project. My research, to be described in the next section, has reached a stage in which it is very ‘labor intensive’, and having graduate-student time should be very important both to the success of the project, as well as for the professional development of my students.

I am the local expert on computer algebra. In the last five years I have been teaching both graduate and undergraduate courses that were very well attended, in using Maple and Mathematica to do research in mathematics. Since most of the graduate students that attend my classes are also teaching assistants, this know-how gets transmitted to the undergraduates.

Paper [36] above was studied in a workshop for gifted high-school students conducted at MIT by Satomi Okazaki, and one of the the students is currently working on using the method for solving related problems, and plans to submit it to the Westinghaus competition.

PROPOSED RESEARCH: COMBINATORICS, SPECIAL FUNCTIONS, and COMPUTER ALGEBRA

My research area could be called Manipulatorics. Aptly coined by Adriano Garsia, this is that part of mathematics that is concerned with concrete manipulations of (in my case mostly combinatorial) objects. This swing-of-the-pendulum back from Bourbaki-style excessive abstraction was greatly inspired by computers and computer algebra, and is a fastly growing area. On the other hand, mathematics without any abstraction is an oxymoron, so good Manipulatorics should give new blood and nutrition to abstract mathematics, which in turn, feeds back ideas into concrete mathematics.

General Outlook

Mathematicians, even pure ones, are finally starting to appreciate the great power and versatility of the computer, not only in communicating mathematics, but also in creating it. In addition to the obvious use in collecting data for the formulation of conjectures, there is the possibility of computers proving theorems, given the right algorithms. The so-called WZ theory, mentioned in the previous section, will be probably joined by algorithmic proof theories for many other branches of mathematics. One such ‘proof theory’ goes back to Rene Descartes and his ‘analytical geometry’, which has gotten a new twist with computer algebra and Gröbner bases, thanks to which it is now possible to prove most theorems in plane (and, in principle, any fixed-dimensional) Geometry.

The greatest advances will be made by combining the 3 aspects of research as I see it: ‘Experimental’ exploration, analogous to experimental science, in which one designs carefully planned experiments, that are of course guided by theory. ‘Theoretical’, roughly paralleling theoretical physics, in which one proposes ways to make sense out of the raw data, and finally, ‘Mathematical’, in which one insists on complete rigor.

In this proposal, these three aspects are intertwined together, but their relative concentration vary from problem to problem. I will now list the problems that I hope to make progress on.

A General Theory Of Permutation Statistics

The study of permutations is very ancient, and was pursued in diverse cultures. For example, the Hebrew Book of Creation, Sefer Yetsira, that tradition attributes to the patriarch Abraham, and that was compiled c. 300 AD, lists the number of permutations of n objects for 2 ≤ n ≤ 7. The general formula,n!, and its, completely rigorous, inductive proof, can be found in “The book of Number” written in the 14th century by Gersonides (Rabbi Levi Ben Gerson , acronymed “Ralbag”).

The more refined counting of permutations, according to various statistics, was probably started by Netto, and reached a climax with the monumental work of MacMahon. In more recent times, it was taken up by Foata and Schützenberger. It was Foata who coined the name ‘statistics’ in this context, as well as the name ‘major index’. It is nowadays a flourishing part of enumerative and algebraic combinatorics, with major contributions coming from: Anders Björner, Jennifer Galovich, Adriano Garsia, Kevin Kadell, Don Rawlings, Jeff Remmel, Bruce Sagan, Richard Stanley, Dennis Stanton, Dennis White, Michelle Wachs, Xavier (Gérard) Viennot and many others.

One interesting generalization, pursued successfully by Björner and Wachs[BW], was to extend the classical definition of ‘inv’, ‘maj’, ‘des’ etc. from permutations to general partially ordered sets. In the generalization that Foata and I have in mind, we keep the classical structures of permutations and words, and instead generalize the ‘statistics’ themselves.

More specificlly, Dominique Foata and I plan to work on a general theory of permutation statistics that would be analogous to going from specific functions (like cos(x), e^{x}, x^{2}) to general analysis on functions. We would like to understand what makes the classical statistics ‘special’. For example, what are the conditions, for two different permutation statistics to be equidistributed, i.e. possess the same generating function? (like ‘inv”, the number of inversions, and the so-called major index, ‘maj’.) Under what conditions is the generating function

F_{n}(q) := ∑_{π∈S_{n}} q^{stat(π)} ,

a) Closed form? (like in the case of inv and maj); b)‘q-P-recursive’ (q-holonomic)? (i.e. F_{n}(q) satisfies a linear recurrence equation with coefficients that are polynomials in (q, q^{n}). c) When is the global exponential generating function ∑_{n=0}^{∞} \frac{F_{n}(q)z^{n}}{n!} nice?, like in the case of ‘des’ (when one gets the Eulerian polynomials, who are not ‘nice‘ by themselves, but which possess a nice generating function.)

What can one say about joint-distributions:

F_{n}(q_{1}, …, q_{k}) := ∑_{π∈S_{n}} q_{1}^{stat_{1}(π)} … q_{k}^{stat_{k}(π)} ?

Can one explain such ‘coincidences’ like the equi-distribution of the pair (‘des’, ‘maj’) with that of (‘exc’, ‘den’) first proved by Foata and I in paper[7] above, and since given a beautiful bijective proof by Han Gue-Nu[Han]. Perhaps there is a more global reason?

The recent beautiful work of Jennifer Galovich an Dennis White on generalized mahonian statistics should also be useful to the present research.

The classical permutation statistics all concern ‘pairs’. For example, the number of inversions, ‘inv’, is the number of pairs (i, j), with i < j such that π(i) > π(j). It would be interesting to explore properties of the analog to ‘triples’ and general k−tuples. The resulting new sequences F_{n}(q), all ‘analogs’ of the sequence {n!}, should also be useful in serving as candidates for yet-to-be-discovered classes of functions and sequences that would generalize the q−holonomic paradigm. One such statistics, that in fact inspired the present generalization, arose naturally in string theory, in Doron Gepner‘s[Gep] work. We would like to understand this better. To sum up, we have:

Research problem 1: Develop a general theory of permutation statistics, and classify the ones that have ‘nice’ properties.

Algorithmic Proof Theory for Special Functions and Combinatorial Summation

I would like to continue the work on ‘mechanical summation’ and ‘mechanical definite-integration’([2-6][8][9][15-17][19][21-23][26][32][39]) in two directions. The first one is in improving the current algorithms to be able to do larger problems. The second, more interesting, direction is to find increasingly larger and more general ‘paradigms’, in which one can successfully develop an algorithmic proof theory.

Curing the Andrews Syndrome

In [Anx], and more dramatically, in several invited conference talks^{†} George Andrews found some naturally occurring identities whose proof turned out to be beyond the present power of my Maple programs, running on the currently available computers. The main problem seemed to be the memory allocation, since the polynomials that arose were gargantuan.

I propose to improve my algorithm so that Andrews’ challenge problems (that arose naturally in his research, and were not artificially tailored to challenge my algorithm), and hopefully others as well, that will arise in the future, would be doable in ‘real time’ (and more importantly, in ‘real space’). The key would probably be to adapt the subroutine that uses the modified Gosper algorithm so that it would be able to handle polynomials in better ‘date structures’ then the obvious, expanded one.

What I mean by this is as follows. Take for example p(n) := \binom{n}{1000}. If you expand it, you would get a polynomial of degree 1000, with huge integer coefficients. But a much better way to describe it would be by saying that it has degree 1000 and to give its values at 0 through 1000. (Namely p(0) = … = p(999)=0,and p(1000) = 1.) I hope that the algorithm of [9] could be modified to handle polynomials in this far more economic data structure (for the present purpose.) This brings us to:

† For example, the Ann Arbor 3rd conference on algebra and combinatorics (June 1994), and the Garsia conference

(late July. 1994) held in Taoramina, Sicily) where George Andrews rolled out on the floor twelve transparencies, taped together, containing the hairy output of my computer program, applied to a (special case!) of the identity he was trying to prove.

Research Problem II: Improve the algorithm for mechanical summation, and its Maple implementation, so that they could handle Andrews’ challenge identities with currently available technology.

As far as the other, more general direction, there are still many identities that do not fall under what I call the holonomic paradigm. Recently, I realized that some identities that are not ‘holonomic’ can be nevertheless be handled by the holonomic approach. Take for example Abel’s identity (e.g. [PGK]):

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

The summand F (n, k) is neither holonomic in n nor in k, and the right side is not holonomic either. But (abel − sp) is really a specialization of

∑_{k=0}^{n} \binom{n}{k}(tk + 1)^{k−1}(t(n − k) + 1)^{n−k} = (tn + 2)^{n} .  (Abel − ge)

Now, the summand F (n, k, t) is not holonomic w.r.t. to n, but is holonomic w.r.t. (the discrete variable )k and (the continuous variable)t. Considering n as a parameter, the holonomic theory promises us that the left side a(t) := ∑_{k} F (n, k, t) should be holonomic in t, i.e. satisfy a certain linear differential equation with polynomial coefficients P (n, t, D_{t})a(t) = 0. The proof is then completed by matching the appropriate ‘initial values’, at t = 0 (for which the identity reduces to the binomial theorem (1 + 1)^{n} = 2^{n}. )

Thus even identities that are conspicuously non-holonomic may be doable, because they are specializations of ‘quasi-holonomic’ identities, with just enough variables to make things work. I would like to make these vague remarks more precise and more general.

It would also be interesting to find generalizations to bi-basic (and multi-basic) equations, as well as ‘dilation-translation’ equations, important in wavelets [DL]. This brings us to:

Research Problem 3: Extend the algorithmic proof theory for hypergeometric and holonomic functions and sequences to more general, yet to be discovered realms of functions.

Refined enumeration of alternating sign matrices I have already mentioned, in the report on work done under my previous grants, that I have succeeded in proving the Mills-Robbins-Rumsey conjecture about the number of alternating sign matrices.

An alternating sign matrix is a square matrix whose entries are drawn from the set {−1, 0, 1}, whose row-sums and column-sums all add up to 1, and in which, in each row and each column, the non-zero entries alternate in sign. Mills, Robbins, and Rumsey[MRR] (see also [Sta]) alternating sign matrix conjecture stated that the number of n × n alternating sign matrices is given by the formula:

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

There many related problems that are still open ([Ro][Sta]). The most pressing is the refined formula, for the number of n × n ASMs whose first row has its (necessarily only) 1 in the r^{th} column. This was “#3” in Stanley’s [Stanl] ‘baker’s dozen’.

Calling this number A(n, r) , Mills, Robbins, and Rumsey, conjectured that

A(n, r) = \binom{2n − 2}{n − 1}^{−1}\binom{n + r − 2}{n − 1}\binom{2n − r − 1}{n − 1}A_{n−1} .

My proof in [37] is indirect. Constant term expressions were derived for both the number of ASMs and the number of so-called totally symmetric self-complementary plane partitions (TSSCPP) for which Andrews[An1] has recently proved are also enumerated by A_{n} above, confirming another conjecture of [MRR] (“#2” in Stanley’s ‘baker’s dozen’). Then I prove that the two constant term expressions are the same.

It would be interesting if the constant term expression for the number of n × k ‘Gog Trapezoids’ (that reduce to n × n ASMs when n = k), that I derived in [37] :

CT [\frac{Λ_{k}(x_{1}, …, x_{k})}{x_{1}^{n}x_{2}^{n} … x_{k}^{n}} × ∏_{i=1}^{k}(x̄_{i})^{−n−1−i} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})^{−1}(1 − x̄_{i}x_{j})^{−1}] ,

where Λ_{k}(x_{1}, …, x_{k}) is the polynomial defined in (Gog_{1}).

Λ_{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})] ,

could be used to prove the formula, A_{n}, directly, perhaps by using the multi-variate WZ methodology of [15]. Combined with the equality result proved in [37], this would give a new proof of Andrews’[Anx] TSSCPP result. More importantly, this method should work equally well, for the refined enumeration, of n × n ASMs whose first row has its sole ‘1’ in the r^{th} column. The work in [37] easily implies the following constant term expression for this number:

CT [\frac{Λ_{n}(x_{1}, …, x_{n})}{x_{1}^{n}x_{2}^{n} … x_{n−1}^{n}x_{n}^{r}} × ∏_{i=1}^{n−1}(x̄_{i})^{−n−1−i}(x̄_{n})^{2n} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})^{−1}(1 − x̄_{i}x_{j})^{−1}] .

It may well be that this, more general, problem, might be easier, since we have two parameters, n and r for a possible induction argument.

The method of [37] seem to me to be suitable for studying the symmetry classes of ASMs ([Ro][Stanl]), and perhaps even, when q-analogized, the q-enumeration of the one remaining symmetry class for plane partitions, posed in [Stanley], that of totally symmetric plane partitions. The case q=1 has been recently settled, in a brilliant way, by John Stembridge[Stem], using Pfaffians and the powerful method of Gessel and Viennot[GV]. Thus:

Research Problem IV: Use the method of [37] to prove the refined ASM conjecture, its symmetryclasses analogs, and the q-enumeration of TSPPs.