%umbI.tex: ``The Umbral Transfer-Matrix Method: I. Foundations''
%a Plain TeX file by Doron Zeilberger (12 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: I. FOUNDATIONS
}
\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/   .}
March 30, 2000.  Supported in part by the NSF.
} 
}
 
{\bf In Fond Memory of Gian-Carlo ROTA (April 27, 1932- April 18, 1999)} 
 
{\bf Abstract:} We lay the foundations for the Umbral Transfer-Matrix
Method, based on Gian-Carlo Rota's seminal notion of the ``umbra'' as
a linear functional on a vector space of formal power series.
The full potential of Rota's concept, to be described in subsequent
parts of this series of articles,
emerges when it is implemented on a computer. 
 
{\bf Priests and Prophets}
 
According to {\it cohen venavi}, a classic Hebrew essay
by Ekhad Ha-Am, there are two ways of serving God:
{\it Priest} and {\it Prophet}. The priest is a very skilled technician
who knows by heart the 613 {\it mitzvahs}, and who can slaughter
a lamb with due regard to the many rigorous and subtle laws.
On the other hand, a prophet is 
often very clumsy in the day-to-day ritual, and
is unable to sacrifice an animal properly.
But prophets
have a direct-line to God. In the long run, their impact and
influence far surpass those of the priests. Don't we all
know the names of Isaiah, Jeremiah, and Ejekiel? Yet none of
us remembers any of the names 
of the high priests who lived at the same time.
 
Gian-Carlo Rota is a paragon of the mathematical prophet.
His technical contributions, while substantial,
dwarf in comparison to his {\it vision}, {\it insight}, and
new unifying {\it concepts}. Also his uncanny {\it realizations}
that some things are {\it important}, have revolutionized
more than one combinatorial area.
 
Rota's dislike of routine priestly work is expressed
nicely in the following extract from
Richard Stanley's touching and warm obituary that
appeared in SIAM News:
 
{\it ROTA was always interested in the ``BIG picture'' and
trying to understand the true essence of any subject in which
he was interested.}
 
