The theory of binomial enumeration is variously called the calculus of
finite differences or the umbral calculus. This theory studies the analogies between
various
sequences of polynomials and the powers sequence
. The
subscript n in
was thought of as the shadow ( ``umbra'' means
``shadow'' in Latin, whence the name umbral calculus) of the
superscript n in
, and many parallels were discovered between
such sequences.
Take the example of the lower factorial polynomials
. Just as
counts the number of functions from an
n-element set to an x-element set,
counts the number of
injections. Just as the derivative maps
to
, the
forward difference operator maps
to
.
Just as also polynomials can be expressed in terms of
via
Taylor's theorem
Newton's theorem allows similar expressions for
where .
Just as
is expanded using the binomial
theorem
expands by Vandermonde's identity
This theory is quite classical with its roots in
the works of Barrow and Newton---expressed in the belief the some
polynomial sequences such as really were just like the
powers of x. Nevertheless, many doubts arose as to the
correctness of such informal reasoning, despite various (see e.g., [7])
attempts to
set it on an axiomatic base.
The contribution of Rota's school was to first set umbral calculus on a firm logical foundation by using operator methods [67,106]. That being done, sequences of polynomials of binomial type
could be for once studied systematically rather than as a collection
of isolated yet philosophically similar results.
The sister sequence of divided powers
then
obeys the identity
Given any species of combinatorial structures (or
quasi-species), let be the number of functions from an
n-element set to an x-element set enriched by this species. A
function is enriched by
associating a (weighted) structure with each of its fibers.
All sequences of binomial type arise in
this manner, and conversely, all such sequence are of binomial type.