THE UMBRAL TRANSFER-MATRIX METHOD: I. FOUNDATIONS

Doron ZEILBERGER ^{1}

In Fond Memory of Gian-Carlo ROTA (April 27, 1932- April 18, 1999)

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.

Priests and Prophets

According to cohen venavi, a classic Hebrew essay by Ekhad Ha-Am, there are two ways of serving God: Priest and Prophet. The priest is a very skilled technician who knows by heart the 613 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 vision, insight, and new unifying concepts. Also his uncanny realizations that some things are 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:

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 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 Forewords (this one to ”Species” by F. Bergeron, G. Labelle, and P. Leroux), he wrote:

“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”

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu

http://www.math.temple.edu/~zeilberg/ . March 30, 2000. Supported in part by the NSF.

While he was talking here about André Joyal’s species, I am sure that he was also referring to his own numerous clarifications of common sense notions. In particular that of the umbra.

The 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 linear functional. Indeed Rota’s seminal contribution, which like almost all major breakthroughs, is a posteriori obvious, was the mere REALIZATION that an Umbra is a linear functional.

Let’s recall Rota’s favorite example. Prove that

a_{n} = ∑_{k=0}^{n} \binom{n}{k}b_{k} ,  (1)

if and only if

b_{n} = ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}a_{k} .  (1′)

The classical umbral proof goes as follows. Let a = b + 1. Then by the binomial theorem

a^{n} = ∑_{k=0}^{n} \binom{n}{k}b^{k} ,  (2)

and also, since b = a − 1,

b^{n} = ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}a^{k} .  (2′)

Now just “lower the superscripts (powers) and make them subscripts”.

Rota’s rendition is as follows. Define a 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, . . .. By linearity, A(p(x)) = B(p(x+1)), for any polynomial p(x), and hence B(q(x)) = A(q(x−1)) for 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.

Hamming got it Backwards: The Purpose of Insight is Computation

Speaking of computations, many mathematicians feel the need to apologize for computing, and Hamming’s famous quip: “the purpose of computation is not numbers but insight” has deteriorated into a cliché. This is a hold-over of our 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 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 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, always be needed.

Why is the Concept of Umbra so Crucial

I will soon define the Umbral Transfer-Matrix Method, but before let me explain, in general terms, why the notion of the umbra is 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 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 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 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 polynomial time, series expansions for the combinatorial objects considered, and sometimes even to solve the induced system of mixed differential-q-equations explicitly, enabling us to get the generating function in some kind of closed form.

Weighted Finite-Parameter Infinite Directed Graphs

The Finite Transfer-Matrix method is used to weight-enumerate paths on a finite digraph, see [Z0] for a detailed exposition. Here, we will be considering directed graphs whose set of vertices, V, is 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 vertex-families, {v_{1}, …, v_{n}}, such that each family v_{i} is an l_{i}-parameter infinite family, parameterized by the l_{i} discrete variables (a_{1}, …, a_{l_{i}}), where (a_{1}, …, a_{l_{i}}) ranges over a well-defined subset D_{i} of {0, 1, 2, 3, …}^{l_{i}}. So the vertex set of our infinite digraph can be partitioned as follows

V = ⋃_{i=1}^{n} ⋃_{(a_{1},...,a_{l_{i}})∈D_{i}} v_{i}(a_{1}, …, a_{l_{i}}) .

We will also assume that for any pair of vertex types v_{i} and v_{j}, there are K(i, j) ≥ 0 families of edges, and for each of k = 1, …, K(i, j), the type-k edge coming out of vertex v_{i}(a_{1}, …, a_{l_{i}}) may wind up in any of the vertices v_{j}(b_{1}, …, b_{l_{j}}), where (b_{1}, …, b_{l_{j}}) may belong to a well-defined subset of D_{j}, let’s call it E_{i,j}^{(k)}(a_{1}, …, a_{l_{i}}). We also assume that every such edge has a certain weight given by a weight-function

W_{i,j}^{(k)}(a_{1}, …, a_{l_{i}}; b_{1}, …, b_{l_{j}}) .

The weight of a path P, W t(P), is the sum of the weights of its participating edges. We are interested in computing the weight-enumerator of all paths

∑_{P ∈P aths} q^{W t(P)} ,