Conversely, Rota was not interested in the ``little picture''
and, as far as I know,
never solved any major (or minor) specific open problem.
He was often criticized, usually behind his back, of publishing
`trivial' results, for example, ``using 50 pages to prove the
Vandermonde-Chu identity''. It is very possible that some of
his longer papers, especially those about the Umbral Calculus, would
not have found a journal, had he not accepted them himself to
{\it Advances in Mathematics}.
 
Luckily, Gian-Carlo was unfazed by these snide remarks and
narrow-minded opinions.  He was a GREAT GURU, and fortunately, he
knew it. In one of his numerous inimitable
{\it Forewords}
(this one to "Species" by F. Bergeron, G. Labelle, and P. Leroux),
he wrote:
 
``{\it There is a second way in which mathematics advances. It happens
whenever some common sense notion that had heretofore been taken for granted
is discovered to be wanting, to need clarification and definition}''
 
While he was talking here about Andr\'e Joyal's
{\it species}, I am sure that he was also referring to
his own numerous {\it clarifications of common sense notions}.
In particular that of the {\it umbra}.
 
The {\it Umbral Calculus} was a standard tool of the trade
in 19th-century algebra,  but it was always surrounded by a magical aura,
and the only attempt at a full rigorization before
Rota, by E.T. Bell, was a conceptual flop. Rota's stroke of
genius had to wait to the 20th century and to the notion
of the {\it linear functional}. Indeed Rota's seminal contribution,
which like almost all major breakthroughs, is {\it a posteriori} obvious,
was the {\it mere} {\it REALIZATION} that an Umbra 
{\it is} a linear functional.
 
Let's recall Rota's favorite example.
Prove that
$$
a_n=\sum_{k=0}^{n} {{n} \choose {k}} b_k \quad,
\eqno(1)
$$
if and only if
$$
b_n=\sum_{k=0}^{n} (-1)^{n-k} {{n} \choose {k}} a_k \quad .
\eqno(1')
$$
The classical umbral proof goes as follows. Let $a=b+1$.
Then by the binomial theorem 
$$
a^n=\sum_{k=0}^{n} {{n} \choose {k}} b^k \quad,
\eqno(2)
$$
and also, since $b=a-1$, 
$$
b^n=\sum_{k=0}^{n} (-1)^{n-k} {{n} \choose {k}} a^k \quad .
\eqno(2')
$$
Now just ``lower the superscripts (powers) and make them subscripts''.
 
Rota's rendition is as follows. Define a {\it linear functional}
(``umbra'') $A$ on the vector space of polynomials, by defining
it on monomials by $A(x^n) :=a_n$, and extending by linearity.
Similarly define $B(x^n) :=b_n$. Equation $(1)$ says 
that $A(x^n)=B((x+1)^n)$ for $n=0,1,2, \dots $. By linearity,
$A(p(x))=B(p(x+1))$, for {\it any} polynomial $p(x)$, and
hence $B(q(x))=A(q(x-1))$ for {\it any} polynomial $q(x)$.
In particular, if $q(x)=x^n$, we get $(1')$.
 
Rota's insight lead to a beautiful theory ([R][RR][LR]),
and enabled a redoing of classical invariant theory in the ``right''
way ([KR]). It also lead to many new results in the theory,
that did not make sense before.  But, as many narrow-minded
petit priests argued, ``it was not good for anything''.
 
In this series of papers, I hope to show how Rota's beautiful
concept, coupled with the Transfer-Matrix method,
could be used to COMPUTE generating functions for
many hard-to-count combinatorial objects, like certain 
important subsets and supersets of lattice animals and self-avoiding walks.
 
{\bf Hamming got it Backwards: The Purpose of Insight is Computation}
 
Speaking of {\it computations}, many mathematicians feel the
need to apologize for computing, and Hamming's famous
quip: ``{\it the purpose of computation is not numbers but
insight}''  has deteriorated into a clich\'e. This is a
hold-over of our {\it pure}-itan upbringing, that made us feel
guilty about ``computation without insight'' the same way
our parents used to feel guilty about ``sex without love''.
 
There is nothing wrong with {\it computation for computation's sake}.
I would love to know the number of self-avoiding walks with $200$ steps,
or the number of polyominoes with $200$ cells. Very often the
numerical output itself does not give any new ``insight'', yet the
attempt to compute it does, but even if it does not, there is still
nothing wrong with brute computation.
 
Actually, there is! Completely brutish computations cannot be carried
very far. So at present we need INSIGHT to do {\it efficient} computations.
In the future, that insight may very well come from computers
themselves, but at present, we still need humans like Rota
to supply such insight.
 
Most of us mathematicians will soon be replaceable by machines
(some of us already are), yet
prophets like Gian-Carlo will, most probably, {\it always}
be needed.
 
{\bf Why is the Concept of Umbra so Crucial}
 
I will soon define the {\it Umbral Transfer-Matrix Method}, but
before let me explain, in general terms, why the notion of
the umbra is {\it so} important. In the finite transfer-matrix method [Z0],
the entries of the matrix are numbers or polynomials.
In the current theory, the entries are {\it operators}.
In all but the most trivial applications, the operators are
very complicated, and it would be impossible to find them
by hand. So we need the computer to ``do research'' and find
the operators. But an operator is a rather abstract notion,
so how can a ``dumb'' computer find it? It can't reason combinatorially.
It turns out that, in many cases of interest,
it is possible to {\it mechanize} the action
of the operator on a generic monomial, since as would become clear
from the examples below, it only involves summing 
(finite and infinite) geometrical series, or their derivatives, that Maple
does very well, and adding them up, that Maple does equally well.
Then, since we know what kind of an operator to expect, it is possible
to {\it automatically deduce} the operator from its action on a generic
monomial, and hence Maple can write down the operator (in a formal,
Maple-readable, format). Once we have the Operator-Matrix,
we can use it to generate in {\it polynomial time}, series expansions
for the combinatorial objects considered, and sometimes even
to solve the induced system of mixed differential-q-equations
{\it explicitly}, enabling us
to get the generating function in some kind of {\it closed form}.
 
{\bf Weighted Finite-Parameter Infinite Directed Graphs}
 
The Finite Transfer-Matrix method is used to weight-enumerate
paths on a {\it finite} digraph, see [Z0] 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 .
$$
\vfill\eject
{\bf Maple Representation of Atomic Rota Operators}
 
The Atomic Rota Operator of $(ARO)$ is represented in our Maple
packages by a list of length $3$:
$$
[R,[\alpha_1, \dots, \alpha_r],[m_1, \dots, m_r]] \quad .
$$
For example: the above operator, in Maple, would read:
$$
[q**3*y1*y2*y3/((1-q*y1)*(1-q**2*y1*y2*y3)),[1,3],[y1*y2*y3,q*y3]] \quad .
$$
 
{\bf Definition of a Rota Operator}: A {\it Rota Operator} is
a sum of Atomic Rota Operators.
 
{\bf Maple Representation of Rota Operators}
 
The Rota operator $\P=\P_1 + \dots + \P_m$, where $\P_1, \dots, \P_m$
are atomic Rota operators, is denoted by the set
$\{ P_1, \dots, \P_m \}$. For example the Rota operator
$f(x) \rightarrow qf'(1)+ xf(qx)+(x/(1-qx)f''(q^3)$ is represented
by $\{ [q,[1],[1]],[x,[0],[q*x]],[x/(1-q*x),[2],[q^3]]\}$.
 
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''.
 
At this point, all this sounds like very abstract nonsense.
Hopefully the following simple examples will make the new concept
clearer. In subsequent parts ([Z2][Z3][Z4][Z5]),
we hope to present ``heavy-duty'' examples, that would be 
hopeless without a computer.
 
{\bf Vertex-Weighted Infinite Directed Graphs}
 
Even though it is easy to subsume this case in the former,
edge-weighted, case, it is pedagogically, and implementation-wise,
easier to treat it separately. In this model, the vertices rather
than the edges are endowed with weights:
$wt(v_i(a_i))$ and the weight of a path is the sum of the weights
of its vertices (counted separately for each visit).
Here we also assume that there $K_{i,j}(a_i,b_j)$ edges between
vertex $v_i(a_i)$ and $v_j(b_j)$.
 
The Umbral Axiom now takes the form
 
{\bf The Umbral Axiom for Vertex-Weighted Digraphs}
 
For every pair of {\it vertex types}, $v_i, v_j$, the 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_{j=1}^{n}
\sum_{ (b_1, \dots , b_{l_j}) \in D_j}
K_{i,j}(a_i,b_j) q^{W_j(b_1 , \dots, b_{l_j}) }
y_1^{b_1} \cdots y_{l_j}^{b_{l_j}}
$$
is a Rota operator, let's call it $\P_{i,j}$.
 
We also assume that, for all vertex-types
$i=1, \dots, n$ the formal power-series
$$
I_{i}(q,x_1, \dots, x_{l_i}):=
\sum_{ (a_1, \dots , a_{l_i}) \in D_i}
q^{W_i(a_1 , \dots, a_{l_i}) }
x_1^{a_1} \cdots x_{l_i}^{a_{l_i}} \quad,
$$
of $1-vertex$ paths, are all rational functions.
The analog of $(FundamentalSystem)$ for Vertex-weighted digraphs is:
$$
F_j= [j \in Start]\, I_j + \sum_{i=1}^{n} \P_{i,j} F_i \quad .
\eqno(FundamentalSystemVW)
$$
 
Both $(FundamentalSystem)$ and $(FundamentalSystemVW)$, have the
form of an
 
{\bf Umbral Scheme}:
$$
F_i= A_i + \sum_{j=1}^{n} \Q_{i,j} F_j \quad ,
\eqno(UmbralScheme)
$$
where $F_j(q,x_1, \dots, x_{l_j})$ are the unknown formal-power series,
and $\Q_{i,j}$ are explicit Rota operators,
together with a subset of $\{1,2, \dots, n \}$, $S$, and
the desired quantity is the formal power-series
$$
\sum_{i \in S} F_i (q,1,\dots,1) \quad ,
$$
where in the argument of $F_i$, there are $l_i$ $1$'s.
 
{\bf Several Statistics}
 
Suppose that we want to weight-enumerate according to several attributes
(statistics), then all we said above goes verbatim, except that
$q$ is replaced by a multi-variable {\bf q}.
 
{\bf Maple Representations of Umbral Schemes}
 
We will represent the Umbral Scheme $(UmbralScheme)$
as a list of length $4$:
$$
[S,UmbralMatrix,InitialVector,VariablesLists] \quad ,
$$
 
where $UmbralMatrix$ is the matrix of Rota operators
$$
UmbralMatrix=[[\Q_{1,1},\Q_{1,2}, \dots, \Q_{1,n}], \dots ,
[\Q_{n,1},\Q_{n,2}, \dots, \Q_{n,n}]] \quad.
$$
In particular, the number of elements of $UmbralMatrix$,
$n$, determines the number of vertex-types,
that we will assume are called $\{1,2, \dots, n \}$.
$S$ is the subset of $\{1,2, \dots, n \}$ mentioned above.
 
$InitialVector$ is the vector of rational functions
$$
InitialVector=[A_1, \dots, A_n] \quad.
$$
Finally $VariablesLists$ is the list of variables that the
$F_i$ depend on (not counting $q$):
$$
VariablesLists=[[x_1, \dots, x_{l_1}],
[x_1, \dots, x_{l_2}], \dots, 
[x_1, \dots, x_{l_n}]]
$$
Note that we may use $x_1, x_2, \dots $ for each of the argument sets
of $F_i$ ($i=1, \dots , n$), i.e. we don't have to invent new names,
since these variables are local.
 
{\bf VERY SIMPLE EXAMPLES THAT EVEN HUMANS CAN WORK OUT}
 
The {\it real power} of the new concept would only emerge
in cases that {\it only} computers can do. But since we still
need humans to program the computer, the programmer (in this case
myself, but hopefully I would be joined by others who would use
this method in the future) would need to really understand and
internalize the concept, before he or she (and soon, also it)
can write the software. The best way to understand new concepts
and methods is to work out a few examples by hand. These examples could also
serve as test-cases for the computer-programs.
 
{\bf Example 1: Ordinary Partitions}
 
Here the digraph consists of one vertex-type, parameterized by
positive integers $v(a)$, with weight $a$.  A partition 
$a_1 \leq a_2 \leq \dots \leq a_k$ can
be represented as a path $v(a_1) \rightarrow \dots \rightarrow v(a_k)$.
Let's call the catalytic variable $x$; the {\it mishkal} of such 
a path is then $q^{a_1 + \dots a_k} x^{a_k}$.
Out of $v(b)$ we may go to any $v(a)$ with $a \geq b$.
Since we only have here one vertex-type, the umbral matrix is
a $1 \times 1$ matrix $(\P_{1,1})$, and
the operator $\P_{1,1}$ acts on monomials $x^b$ by:
$$
x^b \rightarrow \sum_{a \geq b} (qx)^a= { {(qx)^b} \over {1-qx}} \quad,
$$
which, extending linearly, implies that
$$
\P_{1,1} f(x) = { {f(qx)} \over {1-qx} } \quad .
$$
 
The Umbral Scheme is thus
$$
f(x)={ {qx} \over {1-qx} }+ { {f(qx)} \over {1-qx} } \quad ,
$$
 
which, in this simple case, immediately implies that
$g(x)=1+f(x)$ satisfies
$$
g(x)={ {g(qx)} \over {1-qx} } \quad ,
$$
and hence
$$
g(x)=\prod_{i=1}^{\infty} {{1} \over {1-q^i x}} \quad,
$$
and finally, setting the catalyst variable, $x$, to $1$,
we get a new proof of Euler's generating function for integer-partitions,
$g(1)=$
$$
\prod_{i=1}^{\infty} {{1} \over {1-q^i}} \quad .
$$
 
{\bf Example 2: 2-Rowed Plane Partitions}
 
Recall that a 2-rowed plane-partition, with $r$ columns is a $2 \times r$
array of non-negative integers
$$
\matrix{
a_{1,1} & a_{1,2} & \dots& a_{1,r}\cr
a_{2,1} & a_{2,2} & \dots& a_{2,r}\cr} \quad,
$$
such that $a_{i,1} \geq a_{i,2} \geq \dots \geq a_{i,r} \geq 0$,
for $i=1,2$, and $a_{1,j} \geq a_{2,j} \geq 0$, for $j=1, \dots, r$.
Note that we allow $0$, so that even the all-zero-matrix, for example,
is being counted. The weight of a plane partition is the sum of
its entries, and in order to keep track of the number of columns,
we will use the letter $t$.
By (a special case of)
MacMahon's box theorem, the weight-enumerator of 2-rowed 
plane-partitions:
$$
\sum_{A} q^{\vert A \vert} t^{\# columns(A)} , \quad
$$
where the sum ranges over all $2$-rowed plane partitions,
equals:
$$
\sum_{r=0}^{\infty} {{(1-q) } \over {(q)_{r}(q)_{r+1}} }t^r \quad .
\eqno(Percy)
$$
 
Using the present approach, we should be able to rederive the
full expansion of $(Percy)$,
but at this stage we only want to illustrate the
concept, so we will be content to show how Maple can generate
the first $R$ terms of $(Percy)$, for any specified $R$.
 
Now the digraph still only consists of one vertex-type, 
but it is parameterized by {\it ordered pairs}, of integers,
$(a_1,a_2)$, where $a_1 \geq a_2 \geq 0$. 
From a vertex $v(b_1,b_2)$ we may go to 
$v(a_1,a_2)$, satisfying $a_1 \geq a_2 \geq 0$, and
$a_1 \geq b_1, a_2 \geq b_2$. So there is a natural
one-to-one correspondence between $r$-vertex paths
on this infinite digraph, and $2 \times r$ plane partitions.
Let's call the catalytic variables $x_1,x_2$.
Again, we only have here one vertex-type, so the umbral matrix is
a $1 \times 1$ matrix $(\P_{1,1})$, and
the operator $\P_{1,1}$ acts on monomials $x_1^{b_1}x_2^{b_2}$ by:
$$
x_1^{b_1}x_2^{b_2} \,\,
 \rightarrow \,\, t\sum_
{
{{a_1 \geq a_2 \geq 0}, \atop {a_1 \geq b_1, a_2 \geq b_2}}
}
(qx_1)^{a_1} (qx_2)^{a_2} 
$$
$$
=t\sum_{a_2=b_2}^{b_1-1}\sum_{a_1=b_1}^{\infty}(qx_1)^{a_1} (qx_2)^{a_2} 
+
t\sum_{a_2=b_1}^{\infty}\sum_{a_1=a_2}^{\infty}(qx_1)^{a_1} (qx_2)^{a_2} 
$$
$$
=t{{(qx_1)^{b_1}} \over {1-qx_1}}
\left [ {{(qx_2)^{b_2}- (qx_2)^{b_1} } \over {1-qx_2}} \right ]+
{{t} \over {1-qx_1}} \sum_{a_2=b_1}^{\infty} (qx_2)^{a_2}(q x_1)^{a_2}
$$
$$
=t{{(qx_1)^{b_1}(qx_2)^{b_2}- (qx_1)^{b_1}(qx_2)^{b_1} } \over 
{(1-qx_1)(1-qx_2)}} +
t{ {(q^2x_1x_2)^{b_1}}  \over 
{(1-qx_1)(1-q^2x_1x_2)}} \quad .
$$
Extending by linearity, we see that $\P_{1,1}$ is the umbra:
$$
\P_{1,1} f(x_1,x_2) = 
t{{f(qx_1,qx_2)-f(q^2x_1x_2,1)} \over
 {(1-qx_1)(1-qx_2)}}
+
t{{f(q^2x_1x_2,1)} \over
 {(1-qx_1)(1-q^2x_1x_2)}} \quad .
$$
The Umbral Scheme is thus
$$
F(x_1,x_2)={ {t} \over {(1-qx_1)(1-q^2x_1x_2)} }+ 
t{{F(qx_1,qx_2)-F(q^2x_1x_2,1)} \over
 {(1-qx_1)(1-qx_2)}}
+
t{{F(q^2x_1x_2,1)} \over
 {(1-qx_1)(1-q^2x_1x_2)}} \quad .
\eqno(UMP2)
$$
Starting with $F={ {t} \over {(1-qx_1)(1-q^2x_1x_2)}}$,
and iteratively plugging into the right side of $UMP2$,
and expanding with respect to increasingly 
higher powers of $t$, would yield
the MacMahon's expansion $(Percy)$ to any desired ``accuracy''.
 
{\bf Example 3: Counting Compositions without double-descents}
 
We would like to find the generating function 
$$
\sum_{n=0}^{\infty} A(n)q^n ,\quad
$$
where $A(n)$ is the number of vectors of positive integers
$(a_1, \dots, a_r)$ (where $r\geq 0$), such that
$a_1+ \dots +a_r=n$ and we are not allowed to have
a double descent $a_i>a_{i+1}>a_{i+2}$ for any $i=1, \dots, r-2$.
For example $(4,5,6,4,4,6,5,7)$ is allowed, but
$(4,5,6,4,2,5,6,4)$ is not allowed.
 
To model this as paths on a digraph, we have to introduce two kinds
of vertices $u$ (up) corresponding to the situation where the
entry before it is smaller, including the case when it is at the very
beginning; and vertices $d$ (down) corresponding to the situation
where the entry before it is bigger. In the digraph, the followers
of $u(b)$ are $u(a)$ with $a \geq b$, as well as $d(a)$
with $ 1 \leq a <b$. The followers of $d(b)$ may only be
$u(a)$ with $a \geq b$.
 
Hence the operator $\P_{u,u}$ acts on a monomial by:
$$
x^a \, \rightarrow \, \sum_{b=a}^{\infty} (qx)^b =
{{(qx)^a} \over {1-qx}} \quad,
$$
the operator $\P_{u,d}$ acts on a monomial by:
$$
x^a \, \rightarrow \, \sum_{b=1}^{a-1} (qx)^b =
{{qx-(qx)^a} \over {1-qx}} \quad,
$$
the operator $\P_{d,u}$ acts on a monomial by:
$$
x^a \, \rightarrow \, \sum_{b=a}^{\infty} (qx)^b =
{{(qx)^a} \over {1-qx}} \quad,
$$
while $\P_{d,d}$ is $0$.
By linearity, the operators extend to any formal power series in $x$
by
$$
P_{u,u} [f(x)]= {{f(qx)} \over {1-qx}} \quad,
$$
$$
P_{u,d} [f(x)]= {{qxf(1)-f(qx)} \over {1-qx}} \quad,
$$
$$
P_{d,u} [f(x)]= {{f(qx)} \over {1-qx}} \quad,
$$
$$
P_{d,d} [f(x)]= 0 \quad .
$$
 
Let $F_u(x)$ and $F_d(x)$ be as above, where they
also depend on $q$, of course. The Umbral Scheme is
$$
F_u(x)={{qx} \over {1-qx}} + {{F_u(qx)} \over {1-qx}}+
{{F_d(qx)} \over {1-qx}} \quad,
$$
$$
F_d(x)={{qxF_u(1)-F_u(qx)} \over {1-qx}} \quad .
$$
The desired quantity is $F_d(1)+F_u(1)$.
 
{\bf ROTA: The Accompanying Maple Package}
 
The Maple package {\tt ROTA} is available from this 
series of article's web-page \hfill\break
{\tt http://www.math.temple.edu/\Tilde zeilberg/utm.html}. \hfill \break 
The main procedure is {\tt ApplyUmSc(UmSch,q,n,vars)} .
It inputs an umbral scheme, {\tt UmSch}, a variable
{\tt q}, and an integer {\tt n}, and a set of variables,
{\tt vars} (the catalytic variables).
It outputs the series expansion, in the variable {\tt q},
up to the term {\tt q**n} of the computed generating function,
both with the catalytic variables retained, and with them
made $1$.
For example if the umbral scheme is
$$
UMP1:=
[ \{1\}, \{1\}, [[\{[1/(1-q*x), [0], [q*x]]\}]], [q*x/(1-q*x)], [[x]]]: \quad,
$$
then
{\tt ApplyUmSc(UMP1,q,7,$\{$x$\}$)[2];} yields
{\tt [1,2,3,5,7,11,15] }.
 
{\tt ROTA} also contains five sample umbral schemes:
{\tt UMP1} (displayed right above),
{\tt UMP2}, featured in example $2$ above,
{\tt UMW}, that counts compositions with no double descents
(example 3 above), as well as {\tt UmSch1} and {\tt UmSch2},
to be discussed in [Z3].
 
{\bf Future Plans}
 
I hope to apply  the Umbral Transfer-Matrix Method in
forthcoming sequels to the present article ([Z2][Z3][Z4][Z5]).
 
{\bf Final Remark}
 
The scenario in [Z] can be viewed as a very special case of the present
set-up, namely, the case where the monomials $m_1, \dots, m_r$
featuring in the definition of an atomic Rota operator, are all equal to
$1$. As was shown in [Z], in this case the generating function is always
computable explicitly, and furthermore is a rational function.
 
{\bf REFERENCES}
 
[KR] Joseph P.S. Kung and Gian-Carlo Rota,
{\it The invariant theory of binary quadratic forms},
Bulletin of the American Mathematical Society
(New Series) {\bf 10}(1984), 27-85.
 
[LR] Daniel E. Loeb and Gian-Carlo Rota, {\it Formal power series
of logarithmic type}, Advances in Mathematics {\bf 75} (1989), 1-118.
 
[RR] Steven M. Roman and Gian-Carlo Rota, {\it The Umbral Calculus},
Advances in Mathematics {\bf 27} (1978), 95-188.
 
[R] Gian-Carlo Rota, {\it The number of partitions of a set},
American Mathematical Monthly {\bf 71} (1964), 498-504.
Reprinted in: ``Gian-Carlo Rota on Combinatorics'', Joseph P.S. Kung,
ed., Birkhauser, 1995, 111-117.
 
[Z] Doron Zeilberger, {\it Automated counting of Lego Towers},
Journal of Difference Equations and Applications,
{\bf 5} (1999), 323-334.
 
[Z0] Doron Zeilberger, {\it 
SYMBOL-CRUNCHING with the TRANSFER-MATRIX Method
In Order to Count
SKINNY Physical Creatures
}, preprint, available from Zeilberger's website.
 
[Z1] Doron Zeilberger,
{\it The Umbral Transfer-Matrix Method: I. Foundations},
this article.
 
[Z2] Doron Zeilberger,
{\it The Umbral Transfer-Matrix Method: II. Counting Plane and Solid
Partitions},
in preparation.
 
[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
 
 
 
 
 
