 
%begin macros 
\def\Tilde{\char126\relax}
\baselineskip=14pt
\parskip=10pt
\def\epsilon{\varepsilon}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
\def\RightHead{\centerline{NSF Proposal: Symbolic Computation and 
Combinatorics}}
\def\LeftHead{ \centerline{Doron Zeilberger}}
\def\P{{\cal P}} 
%end macros
\centerline{\bf NSF PROPOSAL: SYMBOLIC COMPUTATION and
COMBINATORICS}
 
\centerline{ \it Doron Zeilberger}
 
Department of Mathematics, Temple University, Philadelphia, PA 19122;
{\tt zeilberg@math.temple.edu}  
{\tt http://www.math.temple.edu/\Tilde zeilberg} .
\bigskip 
\centerline{\bf Project Summary}
\centerline{ \bf SYMBOLIC COMPUTATION and COMBINATORICS} 
 
Doron Zeilberger proposes to continue to develop
methodologies for harnessing the great potential of
Symbolic Computation to do research in Combinatorics and
related areas. In particular he hopes to introduce new
computational and conceptual frameworks that would extend
the so-called Wilf-Zeilberger proof theory to much wider classes
of identities and theorems. He also proposes to continue his
efforts in `Artificial Combinatorics', and develop algorithms
for the discovery and {\it rigorous} proof of theorems in
combinatorics whose complexity make them unfeasible for human proofs.
This research should be symbiotic, as it is
expected that both the concrete results and 
the underlying methodologies, would help computer algebra developers
to improve and enhance their systems.
 
 
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\bigskip\bigskip\bigskip\bigskip\bigskip
 
{\bf Note}: Previous grants of Zeilberger were supported by the
Algebra and Number Theory program, with split-funding from
Computational Mathematics
and Numeric and Symbolic Computations (Computer Science). The present proposal
may also be considered for such split-funding. 
 
\vfill\eject
 
{\bf Summary of Results from Previous NSF Support:DMS-9500646 and DMS-9732602}
 
{\bf 1.} The current NSF award number is DMS-9732602
for the period 1997-2000, totaling \$180,000 .
 
{\bf 2.} Its title was: ``{\it Targeted Proof Machines in Combinatorics}''.
 
{\bf 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 section 4.
The lettered references are to papers given at the end of the section
``Proposed Research''.)
 
Symbolic Computation played a larger and larger role in my research efforts.
First, several interesting extensions of WZ theory 
(that was recognized by the award of the 1998 Steele prize
for research to Herb Wilf and myself) were made, mostly in
collaboration with my students Tewodros Amdberhan and
Akalu Tefera, both of whom were supported at various times by
this and the previous NSF grant. Tewodros Amdeberhan and I
investigated applications of WZ theory to  irrationality proofs,
convergence-acceleration formulas, and determinant evaluation. Akalu Tefera
developed a very powerful Maple package {\bf MultInt} that
implements the {\it continuous} WZ theory for an {\it arbitrary}
number of variables. Using this package, Tefera found a
very interesting {\it new} Selberg-like  integral formula for
{\it several} variables.
 
Computer Algebra was also crucial in the design of the
very complicated proof of the
{\it Alternating Sign Matrix Conjecture}([7]), and in that
of the proof of the {\it Refined Alternating Sign Matrix Conjecture}([4]),
where the punch-line was supplied by the Maple package EKHAD.
Both of these proofs are beautifully described (along with
background material and Kuperberg's beautiful simpler proof of
the (unrefined, original) ASM conjecture) in Dave Bressoud's
recent book [Br], that won the MAA Bekenbach Book Prize.
A nice shorter account was written by Bressoud and Jim Propp ([BP]).
 
My student Aaron Robertson, who was also supported by this grant
for one year, and I, proved a conjecture of Ron Graham about
Schur triples ([20]), thereby sharing (with T. Schoen)
the prize of \$100 that Graham offered. Once again, 
computer algebra (the Maple
package {\tt RON}) was very important for designing the proof.
 
My computer, Shalosh B. Ekhad, and I, improved the lower bound
for the asymptotics of the number of ternary square-free words
([18]). Together we also proved a conjecture of 
Alexander Kirillov ([8]). Using WZ theory, Shalosh([22]) proved
a conjecture of Scott Ahlgren and Ken Ono, that was needed to
finish up a deep conjecture of Frits Beukers ([AO]).
 
With Dominique Foata, who served as a consultant to this grant,
we published several papers in pure combinatorics ([5][10][29][35]).
We are especially proud of [29], where a generalization of 
Hyman Bass's
theorem is proved that was subsequently used by Lin and Wang ([LW])
in Knot Theory.
 
Shalosh B. Ekhad and I used clever programming and about two weeks
of computer time to prove the long-lost `Cosmological Theorem',
about the celebrated {\bf 1,11,21,1211,111221, ...} sequence,
supposedly proved, but lost, by Conway ([13]). Because of the
length and complexity of the computer proof, it is unlikely that
the lost (human) `proof' was complete. Also of the same flavor
is the automation of 
the three-rowed case of David Gale's game of {\it Chomp} ([34]).
 
Other attempts at `artificial combinatorics' are
[17], that automatically finds {\it enumeration schemes}
for enumerating so-called Wilf classes, and [26] that
automatically counts {\it Lego towers}, or more prosaically,
generalized {\it vertically convex} polyominoes.
In [27] and [33] the very powerful {\it Goulden-Jackson
method} is extended and implemented. 
 
In [28], a `futuristic' Geometry textbook is given. It is
now incorporated in the much larger, and continuously
evolving Maple package {\tt RENE}, available from 
the proposer's website.
 
In [24], a conjecture of Robbins and Chan was proved.
Alex Postnikov and Richard Stanley ([PS]) found interesting
ramifications in algebraic combinatorics.
 
In [30] we give algorithms for finding {\it generating functions}
for enumerating lattice animals, and self-avoiding polygons and
walks of restricted {\it width} (both globally and locally).
 
But the work that I believe to be the most significant,
and whose further development constitutes a large part of
my planned research to be described below, is
the {\it Umbral Transfer-Matrix method} ([32]).
It combines Gian-Carlo Rota's seminal notion of {\it umbra}
with the Transfer-Matrix method, to produce
{\it functional} equations, as opposed to mere
{\it algebraic} equations.
 
\eject
{\bf 4. List of Publications resulting from the NSF awards
in 1996-2000}
   
{\bf 1996}
  
1.{\it Counting permutations with a prescribed number of forbidden patterns}
(with John Noonan), Advances in Applied Mathematics  {\bf 17}, 381-407.
   
2. {\it Self-Avoiding Walks, the language of science, and Fibonacci numbers},
J. Stat. Planning and Inference {\bf 54}, 135-138.
   
3. {\it Reverend Charles to the aid of Major Percy and Fields-medalist 
Enrico},    Amer. Math. Monthly {\bf 103}, 501-502.
   
4. {\it Proof of the refined alternating sign matrix conjecture},
New York J. of Mathematics  {\bf 2}, 59-68.
   
5. (With D. Foata),
{\it The graphical major index},
J. Comput. Applied Math (special issue on q-series)
{\bf 68}, 79-101.
   
6. {\it The method of undetermined generalization and specialization
   illustrated with Fred Galvin's amazing proof of the Dinitz conjecture},
Amer. Math. Monthly {\bf 103}, 233-239.
   
7.  {\it Proof of the alternating sign matrix conjecture},
Elec. J. Comb. {\bf 3(2)}, R13.
   
8. (With S. B. Ekhad)
{\it An explicit formula for the number of solutions of $X^2=0$ in triangular
   matrices over GF(q)}, Elec. J. Comb. {\bf 3}  R2.
 
{\bf 1997}
  
9. (With A. Regev)
{\it Proof of a Conjecture about Multisets of Hook Numbers},
Annals of Combinatorics {\bf 1}, 391-394.
   
10. (With D. Foata)
{\it A classic proof of a recurrence for a very classical sequence},
J. Comb. Theor.-Ser. A. {\bf 80}, 380-384.
   
11. (With C. Krattenthaler)
{\it Proof of a Determinant Evaluation Conjectured by Bombieri, Hunt, and
   van der Poorten}, New York J. of Math. {\bf 3}, 54-102.
   
12. {\it The Abstract Lace Expansion}, Adv. Appl. Math.
   {\bf 19}, 355-359.
   
13. (With S. B. Ekhad)
{\it Proof of Conway's Lost Cosmological Theorem}
Elect. Res. Announcements of the AMS {\bf 3}, 78-82.
   
14. {\it A comparison of two methods for random labellings of balls by vectors
   of integers} in: ``Advances in Combinatorial
   Methods and Applications to Probability and Statistics'', N.
   Balakrishnan, ed., Birkhauser, 1997 (Mohanty Festschrift).
   
15.{\it Dodgson's Determinant-Evaluation Rule Proved by TWO-TIMING MEN and
   WOMEN} Elect. J. of Combinatorics
   {\bf 4(2)}, [Wilf Festschrift volume], R22.
   
16. (With Tewodros   Amdeberhan)
{\it Hypergeometric Series Acceleration via the WZ method},
Elect. J. of Combinatorics {\bf 4(2)}, [Wilf Festschrift volume], R3.
 
   
{\bf  1998}
  
17. {\it Enumeration Schemes, and More Importantly, Their Automatic
   Generation}, Annals of Combinatorics {\bf 2}, 185-195.
   
18. (With S. B. Ekhad)
{\it There Are More Than 2**(n/17) n-Lettered Ternary Square-Free Words},
J. Integer Sequences {\bf 98.1.9}.
   
19. (With S. B. Ekhad)
{\it Curing the Andrews Syndrome},
J. of Difference Equations and Applications {\bf 4}, 299-310.
   
20. (With A. Robertson)
{\it A 2-Coloring of [1,N] Can Have $(1/22)N^2+O(N)$ Monochromatic Schur
Triples, But Not Less!},   Electronic Journal of Combinatorics {\bf 5}, R19.
   
21. (With T. Amdeberhan)
{\it q-Apery Irrationality Proofs by q-WZ Pairs},
Adv. Appl. Math. {\bf 20}, 275-283.
   
22. (With Scott Ahlgren, Shalosh B. Ekhad, and Ken Ono)
{\it A Binomial Coefficient Identity Associated to a Conjecture of Beukers},
Electronic Journal of Combinatorics {\bf 5}, R10.
   
23. {\it How Much Should a Nineteenth-Century French Bastard Inherit},
J. Difference Eq. Appl. {\bf 3}, 385-388. (Special issue
   in honor of Gerry Ladas.)
 
{\bf 1999}
  
24. {\it Proof Of A Conjecture Of Chan, Robbins, and Yuen},
Elec. Trans, of Numerical Analysis {\bf 9}, 147-148.
   
25. (With A. Robertson and H. Wilf)
{\it Permutation Patterns and Continued Fractions},
Elec. J. Combinatorics {\bf 6}, R38.
   
26. {\it Automated Counting of LEGO Towers},
J. Difference Eq. Appl. {\bf 5}, 323-333.
   
27. (With J. Noonan)
{\it The Goulden-Jackson Cluster Method: Extensions, Applications, and
Implementations},   Difference Eq. Appl. {\bf 5}, 355-377.
   
28. (With S. B. Ekhad)
{\it PLANE GEOMETRY: An Elementary School Textbook (ca. 2050)},
Mathematical Intelligencer {\bf 21(3)}, 64-70.
   
29. (With D. Foata)
{\it Combinatorial Proofs of Bass's Evaluations of the Ihara-Selberg Zeta
   function of a Graph},
Trans. Amer. Math. Soc. {\bf 351}, 2257--2274.
   
 
{\bf  2000}
  
30. {\it Symbol-Crunching with the Transfer-Matrix Method in Order to Count
   Skinny Physical Creatures}, INTEGERS, {\bf 0}, A9 .
   
31. {\it How Berger, Felzenbaum, and Fraenkel Revolutionized COVERING SYSTEMS
   The Same Way that George Boole Revolutionized LOGIC}, 
to appear in Elect. J. Combinatorics (special issue in
   honor of Aviezri Fraenkel).
   
32. {\it The Umbral Transfer-Matrix Method: I. Foundations},
to appear in J. Comb. Theory, Ser. A, Rota memorial issue.
 
33. (With A. Edlin) {\it The Goulden-Jacskon Cluster Method For Cyclic Words},
Advances in Applied Mathematics {\bf 25}, 228-232.
      
34. {\it Three-Rowed CHOMP}, to appear in Adv. Appl. Math.
 
35. {\it Babson and Streingrimsson's permutation statistics
are indeed Mahonian, (and sometimes even Euler-Mahonian)},
submitted.
 
{\bf 5.} Many of my papers are accompanied by Maple packages
that are available, free of charge, from my homepage
{\tt http://www.math.temple.edu/\Tilde zeilberg/}.
In addition, there are quite a few packages that
belong to forthcoming papers, or stand by themselves.
Some of them are of a rather general scope, and should
be useful to researchers in combinatorics, number theory,
analysis, statistical physics, and possibly other areas.
 
{\bf 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 connection is less obvious.
 
{\bf 7. Education and Human Resources Statement.}
 
In 1997, my Ph.D. students John Majewicz, Tewodros Amdeberhan,
and John Noonan finished. Amdeberhan and Noonan were each supported
for one year in the penultimate grant.
John Majewicz has accepted an Associate Professorship
at the Community College of Philadelphia. John Noonan is
Assistant Professor at Mount Vernon Nazarene College, Ohio,
and Tewodros Amdeberhan declined an offer for a postdoc
at Penn-State in favor of a tenure-track appointment at
deVry Inst. of Tech., NJ. He is currently associate professor there.
 
All these theses combined experimental mathematics with
more theoretical investigations and used computer algebra heavily.
 
Last year (spring 1999), Aaron Robertson and Melkamu Zeleke,
who were each supported for one year by
this grant, graduated. Aaron accepted a tenure-track appointment
at Colgate University. I am very pleased that he is continuing to
do very deep research, both computational and theoretical,
in Ramsey theory. Melkamu is currently tenure-track
assistant professor at William Patterson University.
Melkamu is collaborating very nicely with colleagues in
bijective combinatorics.
 
This year (spring 2000) Akalu Tefera and Anne Edlin received
their Ph.D. under my direction.
Akalu just started a tenure-track assistant professorship
at Grand Valley State University ( in Michigan), and
Anne is assistant professor at Holy Family College (New Jersey).
As I mentioned above Akalu developed sophisticated software for
the continuous WZ method. Anne extended 
and implemented the Goulden-Jackson method to cyclic words.
 
Right now I only have one student, Mohamud Mohammed, who is
very strong and promising. I also have several other strong
prospective students.
The research conducted by my students involves large-scale
computing that should yield software
of wide interest and applicability to
the mathematical community. I am hence requesting student
support, on the level of one student,
that would be split between my students, and would free them
from some teaching obligations.
 
I am the local expert on computer algebra. Since 1988, 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 [2] above was studied in a workshop for gifted high-school
students conducted at MIT by Satomi Okazaki, and one of the students,
Lauren Williams (currently a Sophomore at Harvard), used its method
to write a paper (that later appeared in the Elec. J. Combinatorics),
that won third prize in the 
1996 International Science Fair. Lauren is currently a senior
at Harvard and plans to specialize in combinatorics.
\vfill
\eject 
\centerline{\bf PROPOSED RESEARCH: SYMBOLIC COMPUTATION and COMBINATORICS}
 
{\bf Introduction}
 
While the so-called {\it Wilf-Zeilberger (WZ) proof theory} and 
the {\it holonomic} paradigm, that has been successfully
implemented in all the major computer algebra systems,
and are widely used by mathematicians and scientists, can handle
a rather {\it wide} class of summations and integrations,
I feel that it is still but the {\it tip of an iceberg}.
In this proposal, I will describe my plans to extend
WZ theory to {\it sums and integrals with arbitrarily many
summation and integration signs}, like the celebrated
Selberg and Mehta integrals and the Macdonald-Dyson constant
term identities for the infinite families of root systems. I also hope
to go far beyond the {\it holonomic paradigm}, trying
to find wider and wider computationally decidable {ansatzes}.
 
I also hope to continue to do `Artificial Combinatorics'.
Here one looks at a class of combinatorial problems,
for example that of enumerating so-called Wilf classes,
and tries to {\it teach the computer} how to do research,
by formalizing methods and tricks used, usually implicitly,
in human research, and programing them. Once the computer
`learned' how to perform these `tricks' it can go much
further, of course.
 
In addition, I also hope to continue my work on a general
theory of permutation statistics, in collaboration with Dominique Foata.
 
{\bf WZ Theory: Chapter II}
 
Recall the ([WZ])
 
{\bf Fundamental Theorem of Multi-WZ Theory (Discrete Version)}
 
`Whenever' we want to prove an identity of the form:
$$
\sum_{k_1}\dots  \sum_{k_r} NICE(n; k_1, \dots , k_r) \equiv 1 \quad,
$$
There exist $NICE'_1, NICE'_2, \dots, NICE'_r$ such that
$$
\Delta_n NICE = \sum_{i=1}^{r} \Delta_{k_i} NICE'_i \quad
$$
Furthermore, $R_i:=NICE'_i/NICE$, ($i=1, \dots, r$),
are rational functions of $(n; k_1, \dots , k_r)$.
 
We also have the :
 
{\bf Fundamental Theorem of Multi-WZ Theory (Continuous Version)}
 
`Whenever' we want to prove an identity of the form:
$$
\int \dots \int NICE(n; x_1, \dots, x_r) \,\, dx_1 \dots dx_r \equiv 1 \quad,
$$
there exist $NICE'_i(n; x_1, \dots, x_r)$ ($i=1, \dots, r$), such that
$$
\Delta_n NICE = \sum_{i=1}^{r} {{\partial} \over {\partial x_i}} NICE'_i
\quad .
$$
Furthermore, $R_i:=NICE'_i/NICE$ are rational functions of
$(n; x_1, \dots, x_r)$.
 
Note that the mere existence of  $NICE'_i$
(or equivalently the $R_i$), together with
the trivially verifiable case $n=0$, implies the identity, 
since,
$$
\Delta_n \int \dots \int NICE \,=\,
\int \dots \int \Delta_n NICE \,=\,
\sum_{i=1}^{r} \int \dots \int {{\partial} \over {\partial x_i}} \{ NICE'_i\}
=0 \quad ,
$$
(because the $NICE'_i$ are of compact support).
 
Two famous examples are
$$
\int_{0}^{1} \dots \int_{0}^{1} \prod_{i=1}^{r} t_i^x (1-t_i)^y
\prod_{1 \leq i < j \leq r} (t_i-t_j)^{2z} dt_1 \dots dt_r
$$
$$
=\prod_{j=1}^{r}
{{(x+(j-1)z)!(y+(j-1)z)!(jz)!}
\over
{(x+y+(r+j-2)z+1)!z!}} \quad .
\eqno(Selberg)
$$
and
$$
\int_{|z_1|=1} \dots \int_{|z_r|=1}  
\{\prod_{1 \leq i \neq j \leq r} (1- z_i/z_j)^a \} {{dz_1} \over {z_1}}
\dots {{dz_r} \over {z_r}} ={{(ra)!} \over {a!^r}} \quad .
\eqno(Dyson)
$$
[This identity has a good pedigree. It was conjectured
in 1960 by Dyson, and proved a year later by
Gunson, and by Ken Wilson of Nobel (Renormalization Group) fame.
The `book' proof was given, in 1970, by the great
statistician I.J. Good.]
 
At present, using the multi-WZ method, Shalosh B. Ekhad can prove
$(Selberg)$,$(Dyson)$ (and any other such multi-dimensional identity),
for each {\it specific} number of variables $r$.
In practice, Shalosh can do it for $r=1,2,3,4$. It did.
Then the humans (in this case, myself and Wilf), looked at Shalosh's
proof, detected a common pattern, and it was a trivial,
albeit human, step, to formulate a WZ proof for
a general $r$ (see [WZ]  for a proof of $(Selberg)$).
 
But, right now, we still need this human factor. 
 
Another famous example is the Macdonald constant term
conjecture
(that Ian Macdonald talked about in his plenary talk,
at ICM 1998). Right now, Shalosh can do it (in principle) for each
specific root system, but it takes a human of the
caliber of Cerednick to do it for {\it all root systems}.
 
It would be nice to be able to {\it automatically} prove such
Selberg-type integrals for {\it arbitrary} dimension, keeping
the dimension $n$ as a symbol.  
For that
one would have to define precisely the notion of {\it hypergeometric
function} (what I called `nice') of $r$ variables, where
$r$ is not {\it merely} a symbol {\it denoting} an integer,
but is a {\it symbol} period. Prototype nice functions
should be:
$$
\left ( \sum_{i=1}^{r} n_i \right )!
$$
$$
\prod_{i=1}^{r} NICE(n_i)
$$
and, probably
$$
\prod_{i=1}^{r-1} NICE(n_i+n_{i-1}) \quad ,
$$
$$
\prod_{1 \leq i < j \leq r} NICE(n_i+n_j) \quad ,
$$
where $NICE$ is a nice function of a single discrete variable.
 
The `language' should contain, as primitive symbols,
$\prod$ and $\sum$, that would have to be incorporated into
the algorithm.
 
We also need a notion of `global' niceness for
$NICE'_1 , \dots ,  NICE'_r$, i.e., it does not suffice
that $NICE'_i$ would be nice in its arguments,
but we should insist that $NICE_i'$, when
also viewed as a function of its {\it subscript}
$i$, is nice, in a sense yet to be made precise.
Somehow, we should also bring in symmetry.
 
So hopefully, if this plan succeeds,
Macdonald's constant term identities, the Mehta integral,
the Selberg integral, and their kin,
would be fully automated.
 
{\bf Beyond the Holonomic Paradigm}
 
Recall that a continuous function of {\it one} variable
$f(x)$ is {\it holonomic} (a.k.a. D-finite) if it satisfies a
homogeneous linear differential equation with 
{\it polynomial} coefficients. For functions of several variables
one insists on equations on each variable.
While this class includes all polynomials and functions of
hypergeometric type, and hence most of the classical functions
of mathematical physics, it is still a rather {\it special} class.
 
It should be interesting to explore larger classes that would also
carry their own {\it proof theory}. One obvious choice would be
solutions of differential equations with {\it holonomic} coefficients,
that one could call {\it super holonomic}. The simplest such
function is $e^{e^x}$. However, preliminary investigations show that
a richer theory can be obtained by considering the narrower class
of solutions of differential equations with {\it algebraic} coefficients.
 
Another interesting problem would be to extend WZ theory to
{\it multibasic} sums, i.e. q-hypergeometric sums with several bases.
\vfill\eject
{\bf Enumeration Schemes}
 
Suppose that we have to find a `formula' (in the sense of Wilf,
i.e. a polynomial-time algorithm) for computing $a_n:=\vert A_n\vert$,
where $A_n$ is an infinite family of finite sets, parameterized
by $n$. Usually $A_n$ is a natural subset of a larger set
$B_n$, and is defined as the set of members of $B_n$ that
satisfy a certain set of conditions $C_n$. For example
if $A_n$ is the set of permutations on $\{1,2, \dots , n\}$,
then $B_n$ may be taken as the set of words of length
$n$ over the alphabet $\{1,2, \dots , n\}$, and $C_n$ can
be taken as the condition: `no letter can appear twice'.
A naive algorithm for enumerating $A_n$ would be to
actually {\it construct} the set, by examining the
members of $B_n$, one by one, checking whether they
satisfy $C_n$, and admitting those that qualify.
Then $a_n$=Cardinality of $A_n$.
 
But a much better approach would be to find a
{\it structure} theorem that expresses $A_n$, using unions,
Cartesian products, and possibly complements, of well known sets.
Failing this, it would be also nice to express $A_n$,
recursively, in terms of $A_{n-1}, A_{n-2}, \dots $, and easy-to-count
sets, getting a {\it recurrence formula}. Going back to the
permutation example, Levi Ben Gerson proved the structure
theorem $A_n \equiv \{1,2, \dots , n\} \times A_{n-1}$, from which
he deduced the {\it recurrence} $a_n=n a_{n-1}$, enabling a
polynomial-(in fact linear-) time algorithm for computing
$a_i$, for $1 \leq i \leq n$.
 
Alas, this is not always easy, and for many enumeration sequences,
e.g. the number of self-avoiding walks, may well be
{\it impossible}, and who knows, perhaps one day even
{\it provably impossible}.
 
It is conceivable, however, that a combinatorial family
$A(n)$, does not possess a recursive structure by itself, but by
{\it refining it}, using a suitable parameter, one can partition
$A(n)$ into the disjoint union:
$$
A(n)= \bigcup_{i=1}^{n} B(n,i) \quad, 
$$
and try and find a {\it structure theorem} for the two-parameter
family $B(n,i)$. This will imply a recurrence for the
cardinalities $b(n,i):=\vert B(n,i) \vert$, that would enable
a fast algorithm for $a(n)=\sum_{i=1}^{n} b(n,i)$.
 
Sometimes, not even the $B(n,i)$ suffice. Then we could try to
partition $B(n,i)$ into the following disjoint union:
$$
B(n,i)= \bigcup_{j=1}^{i-1} C_1(n,i,j) \cup \bigcup_{j=i+1}^{n} 
C_2(n,i,j)  \quad,
$$
and try to express $C_1(n,i,j)$ and $C_2(n,i,j)$ in terms of
$A(m)$, $B(m,i')$, $C_1(m,i',j')$, and $C_2(m,i',j')$, with
$m<n$. One can keep going {\it indefinitely}.
If this process {\it halts} after a finite number
of refinements, then we have indeed a {\it formula} (in the
sense of Wilf) for $a(n)$. 
 
In [17] I showed how to enumerate Wilf classes, but the
`success rate' was only about 20 percents. I propose to refine
and enhance the notion of {\it enumeration schemes} to make the
success rate closer to 100 percents. I also hope to use the
same circle of ideas in enumerating {\it words},
special kinds of {\it graphs}, and other combinatorial families.
 
{\bf The Umbral Transfer-Matrix Method}
 
The Finite Transfer-Matrix method is used to weight-enumerate
paths on a {\it finite} digraph, see [30] for a detailed exposition.
Here, we will be considering directed graphs whose
set of vertices, $V$, is {\it infinite},
with possibly multiple edges. Even though
there are infinitely many vertices, we will assume that they
can be partitioned into a finite union of {\it vertex-families},
$\{ v_1, \dots, v_n \}$, such that each family $v_i$ is
an $l_i$-parameter infinite family, parameterized by the
$l_i$ discrete variables $(a_1, \dots , a_{l_i})$,
where $(a_1, \dots , a_{l_i})$ ranges over a well-defined
subset $D_i$ of $\{0, 1,2,3, \dots\}^{l_i}$.
So the vertex set of our infinite digraph can be partitioned as follows
$$
V=\bigcup_{i=1}^n 
\bigcup_{(a_1, \dots, a_{l_i}) \in D_i }
v_i(a_1, \dots, a_{l_i}) \quad.
$$
 
We will also assume that for any pair of vertex types $v_i$
and $v_j$, there are $K(i,j) \geq 0$
families of edges, and for each of
$k=1, \dots, K(i,j)$, the type-$k$ edge coming out of vertex
$v_i(a_1, \dots, a_{l_i})$ may wind up in any of
the vertices
$v_j(b_1, \dots, b_{l_j})$, where
$(b_1, \dots, b_{l_j})$ may belong to a well-defined
subset of $D_j$, let's call it $E_{i,j}^{(k)}(a_1, \dots, a_{l_i})$.
We also assume that every such edge 
has a certain {\it weight} given by a  {\it weight-function}
$$
W_{i,j}^{(k)}(a_1 , \dots, a_{l_i};b_1 , \dots, b_{l_j}) \quad .
$$
 
The weight of a {\it path} $P$, $Wt(P)$, is the sum of the weights of
its participating edges. We are interested in computing
the weight-enumerator of all paths
$$
\sum_{P \in Paths} q^{Wt(P)} \quad,
$$
either explicitly, and failing this, to have a polynomial-time
algorithm for computing the {\it series expansion}, i.e. the first
$N$ terms of its power-series expansion, for any given $N$.
 
We now digress to define a {\it Rota-Operator}.
 
{\bf Definition of an Atomic Rota-Operator}: An Atomic Rota operator
from the 
ring of formal power series in $r$ variables $Z(q)(x_1, \dots, x_r)$ to the
ring of formal power series in $s$ variables $Z(q)(y_1, \dots, y_s)$ 
(with coefficients from the ring of integer-coefficient
formal power-series in $q$),
is an operator of the form
$$
T[f(x_1, \dots, x_r)]=
R(q,y_1, \dots, y_s) D_{x_1}^{\alpha_1} \dots D_{x_r}^{\alpha_r}
f(x_1, \dots, x_r)\vert_{\{x_1=m_1, \dots, x_r=m_r\}} \quad ,
\eqno(ARO)
$$
where $R(x,q_1, \dots, x_r)$ is a rational function of all its arguments,
$D_{x_1}, \dots, D_{x_r}$ are the differentiation operators with respect
to $x_1, \dots, x_r$ respectively, $\alpha_1, \dots, \alpha_r$ are
non-negative integers, and $m_1$, \dots, $m_r$ are each {\it monomials}
in the variables $(q, y_1, \dots, y_s)$.
 
{\bf An Example of an Atomic Rota Operator}:
$$
f(x_1,x_2) \rightarrow {{q^3y_1y_2y_3} \over {(1-qy_1)(1-q^2y_1y_2y_3)}}
D_{x_1}D_{x_2}^{3} f(y_1y_2y_3,qy_3) \quad .
$$
 
{\bf Definition of a Rota Operator}: A {\it Rota Operator} is
a sum of Atomic Rota Operators.
 
It turns out that in many applications, the following 
property holds:
 
{\bf The Umbral Axiom}
 
For every pair of {\it vertex types}, $v_i, v_j$, and for
each of its $K(i,j)$ edge-types connecting them, the following operator
from $Z(q)(x_1, \dots, x_{l_i})$ to $Z(q)(y_1, \dots, y_{l_j})$,
defined on the basis of monomials by
$$
x_1^{a_1} \cdots x_{l_i}^{a_{l_i}} \rightarrow
\sum_{ (b_1, \dots , b_{l_j}) \in E^{k}_{i,j} (a_1, \dots, a_{l_i}) }
q^{W_{i,j}^{(k)}(a_1 , \dots, a_{l_i};b_1 , \dots, b_{l_j})}
y_1^{b_1} \cdots y_{l_j}^{b_{l_j}}
$$
is an atomic Rota operator, let's call it $Q_{i,j}^{k}$.
 
Also, let's define the {\it transition-operator} from
vertices of type $i$ to vertices of type $j$
($1 \leq i,j \leq n)$, by
$$
\P_{i,j} := \sum_{k \in K(i,j)} Q_{i,j}^{k} \quad .
$$
which by our assumption are all Rota operators.
 
Let's define the {\it mishkal} of a path $P$, in our digraph,
that ends with the vertex $v_i(a_1, \dots, a_{l_i})$ by
$$
q^{Wt(P)} x_1^{a_1} \dots x_{l_i}^{a_{l_i}} \quad ,
$$
and let's define the {\it total mishkal} of all the paths that
end in a type-$i$ vertex by
$$
F_i(q;x_1, \dots , x_{l_i}):=\sum_{P} mishkal(P) \quad,
$$
where the sum extends over the infinite set of paths that end
in a type-$i$ vertex.
 
It follows immediately from this set-up that the $n$ formal power series
$F_j$, ($j=1, \dots, n$) satisfy the following system
of $n$ differential-functional equations
$$
F_j= [j \in Start] + \sum_{i=1}^{n} \P_{i,j} F_i \quad .
\eqno(FundamentalSystem)
$$
In the lucky case, we can solve this system explicitly,
but at any rate, we can use it iteratively to find a series
expansion in $q$. In either case, the desired weight-enumerator
is given by
$$
\sum_{j \in Finish} F_j(q;1, \dots, 1) \quad .
$$
 
Note that the variables $x_1, \dots, x_{l_i}$
corresponding to the $l_i$-parameter vertex type $i$,
for $i=1, \dots, n$, serve as {\it catalysts}, all to be discarded
(i.e. substituted by $1$) at the end of the ``reaction''.
 
I propose to use this set-up to study important subsets 
and supersets of
`hard-to-count' combinatorial families that arise in statistical
physics: lattice animals, self-avoiding walks and polygons,
and percolation. Here the number of components in each vertical
slice is bounded, but the size itself is indefinitely large.
So this can capture many more creatures than the finite-transfer
matrix methods in which the creatures are confined to a strip.
Even more interesting is the kind of {\it functional equations}
for the generating functions of these sophisticated toy models.
Recall that in the finite transfer-matrix method, one always gets
{\it rational functions} making the critical behavior
clearly unphysical and mathematically boring. The kind of functional
equations that one should get now resemble those of the
Renormalization Group method, and should give `interesting', and hopefully
closer-to-reality, critical behavior.
\bigskip
 
\centerline{\bf 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, {\it 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 \leq n \leq 7$. The general formula,$n!$, and its,
completely rigorous,
inductive proof, can be found in ``{\it Sefer Ma'asei Khosev}'' 
written in the 14th
century by Rabbi Levi Ben Gerson.
 
The more refined counting of permutations, according to various
{\it 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\"utzenberger. 
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\"orner, Jennifer Galovich,
Adriano Garsia, Kevin Kadell, Don Rawlings, Jeff Remmel, Bruce Sagan, 
Richard Stanley, Dennis Stanton,
Dennis White, Michelle Wachs, Xavier (G\'erard) Viennot and many others.
 
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):=\sum_{\pi \in S_n} q^{stat(\pi)} \quad ,
$$
 
 
a) Closed form? (like in the case of {\it inv} and {\it 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
$\sum_{n=0}^{\infty} {{F_n(q) z^n} \over {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 , \dots , q_k):=\sum_{\pi \in S_n} q_1^{stat_1(\pi)}
\dots q_k^{stat_k(\pi)} \quad ?
$$
 
In a very interesting recent paper, Eric Babson and Einer Steingrimsson
[BS] initiated their own theory of `pattern-statistics' that include
most of the known permutation statistics. They made several conjectures
that Foata and I proved, by combining symbolic computation and
`human combinatorics'. We hope that our ideas, combined with
Babson and Steingrimsson's seminal concept will prove useful.
\vfill
\eject
{\bf REFERENCES}
 
 
[A0] S. Ahlgren and K. Ono
{\it A Gaussian hypergeometric series evaluation and
Ap\'ery number congruences}, J. Reine Angew. Math. {\bf 518} (2000),
187-212.
 
[BS] Eric Babson and Einer Steingrimsson,
{\it Generalized permutation patterns and a classification
of the Mahonian statistics}, S\'em. Loth. Comb. 
[{\eighttt http://radon.mat.univie.ac.at/\Tilde slc/}]
{\bf 44 }(2000),
B44b.
 
[Br] David Bressoud, ``{\it Proofs and Confirmations:
The Story of the Alternating Sign Matrix Conjecture}'',
Cambridge University Press and The Mathematical 
Association of America, 1999.
 
[BP] David Bressoud and James Propp, {\it How the alternating
sign conjecture was solved}, Notices Amer. Math. Soc. {\bf 46}
(1999), 637-646.
 
[LW] Xiao-Song Lin and Zhenghan Wang,
{\it Random Walk on Knot Diagrams, Colored Jones Polynomial
and Ihara-Selberg Zeta Function}, preprint,
{\tt http://xxx.lanl.gov : math.GT/9812039}.
 
[PS] Alexander Postnikov and Richard Stanely, {\it Deformation of
Coxeter hyperplane arrangements}, preprint, 
{\tt http://xxx.lanl.gov : math.CO/9712213}.
 
[WZ] Herb Wilf and Doron Zeilberger,
 {\it An algorithmic proof theory for hypergeometric
(ordinary and "q") multisum/integral identities}, Invent. Math. 
{\bf 108}, 575-633 (1992).
 
{\bf Biographical Sketch-Doron Zeilberger, P.I.}
 
{\bf a. Professional Preparation}
 
University of London, Mathematics, B.Sc. (With First Class Honours),
1972.
 
Weizmann Institute of Science, Mathematics, Ph.D., 1976.
 
Institute for Advanced Study, Mathematics, member, 1977-1978.
 
{\bf b. Appointments}
 
1990-present: Temple University, Laura H. Carnell Professor(2000-),
Professor (1990-1999).
 
1983-1990: Drexel University, Professor (1988-1990), Associate Professor
(1983-1988).
 
1982-1983: University of Pennsylvania, Lecturer.
 
1980-1982: Weizmann Institute of Science, Senior Scientist.
 
1979-1980: University of Illinois, Urbana, Visiting Lecturer.
 
1978-1979: Georgia Institute of Technology, Visiting Assistant Professor.
 
 
{\bf c. (i) Five Relevant Publications}
 
1. (With M. Petkovsek and H. S. Wilf) {\it A=B}, AK Peters, Wellesley, (1996).
 
2. (With C. Krattenthaler)
{\it Proof of a Determinant Evaluation Conjectured by Bombieri, Hunt, and
van der Poorten}, New York J. of Math. {\bf 3}(1997), 54-102.
 
3. {\it Theorems for a price: Tomorrow's semi-rigorous mathematical culture},
Notices of the Amer. Math. Soc. {\bf 40 \# 8}, 978-981 (Oct. 1993).
Reprinted: Math. Intell. {\bf 16}, no. 4, 11-14 (Fall 1994).
 
4. {\it A Holonomic systems approach to special functions
identities}, J. of Computational and Applied Math. {\bf 32},
321-368 (1990).
 
5. (With H.S. Wilf) {\it An algorithmic proof theory for hypergeometric
(ordinary and "q") multisum/integral identities}, Invent. Math. 
{\bf 108}, 575-633 (1992).
 
{\bf c. (ii) Five Other Publications}
 
1. (With G. Almkvist) {\it The method of differentiating under the
integral sign}, J. Symbolic Computation {\bf 10}, 571-591 (1990).
 
2. {\it The method of creative telescoping}, J. Symbolic Computation
{\bf 11}, 195-204 (1991).
 
3. {\it Proof of the alternating sign matrix conjecture}, Elect. J. 
Combinatorics {\bf 3(2)} [Foata Festschrift] R13 (1996).
 
4. (With D. Bressoud) {\it A proof of Andrews' q-Dyson conjecture},
Discrete Math. {\bf 54}, 201-224 (1985).
 
5. {\it  Sister Celine's technique and its generalizations}, J. Math.
Anal. Appl. {\bf 85}, 114-145 (1982).
 
{\bf d. Synergetic Activities}
 
The {\it Wilf-Zeilberger Algorithmic Proof Theory} has been
widely used by mathematicians and scientists alike, and
has been implemented in all major computer algebra systems.
Currently, the National Institute of Standards and Technology is
`wiring' the classic handbook of mathematical functions
(the most widely cited book in science), by using
WZ theory as its driving force.
 
My many Maple packages, in addition to doing the specific
tasks that they were designed to do, when taken together,
constitute a whole `research methodology' for doing
computer-assisted and computer-generated research.
 
{\bf e. Collaborators and Advisor}
 
{\bf e(i). Recent Collaborators}
 
Tewodros Amdeberhan (deVry Inst.), Shalosh B. Ekhad (Temple Univ.),
Dominique Foata (Univ. of Strasbourg), 
Christian Krattenthaler (Univ. of Vienna), 
Istvan Nemes (RISC-Linz), John Noonan (Mount Vernon Nazarene College),
Marko Petkovsek (University of Slovenia), and Herb Wilf
(University of Pennsylvania). 
 
{\bf e(ii). Graduate Advisor}
 
Harry Dym (Weizmann Institute).
 
{\bf e(iii). Thesis Advisor}
 
So far, ten students received their Ph.D. degree under by supervision.
\smallskip
     * Sheldon Parnes (Industry, Coloardo), 1993.
\smallskip
     * Ethan Lewis (IBM, Israel) 1994.
\smallskip
     * Craig Orr (NSA), 1994.
\smallskip
     * John Majewicz (Comm. College of Philadelphia), 1997.
\smallskip
     * John Noonan (Mt. Vernon Nazarene College, OH), 1997.
\smallskip
     * Tewodros Amdeberhan (deVry Inst. of Tech., NJ), 1997.
\smallskip
     * Melkamu Zeleke (William Patterson Univ., Wayne, NJ),  1998.
\smallskip
     * Aaron Robertson (Colgate Univ., Hamilton, NY), 1999.
\smallskip
     * Akalu Tefara (Grand Valley State Univ., MI), 2000.
\smallskip
     * Anne Edlin (Holy Family College, NJ), 2000.
\smallskip
 
 
{\bf Short Biography-Dominique Foata, consultant}
 
Dominique Foata received his {\it doctorat de  \'etat} under
Marcel-Paul Sch\"utzenberger in $1965$. He is currently
distinguished professor of mathematics at the University
of Strasbourg. His many honors include ICM 83',
and the UAP prize, 1985.
 
\end
 
 
 