either explicitly, and failing this, to have a polynomial-time algorithm for computing the series expansion, i.e. the first N terms of its power-series expansion, for any given N.

We now digress to define a Rota-Operator.

Definition of an Atomic Rota-Operator: An Atomic Rota operator from the ring of formal power series in r variables Z(q)(x_{1}, …, x_{r}) to the ring of formal power series in s variables Z(q)(y_{1}, …, 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}, …, x_{r})] = R(q, y_{1}, …, y_{s})D_{x_{1}}^{α_{1}} … D_{x_{r}}^{α_{r}}f(x_{1}, …, x_{r})|_{{x_{1}=m_{1},...,x_{r}=m_{r}}} ,  (ARO)

where R(x, q_{1}, …, x_{r}) is a rational function of all its arguments, D_{x_{1}}, …, D_{x_{r}} are the differentiation operators with respect to x_{1}, …, x_{r} respectively, α_{1}, …, α_{r} are non-negative integers, and m_{1}, …, m_{r} are each monomials in the variables (q, y_{1}, …, y_{s}).

An Example of an Atomic Rota Operator:

f(x_{1}, x_{2}) → \frac{q^{3}y_{1}y_{2}y_{3}}{(1 − qy_{1})(1 − q^{2}y_{1}y_{2}y_{3})}D_{x_{1}}D_{x_{2}}^{3}f(y_{1}y_{2}y_{3}, qy_{3}) .

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, [α_{1}, …, α_{r}], [m_{1}, …, m_{r}]] .

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]] .

Definition of a Rota Operator: A Rota Operator is a sum of Atomic Rota Operators. Maple Representation of Rota Operators The Rota operator P = P_{1} + … + P_{m}, where P_{1}, …, P_{m} are atomic Rota operators, is denoted by the set {P_{1}, …, P_{m}}. For example the Rota operator f(x) → 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: The Umbral Axiom For every pair of 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}, …, x_{l_{i}}) to Z(q)(y_{1}, …, y_{l_{j}}), defined on the basis of monomials by

x_{1}^{a_{1}} ⋯ x_{l_{i}}^{a_{l_{i}}} → ∑_{(b_{1},...,b_{l_{j}})∈E_{i,j}^{k}(a_{1},...,a_{l_{i}})} q^{W_{i,j}^{(k)}(a_{1},...,a_{l_{i}};b_{1},...,b_{l_{j}})}y_{1}^{b_{1}} ⋯ y_{l_{j}}^{b_{l_{j}}}

is an atomic Rota operator, let’s call it Q_{i,j}^{k}. Also, let’s define the transition-operator from vertices of type i to vertices of type j (1 ≤ i, j ≤ n), by

P_{i,j} := ∑_{k∈K(i,j)} Q_{i,j}^{k} .

which by our assumption are all Rota operators. Let’s define the mishkal of a path P, in our digraph, that ends with the vertex v_{i}(a_{1}, …, a_{l_{i}}) by

q^{W t(P)}x_{1}^{a_{1}} … x_{l_{i}}^{a_{l_{i}}} ,

and let’s define the total mishkal of all the paths that end in a type-i vertex by

F_{i}(q; x_{1}, …, x_{l_{i}}) := ∑_{P} mishkal(P) ,

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, …, n) satisfy the following system of n differential-functional equations

F_{j} = [j ∈ Start] + ∑_{i=1}^{n} P_{i,j}F_{i} .  (F undamentalSystem)

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

∑_{j∈F inish} F_{j}(q; 1, …, 1) .

Note that the variables x_{1}, …, x_{l_{i}} corresponding to the l_{i}-parameter vertex type i, for i = 1, …, n, serve as 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.

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

The Umbral Axiom for Vertex-Weighted Digraphs

For every pair of vertex types, v_{i}, v_{j}, the operator from Z(q)(x_{1}, …, x_{l_{i}}) to Z(q)(y_{1}, …, y_{l_{j}}), defined on the basis of monomials by

x_{1}^{a_{1}} ⋯ x_{l_{i}}^{a_{l_{i}}} → ∑_{j=1}^{n} ∑_{(b_{1},...,b_{l_{j}})∈D_{j}} K_{i,j}(a_{i}, b_{j})q^{W_{j}(b_{1},...,b_{l_{j}})}y_{1}^{b_{1}} ⋯ 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, …, n the formal power-series

