Florida Atlantic University right arrow Mathematical Sciences right arrows H. Niederhausen right arrows Research right arrow niederha@fau.edu

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: Rota

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 ($f$), linear functionals ($L$), and a certain class of (shift invariant) linear operators ($S$) on polynomials ($p$).
MATH
Common ground to the three concepts are special polynomial sequences, called Sheffer sequences. A polynomial sequence MATH is a sequence of polynomials MATH such that $\deg s_{m}=m$, $s_{0}\neq 0$. It is convenient to define $s_{m}=0$ for negative $m$. The coefficient ring $\QTR{Bbb}{K}$ is assumed to be of characteristic $0$. Usually it suffices to choose $\QTR{Bbb}{K}$ as MATH, the ring of polynomials in some weight parameter $\omega $. A formal power series $g(t)$ of order $1$ (i.e., MATH and MATH is a unit in $\QTR{Bbb}{K}$) will be called a delta series. We substitute the derivative operator $\QTR{cal}{D}$ for $t$ in a delta series, and obtain a shift-invariant linear operator $Q$ called a delta operator. The derivative $\QTR{cal}{D}$ itself is a delta operator, and like $\QTR{cal}{D}$ every delta operator $Q$ reduces degrees by one, and has its null-space equal to the constant polynomials. The solutions to the system of operator equations (recursion!)
MATH
are therefore only determined up to constants; every polynomial sequence MATH solving that system is a $Q~$- $~$Sheffer sequence (note that MATH is a Sheffer polynomial in the sense of Rota, Kahaner and Odlyzko [6]). Initial values determine the constants, and if the initial values are MATH, this special Sheffer sequence is called the $Q~$- $~$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 $Q$, and the $Q$-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 $\rightarrow $ and $\uparrow $, starting and ending at a common point without intersections in between, thus forming a polygon. In order to count the number $c_{2n}$ of staircase polygons with circumference $2n$, we actually enumerate truncated (by a line with slope $-1$) staircase polygons which have a diagonal gap $i>0$ (from truncation) and call their number MATH if the remaining piece of the original staircase circumference is $2i+2m$. Note that $2i$ is the smallest possible remaining circumference of a truncated staircase polygon with gap $i$, thus MATH. The picture below explains the terminology and shows what we mean by the "handles" of the truncated polygon.
MATH
If we move the truncation line one unit to the right, we lose the old handles, and the gap changes according to their direction,
MATH
The initial values MATH for $m>0$ guarantee that there always is a gap. The above recursion can be interpreted as a system of difference equations, and from MATH follows that the solution can be extended to a polynomial sequence MATH. Define the operator $B$ by linear extension of its action on the basis MATH, MATH for all $m$. The recursion MATH is equivalent to the operator identities
MATH
where $\nabla =1-E^{-1}$ is the backwards difference operator, a delta operator with basic sequence MATH. The Transfer Theorem will show that $B$ is also a delta operator, and its basic sequence is our solution sequence MATH because of the initial values MATH. The Transfer Formula expandsMATH as
MATH
( MATH stands for the coefficient of $t^{m}$ in $f\left( t\right) $), and also tells us the generating function
MATH
The total number $c_{2n}$ of staircase polygons of circumference $2n$ equals the number of truncated staircase polygons of circumference $2n-2$ and gap $1$,
MATH
(and old result by Levine), a Catalan number.

If necessary and possible, the initial conditions are formulated as a functional on MATH, and the Functional Expansion Theorem expands the Sheffer polynomials $s_{m}$ 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 $4\times n$ rectangle with $m$ squares of size $2\times 2$
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
MATH
are also in the scope of the Expansion Theorem. We find the basic solution (initial values MATH)
MATH

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 $\phi $ 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 $\QTR{cal}{D}$, and the first term in the delta series is invertible. For example, in the above differential equation the derivative operator $\QTR{cal}{D}$ is expressed as the delta series MATH, where $Qg_{m}=g_{m-1}$. We do not need to know more about $Q$ to find its basic sequence! If the initial values are more involved than MATH, 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 $L$ 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 $K[x][[t]]$$,$ 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.