%umbII.tex: ``The Umbral Transfer-Matrix Method: II. 
%Counting Plane Partitions''
%a Plain TeX file by Doron Zeilberger (3 pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\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\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
%end macros
 
\bf
\centerline
{
THE UMBRAL TRANSFER-MATRIX METHOD: 
II. Counting Plane Partitions
}
\rm
\bigskip
\centerline{ {\it 
Doron ZEILBERGER
}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. 
%\break
{\eighttt zeilberg@math.temple.edu} \hfill \break
{\eighttt http://www.math.temple.edu/\Tilde zeilberg/   .}
Oct. 25, 2000.  Exclusive to The Personal Journal of
Ekhad and Zeilberger
{\eighttt http://www.math.temple.edu/\Tilde zeilberg/pj.html   .}
Accompanied by Maple package {\tt PPar} available from
Zeilberger's Umbral Page
{\eighttt http://www.math.temple.edu/\Tilde zeilberg/umb.html   .}
Supported in part by the NSF.
} 
}
 
{\bf Abstract:} We continue the 
5-part saga on the Umbral Transfer-Matrix
Method, based on Gian-Carlo Rota's seminal notion of the umbra.
In this article we describe the Maple package {\tt PPar} that
automatically constructs Umbral Schemes for enumerating
$r$-rowed plane partitions, for {\it specific} but
{\it arbitrary} $r$, and that
also automatically constructs {\it Evolution Umbra} for
monotone triangles.
 
{\bf An Umbra for $r$-rowed plane partitions}
 
Recall that an $r \times k$ plane-partition is a matrix
of non-negative integers $(a_{i,j})$, $1 \leq i \leq r, 1 \leq j \leq k$,
that is weakly decreasing along every row and every column.
There is only one `state' i.e. vertex-type,
and it is parameterized by non-increasing tuples of non-negative
integers: $(a_1, \dots, a_r)$, where 
$a_1 \geq a_2 \geq \dots \geq a_r \geq 0$. The Rota operator
connecting one column to the next is
the operator sending a generic monomial
$x_1^{b_1} x_2^{b_2} \cdots x_r^{b_r}$ corresponding to the current
leftmost column, to the sum of all monomials
$(q x_1)^{a_1} (q x_2)^{a_2} \cdots (q x_r)^{a_r}$ , where
the sum ranges over all
$a_1 \geq a_2 \geq \dots \geq a_r \geq 0$ for which
$a_i \geq b_i$ for all $i$ between $1$ and $r$.
 
In order to do this automatically, we have to partition the
summed set into `chambers'. For any given $i$ ($1 \leq i \leq r$),
of course it is required that $a_i \geq b_i$, i.e. thinking of
the $b_1, b_2, \dots, b_r$ as the heights of girls who 
stand in (weakly) decreasing order, and who each must find
a (weakly) taller boy as her dancing partner, and the chosen boys
must also be in (weakly) decreasing order, then a short girl is
allowed to pick a boy that is even taller than her taller neighbor,
in fact, the shortest girl may even pick a boy that is taller
than the tallest girl. BUT, if she does that, then of course
all the other boys must be taller than the tallest girl.
 
So for a fixed $(b_1, \dots, b_r)$, and a legal choice
$(a_1, \dots, a_r)$, let's call the {\it profile}
$f(i)$ the smallest $j$ such that $a_i\geq b_j$. Of course
$f(i) \leq i$, and $f(1) \leq f(2) \leq \dots \leq f(r)$.
It is well known and easy to see that there are 
$C_r={{2r} \choose {r}}/(r+1)$ such sequences, and they are sometimes
called {\it Catalan sequences}. For example when $r=2$ there
are $2$ Catalan sequences: 11 and 12, and when $r=3$ there are $5$:
$111,112,113,122,123$.
 
Now for any specific profile, $f$, it is easy to sum
$(q x_1)^{a_1} (q x_2)^{a_2} \cdots (q x_r)^{a_r}$ , over all
$(a_1, \dots, a_r)$ with that profile, since it only involves
summing series of the form
$$
P_m (A,B;z):=\sum_{A \leq i_1 \leq i_2 \leq \dots \leq i_m \leq B}
z_1^{i_1} \dots z_m^{i_m} \quad,
$$
that Maple (and even you!) can  evaluate in closed form (symbolically).
Then the required sum is a product of a certain number of such
expressions, where the number of terms in the product equals the
cardinality of the range of $f$. For example 
the profile $1111$ would only have
$P_4 (b_1, \infty; qx_1, qx_2,qx_3,qx_4)$ 
while the profile
$1234$ would be
$$
P_1(b_1,\infty; qx_1)P_1(b_2,b_1-1; qx_2)
P_1(b_3,b_2-1; qx_3)P_1(b_4,b_3-1; qx_4) \quad.
$$
For details study carefully the source code of the Maple package
{\tt PPar}.
 
The next step is to find the pre-umbra by summing all these
$C_r$ expressions, and finally the {\it master} package
{\tt ROTA} converts the pre-umbra to a full-fledged
Umbral Scheme. The function call is {\tt UmbralScPP(x,q,t,r)}.
Here $x$ is the indexed variable, as above, $q$ is the
usual $q$ that keeps track of the sum of the parts of
the plane-partition, and $t$ keeps track of 
the number of columns. Note that the zero vector is permitted,
so the coeff. of $t^k$ is really the generating function for
plane partition with at most $k$ columns and at most $r$ rows,
i.e. those whose 3D Ferrers diagram fit in an $r \times k \times \infty$
box, and in addition it is weighted by $x_1^{a_1} \dots x_r^{a_r}$,
where $a_1, \dots, a_r$ is the leftmost column.
For example, to get (essentially) the umbra
derived by hand in [Z1] (for 2-rowed plane-partitions)
type: {\tt UmbralScPP(x,q,t,2)}.
 
To get the generating function for {\tt n}-rowed, {\tt r}-column
plane partitions, using the variable {\tt q}, type
{\tt GFPP(n,r,q);}, for specific {\tt r} and {\tt n}. For example
try  {\tt GFPP(2,3,q);}. Of course, we already have MacMahon's
box theorem, so we don't need {\tt PPar}, but the point is
to {\it illustrate} a general method that could be applied in
many other situations, where closed form, or even efficient algorithms,
are not known and may not exist. In fact
{\tt CheckPercy(n,r,q);} compares the answer to MacMahon's box theorem,
and returns {\tt true} if it agrees. If you want to keep track
of the leftmost column, i.e. the weight is the previous one times
$x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$, where $a_1, \dots, a_n$
are the entries of the leftmost row, then type:
{\tt GFPPx(n,x,r,q);} . Here {\tt n} and {\tt r} are {\it specific}
integers, while $x$ and $q$ are symbols. For example, 
{\tt GFPPx(3,x,2,q);}.
 
{\bf An Umbra for Monotone Triangles}
 
Recall that a {\it monotone triangle}  (a.k.a. {\it strict Gelfand
pattern})
of size $n$ is a triangular array of positive integers
$(a_{i,j})$, $n \geq i \geq j \geq 1$, such that
$a_{i,j} < a_{i,j+1}$ and $a_{i-1,j-1} \leq a_{i,j} \leq a_{i-1,j}$.
The monotone triangles of size $n$ whose bottom row
is $1, 2, \dots, n$, i.e. for which $a_{n,j}=j$ for $j=1, \dots, n$,
are in simple bijection with $n \times n$ {\it alternating sign
matrices}.
 
I believe that the Umbral Transfer Matrix method could be used
to get yet another proof of the {\it Alternating Sign Matrix Conjecture}
(see [B] for a gripping account). But it is not clear that this would
be easier than the two already existing proofs. Since I have already
paid my dues working on this problem, I will leave this as 
a challenge to the reader. Here I will only use it as an illustrative
example, and describe the {\it automatic} generation of
the generating function for {\it all} monotone triangles,
but of a {\it specific} size. Then extracting the coefficient
of $x_1 x_2^2 x_3^3 \dots x_n^n$ would give the $n$-th term in
the famous ASM sequence.
 
Suppose that the bottom row is now $(b_1, \dots, b_k)$.
The weight of such a monotone triangle is $x_1^{b_1} \cdots x_k^{b_k}$.
Which tuples $(a_1, \dots, a_{k+1})$ may continue it to
the $(k+1)$-th row? We need to sum
$x_1^{a_1} \cdots x_{k+1}^{a_{k+1}}$ over all legal $(k+1)$-tuples
such that $a_1 < a_2 < \dots < a_k < a_{k+1}$ and
$a_1 \leq b_1 \leq a_2 \leq \dots \leq b_k \leq a_{k+1}$. The summed-over set
can be partitioned into $2^k$ subsets, according to 
{\it profile}. The profile of 
$(a_1, \dots, a_{k+1})$ is the subset of $\{1,2, \dots k\}$ such that
$b_i=a_{i+1}$. It is easy to explicitly (symbolically) sum the
monomials corresponding to tuples belonging to any one profile.
{\tt PPar} does that for each of the $2^k$ profiles, getting expressions
in $x_1, \dots, x_{k+1}$ and $b_1, \dots, b_k$. It adds them
all up thereby getting the {\it preumbra} connecting a generic
monomial $x_1^{b_1} \cdots x_k^{b_k}$ to the sum of all its legal
extensions.  Then procedure {\it ToUmbra} from the
master package {\tt ROTA} turns the pre-umbra into the Umbra
$T_k$ connecting monotone triangles of size $k$ to those of
size $k+1$. This is done with procedure {\tt UmbraMT} of
{\tt PPar}. The function call is {\tt UmbraMT(x,k);},where
$x$ is the symbol for the indexed variable, and $k$ is
a {\it specific} integer. For example try
{\tt UmbraMT(x,3);}. To get the generating function for
monotone triangles of size $k$ (which is just
$T_{k-1}T_{k-2} \dots T_1 (x_1)$), type {\tt GFMT(x,k);}.
To get the number of monotone triangles of size $k$ with a
prescribed bottom row (a list of increasing integers), type
{\tt MT(bottom\_row);}. For example {\tt MT([1,2,3,4,5]);} 
should yield the number of $5 \times 5$ alternating sign matrices
(429), while {\tt MT([1,3,5,7]);} gives the number of
monotone triangles of size $4$ whose bottom row is
$1,3,5,7$. Once again, note that this is {\it not} the most efficient
way to crank out numbers, and the main justification of
procedure {\tt MT} is to test the validity of the program.
 
{\bf Other Symmetry Classes and Solid Partitions}
 
The Same approach should enable one to construct {\it umbra},
or Umbral Schemes, for symmetric, totally symmetric, and
other kinds of plane partitions. It should also be amenable
to counting solid partitions, and more generally, generalized
partitions that live on a poset, taking Stanley's classical
theory of P-partitions ([S]) as a starting point, and
building Umbral Schemes on it.
  
{\bf REFERENCES}
 
[B] David Bressoud, ``{\it Proofs and Confirmations: The Story
of The Alternating Sign Matrix Conjecture}", Cambridge University
Press and The Math. Assoc. of Amer., 1999.
 
[S] Richard P. Stanley, ``{\it Enumerative Combinatorics}",
volume 1, Wadsworth, Monterey, California, 1986.
Reprinted by Cambridge University Press.
 
[Z1] Doron Zeilberger,
{\it The Umbral Transfer-Matrix Method: I. Foundations},
J. Comb. Theory Ser. A {\bf 91} (2000), 451-463.
[Rota memorial issue].
 
[Z2] Doron Zeilberger,
{\it The Umbral Transfer-Matrix Method: II. Counting Plane 
Partitions}, Personal Journal of Ekhad and Zeilberger,
{\eighttt http://www.math.temple.edu/\Tilde zeilberg/pj.html   .}
(this article).
 
[Z3] Doron Zeilberger,
{\it The Umbral Transfer-Matrix Method: III. Counting Animals},
in preparation.
 
[Z4] Doron Zeilberger,
{\it The Umbral Transfer-Matrix Method: IV. Counting Self-Avoiding
Polygons and Walks}, in preparation.
 
[Z5] Doron Zeilberger,
{\it The Umbral Transfer-Matrix Method: V. The Goulden-Jackson
Cluster-Method for Infinitely Many Mistakes}, in preparation.
 
\bye