I_{i}(q, x_{1}, …, x_{l_{i}}) := ∑_{(a_{1},...,a_{l_{i}})∈D_{i}} q^{W_{i}(a_{1},...,a_{l_{i}})}x_{1}^{a_{1}} ⋯ x_{l_{i}}^{a_{l_{i}}} ,

of 1 − vertex paths, are all rational functions. The analog of (F undamentalSystem) for Vertexweighted digraphs is:

F_{j} = [j ∈ Start] I_{j} + ∑_{i=1}^{n} P_{i,j}F_{i} .  (F undamentalSystemV W)

Both (F undamentalSystem) and (F undamentalSystemV W), have the form of an Umbral Scheme:

F_{i} = A_{i} + ∑_{j=1}^{n} Q_{i,j}F_{j} ,  (UmbralScheme)

where F_{j}(q, x_{1}, …, x_{l_{j}}) are the unknown formal-power series, and Q_{i,j} are explicit Rota operators, together with a subset of {1, 2, …, n}, S, and the desired quantity is the formal power-series

∑_{i∈S} F_{i}(q, 1, …, 1) ,

where in the argument of F_{i}, there are l_{i} 1’s. 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 q. Maple Representations of Umbral Schemes We will represent the Umbral Scheme (UmbralScheme) as a list of length 4:

[S, UmbralMatrix, InitialV ector, V ariablesLists] ,

where UmbralMatrix is the matrix of Rota operators

UmbralMatrix = [[Q_{1,1}, Q_{1,2}, …, Q_{1,n}], …, [Q_{n,1}, Q_{n,2}, …, Q_{n,n}]] .

In particular, the number of elements of UmbralMatrix, n, determines the number of vertex-types, that we will assume are called {1, 2, …, n}. S is the subset of {1, 2, …, n} mentioned above. InitialV ector is the vector of rational functions

InitialV ector = [A_{1}, …, A_{n}] .

Finally V ariablesLists is the list of variables that the F_{i} depend on (not counting q):

V ariablesLists = [[x_{1}, …, x_{l_{1}}], [x_{1}, …, x_{l_{2}}], …, [x_{1}, …, x_{l_{n}}]]

Note that we may use x_{1}, x_{2}, … for each of the argument sets of F_{i} (i = 1, …, n), i.e. we don’t have to invent new names, since these variables are local. VERY SIMPLE EXAMPLES THAT EVEN HUMANS CAN WORK OUT The real power of the new concept would only emerge in cases that 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.

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} ≤ a_{2} ≤ … ≤ a_{k} can be represented as a path v(a_{1}) → … → v(a_{k}). Let’s call the catalytic variable x; the mishkal of such a path is then q^{a_{1}+...a_{k}}x^{a_{k}}. Out of v(b) we may go to any v(a) with a ≥ b. Since we only have here one vertex-type, the umbral matrix is a 1 × 1 matrix (P_{1,1}), and the operator P_{1,1} acts on monomials x^{b} by:

x^{b} → ∑_{a≥b}(qx)^{a} = \frac{(qx)^{b}}{1 − qx} ,

which, extending linearly, implies that

P_{1,1}f(x) = \frac{f(qx)}{1 − qx} .

The Umbral Scheme is thus

f(x) = \frac{qx}{1 − qx} + \frac{f(qx)}{1 − qx} ,

which, in this simple case, immediately implies that g(x) = 1 + f(x) satisfies

g(x) = \frac{g(qx)}{1 − qx} ,

and hence

g(x) = ∏_{i=1}^{∞} \frac{1}{1 − q^{i}x} ,

and finally, setting the catalyst variable, x, to 1, we get a new proof of Euler’s generating function for integer-partitions, g(1) =

∏_{i=1}^{∞} \frac{1}{1 − q^{i}} .

Example 2: 2-Rowed Plane Partitions

Recall that a 2-rowed plane-partition, with r columns is a 2 × r array of non-negative integers

\begin{matrix}a_{1,1} & a_{1,2} & … & a_{1,r} \\ a_{2,1} & a_{2,2} & … & a_{2,r} \end{matrix} ,

