# A Short Introduction to Umbral Calculus

If part of the formulas are cut off in you browser, try increasing the text size under the "View" option.

Until the middle of the twentieth century Umbral Calculus, or Blissard Calculus, was nothing but a clever (if not magical) tool for manipulating sums, especially for expanding one sequence of special numbers in terms of another. Two papers appeared in the early 1970's that resurrected the dormant Umbral Calculus, and initiated numerous subsequent studies:

• On the Foundations of Combinatorial Theory III: Theory of Binomial Enumeration, by Ron Mullin (now a member of our department) and Gian-Carlo Rota in 1970 [4], and

• On the foundations of combinatorial theory VIII: Finite operator calculus, by G.-C. Rota, D. Kahaner, and A. Odlyzko in 1973 [6].

Hence Umbral Calculus was freed of its magical aura and put on a solid basis. To get a feel for the diversity of work building up on this foundation, I suggest to browse through the selected survey of umbral calculus, with over 500 references, compiled for the web by A. Di Bucchianico and D.E. Loeb (1995, last updated 2000) [1]. The survey also contains an overview over Umbral Calculus, from a different perspective than this introduction.

After 1973, Umbral Calculus branched out in many directions, some purely algebraic (the Hopf algebra interpretation), some more linear algebra oriented, some pointing to optimization theory, and some (including Rota's own late contributions) returning close to the original concept of umbrae. Ira Gessel's recent paper [3] is a splendid example of the applicability of this very elementary approach.

My own work on and with Umbral Calculus is based on J. M. Freeman's (emeritus of our department) generalization [2] of Rota's finite operator calculus, the Method of Transforms. The focus is on connections to other areas of mathematics, with an emphasis on combinatorial enumeration. The latter is my preferred application, because of the unifying Umbral Calculus approach to solving linear recursions.

Further details on how to apply Umbral Calculus are necessarily more technical in nature. The following exposition is adapted from the introduction to my recent paper Rota's Umbral Calculus and Recursions [5].

# More Finite Operator Calculus

In the finite operator (linear algebra) approach to Umbral Calculus we exploit the isomorphism between formal power series (), linear functionals (), and a certain class of (shift invariant) linear operators () on polynomials ().

Common ground to the three concepts are special polynomial sequences, called Sheffer sequences. A polynomial sequence is a sequence of polynomials such that , . It is convenient to define for negative . The coefficient ring is assumed to be of characteristic . Usually it suffices to choose as , the ring of polynomials in some weight parameter . A formal power series of order (i.e., and is a unit in ) will be called a delta series. We substitute the derivative operator for in a delta series, and obtain a shift-invariant linear operator called a delta operator. The derivative itself is a delta operator, and like every delta operator reduces degrees by one, and has its null-space equal to the constant polynomials. The solutions to the system of operator equations (recursion!)

are therefore only determined up to constants; every polynomial sequence solving that system is a - Sheffer sequence (note that is a Sheffer polynomial in the sense of Rota, Kahaner and Odlyzko [6]). Initial values determine the constants, and if the initial values are , this special Sheffer sequence is called the - basic sequence. Umbral Calculus can be used as a tool for solving recursions, if the exact solutions to such recursions are Sheffer sequences. In that case, the recursion will lead to an operator equation involving the (unknown) delta operator , and the -basic sequence is expanded with the help of Transfer Formulas. It is rare that an interesting combinatorial problem can be solved by a basic sequence, but the following example is an exception.

Example

A staircase polygon (parallelogram polyomino) can be viewed as a pair of lattice paths with steps and , starting and ending at a common point without intersections in between, thus forming a polygon. In order to count the number of staircase polygons with circumference , we actually enumerate truncated (by a line with slope ) staircase polygons which have a diagonal gap (from truncation) and call their number if the remaining piece of the original staircase circumference is . Note that is the smallest possible remaining circumference of a truncated staircase polygon with gap , thus . The picture below explains the terminology and shows what we mean by the "handles" of the truncated polygon.

If we move the truncation line one unit to the right, we lose the old handles, and the gap changes according to their direction,

The initial values for guarantee that there always is a gap. The above recursion can be interpreted as a system of difference equations, and from follows that the solution can be extended to a polynomial sequence . Define the operator by linear extension of its action on the basis , for all . The recursion is equivalent to the operator identities

where is the backwards difference operator, a delta operator with basic sequence . The Transfer Theorem will show that is also a delta operator, and its basic sequence is our solution sequence because of the initial values . The Transfer Formula expands as

( stands for the coefficient of in ), and also tells us the generating function

The total number of staircase polygons of circumference equals the number of truncated staircase polygons of circumference and gap ,

(and old result by Levine), a Catalan number.

If necessary and possible, the initial conditions are formulated as a functional on , and the Functional Expansion Theorem expands the Sheffer polynomials in terms of the basic sequence. We call this the "bottom up" approach: Starting with simple "building blocks" (in combinatorics they usually are binomial coefficients) we construct the basic sequence, and from this more advanced material the exact solution is put together such that the initial conditions are satisfied. In the more commonly applied "top down" approach a generating function identity is solved, and the exact solution may be obtained by finding coefficients. We will show that in many applications Umbral Calculus provides the generating function too; the more interesting problems may be those where that is not the case. Some examples that can be approached via Umbral Calculus:.

 # of variables Topic One Generalized elevated Schröder paths Two Staircase polygons Two Tiling a rectangle with squares of size Two Lattice paths with infinite step set and special access Three A lattice walk with frequent stops

All the above examples come from combinatorics and are discrete. However, recursions like

are also in the scope of the Expansion Theorem. We find the basic solution (initial values )

Umbral Calculus tools can be applied to delta recursions, i.e., recursions that are solved by polynomial sequences, and lead to operator identities where some (known) delta operator is expressed as a delta series in some other (unknown) delta operator. The coefficients of the delta series may be linear operators themselves, as long as they can be expanded as power series in , and the first term in the delta series is invertible. For example, in the above differential equation the derivative operator is expressed as the delta series , where . We do not need to know more about to find its basic sequence! If the initial values are more involved than , we will in general no longer be able to solve the system. However, the Functional Expansion Theorem can be used for expansions of the solution if the initial values can be expressed in terms of a functional that does not vanish on constants.

# Some References

1. Di Bucchianico,A. and Loeb, D.E. (1995, last updated 2000) A selected survey of umbral calculus, Dynamical Survey 3, Electronic J. of Combinatorics.

2. Freeman, J.M. (1985). Transforms of operators on Congr. Numerantium 48, 115-132.

3. Gessel, I. (2001). Applications of the classical umbral calculus. To appear in Algebra Universalis. dvi file, pdf file.

4. Mullin, R. and Rota, G. C. (1970). On the Foundations of Combinatorial Theory III: Theory of Binomial Enumeration, in B. Harris (ed.). Graph Theory and Its Applications, Academic Press, New York, pp.167-213

5. Niederhausen, H. (2002). Rota's Umbral Calculus and Recursions. To appear in Algebra Universalis.

6. Rota, G.-C., Kahaner, D., and Odlyzko, A. (1973). On the Foundations of Combinatorial Theory VIII: Finite operator calculus, J. Math. Anal. Appl. 42, 684-760

This document created by Scientific WorkPlace 4.1.