such that a_{i,1} ≥ a_{i,2} ≥ … ≥ a_{i,r} ≥ 0, for i = 1, 2, and a_{1,j} ≥ a_{2,j} ≥ 0, for j = 1, …, 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:

∑_{A} q^{|A|}t^{#columns(A)},

where the sum ranges over all 2-rowed plane partitions, equals:

∑_{r=0}^{∞} \frac{(1 − q)}{(q)_{r}(q)_{r+1}} t^{r} .  (P ercy)

Using the present approach, we should be able to rederive the full expansion of (P ercy), 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 (P ercy), for any specified R.

Now the digraph still only consists of one vertex-type, but it is parameterized by ordered pairs, of integers, (a_{1}, a_{2}), where a_{1} ≥ a_{2} ≥ 0. From a vertex v(b_{1}, b_{2}) we may go to v(a_{1}, a_{2}), satisfying a_{1} ≥ a_{2} ≥ 0, and a_{1} ≥ b_{1}, a_{2} ≥ b_{2}. So there is a natural one-to-one correspondence between r-vertex paths on this infinite digraph, and 2 × 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 × 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}} → t ∑_{{a_{1}≥a_{2}≥0, \atop a_{1}≥b_{1},a_{2}≥b_{2}}} (qx_{1})^{a_{1}}(qx_{2})^{a_{2}}

= t ∑_{a_{2}=b_{2}}^{b_{1}−1} ∑_{a_{1}=b_{1}}^{∞}(qx_{1})^{a_{1}}(qx_{2})^{a_{2}} + t ∑_{a_{2}=b_{1}}^{∞} ∑_{a_{1}=a_{2}}^{∞}(qx_{1})^{a_{1}}(qx_{2})^{a_{2}}

= t\frac{(qx_{1})^{b_{1}}}{1 − qx_{1}} [\frac{(qx_{2})^{b_{2}} − (qx_{2})^{b_{1}}}{1 − qx_{2}} ] + \frac{t}{1 − qx_{1}} ∑_{a_{2}=b_{1}}^{∞}(qx_{2})^{a_{2}}(qx_{1})^{a_{2}}

= t\frac{(qx_{1})^{b_{1}}(qx_{2})^{b_{2}} − (qx_{1})^{b_{1}}(qx_{2})^{b_{1}}}{(1 − qx_{1})(1 − qx_{2})} + t\frac{(q^{2}x_{1}x_{2})^{b_{1}}}{(1 − qx_{1})(1 − q^{2}x_{1}x_{2})} .

Extending by linearity, we see that P_{1,1} is the umbra:

P_{1,1}f(x_{1}, x_{2}) = t\frac{f(qx_{1}, qx_{2}) − f(q^{2}x_{1}x_{2}, 1)}{(1 − qx_{1})(1 − qx_{2})} + t\frac{f(q^{2}x_{1}x_{2}, 1)}{(1 − qx_{1})(1 − q^{2}x_{1}x_{2})} .

The Umbral Scheme is thus

F (x_{1}, x_{2}) = \frac{t}{(1 − qx_{1})(1 − q^{2}x_{1}x_{2})} + t\frac{F (qx_{1}, qx_{2}) − F (q^{2}x_{1}x_{2}, 1)}{(1 − qx_{1})(1 − qx_{2})} + t\frac{F (q^{2}x_{1}x_{2}, 1)}{(1 − qx_{1})(1 − q^{2}x_{1}x_{2})} .

(UMP 2)

Starting with F = \frac{t}{(1−qx_{1})(1−q^{2}x_{1}x_{2})}, and iteratively plugging into the right side of UMP 2, and expanding with respect to increasingly higher powers of t, would yield the MacMahon’s expansion (P ercy) to any desired “accuracy”.

Example 3: Counting Compositions without double-descents

We would like to find the generating function

∑_{n=0}^{∞} A(n)q^{n},

where A(n) is the number of vectors of positive integers (a_{1}, …, a_{r}) (where r ≥ 0), such that a_{1} + … + 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, …, 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 ≥ b, as well as d(a) with 1 ≤ a < b. The followers of d(b) may only be u(a) with a ≥ b.

Hence the operator P_{u,u} acts on a monomial by:

x^{a} → ∑_{b=a}^{∞}(qx)^{b} = \frac{(qx)^{a}}{1 − qx} ,

the operator P_{u,d} acts on a monomial by:

x^{a} → ∑_{b=1}^{a−1}(qx)^{b} = \frac{qx − (qx)^{a}}{1 − qx} ,

the operator P_{d,u} acts on a monomial by:

x^{a} → ∑_{b=a}^{∞}(qx)^{b} = \frac{(qx)^{a}}{1 − qx} ,

while P_{d,d} is 0. By linearity, the operators extend to any formal power series in x by

P_{u,u}[f(x)] = \frac{f(qx)}{1 − qx} ,

P_{u,d}[f(x)] = \frac{qxf(1) − f(qx)}{1 − qx} ,

P_{d,u}[f(x)] = \frac{f(qx)}{1 − qx} ,

P_{d,d}[f(x)] = 0 .

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) = \frac{qx}{1 − qx} + \frac{F_{u}(qx)}{1 − qx} + \frac{F_{d}(qx)}{1 − qx} ,

F_{d}(x) = \frac{qxF_{u}(1) − F_{u}(qx)}{1 − qx} .

The desired quantity is F_{d}(1) + F_{u}(1).

ROTA: The Accompanying Maple Package

The Maple package ROTA is available from this series of article’s web-page

http://www.math.temple.edu/~zeilberg/utm.html.

The main procedure is ApplyUmSc(UmSch,q,n,vars) . It inputs an umbral scheme, UmSch, a variable q, and an integer n, and a set of variables, vars (the catalytic variables). It outputs the series expansion, in the variable q, up to the term 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

UMP 1 := [{1}, {1}, [[{[1/(1 − q ∗ x), [0], [q ∗ x]]}]], [q ∗ x/(1 − q ∗ x)], [[x]]] : ,

then ApplyUmSc(UMP1,q,7,{x})[2]; yields [1,2,3,5,7,11,15] .

ROTA also contains five sample umbral schemes: UMP1 (displayed right above), UMP2, featured in example 2 above, UMW, that counts compositions with no double descents (example 3 above), as well as UmSch1 and UmSch2, to be discussed in [Z3].

Future Plans

I hope to apply the Umbral Transfer-Matrix Method in forthcoming sequels to the present article ([Z2][Z3][Z4][Z5]).

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}, …, 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.

REFERENCES

[KR] Joseph P.S. Kung and Gian-Carlo Rota, The invariant theory of binary quadratic forms, Bulletin of the American Mathematical Society (New Series) 10(1984), 27-85.

[LR] Daniel E. Loeb and Gian-Carlo Rota, Formal power series of logarithmic type, Advances in Mathematics 75 (1989), 1-118.

[RR] Steven M. Roman and Gian-Carlo Rota, The Umbral Calculus, Advances in Mathematics 27 (1978), 95-188.

[R] Gian-Carlo Rota, The number of partitions of a set, American Mathematical Monthly 71 (1964), 498-504. Reprinted in: “Gian-Carlo Rota on Combinatorics”, Joseph P.S. Kung, ed., Birkhauser, 1995, 111-117.

[Z] Doron Zeilberger, Automated counting of Lego Towers, Journal of Difference Equations and Applications, 5 (1999), 323-334.

[Z0] Doron Zeilberger, SYMBOL-CRUNCHING with the TRANSFER-MATRIX Method In Order to Count SKINNY Physical Creatures , preprint, available from Zeilberger’s website.

[Z1] Doron Zeilberger, The Umbral Transfer-Matrix Method: I. Foundations, this article.

[Z2] Doron Zeilberger, The Umbral Transfer-Matrix Method: II. Counting Plane and Solid Partitions, in preparation.

[Z3] Doron Zeilberger, The Umbral Transfer-Matrix Method: III. Counting Animals, in preparation.

[Z4] Doron Zeilberger, The Umbral Transfer-Matrix Method: IV. Counting Self-Avoiding Polygons and Walks, in preparation.

[Z5] Doron Zeilberger, The Umbral Transfer-Matrix Method: V. The Goulden-Jackson Cluster-Method for Infinitely Many Mistakes, in preparation.