In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a
polynomial sequence, i.e., a sequence of
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
s
indexed by non-negative
integers
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
in which the index of each polynomial equals its
degree, is said to be of binomial type if it satisfies the sequence of identities
:
Many such sequences exist. The
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of all such sequences forms a
Lie group
In mathematics, a Lie group (pronounced ) is a group (mathematics), group that is also a differentiable manifold, such that group multiplication and taking inverses are both differentiable.
A manifold is a space that locally resembles Eucli ...
under the operation of
umbral composition, explained below. Every sequence of binomial type may be expressed in terms of the
Bell polynomials. Every sequence of binomial type is a
Sheffer sequence (but most Sheffer sequences are not of binomial type). Polynomial sequences put on firm footing the vague 19th century notions of
umbral calculus.
Examples
* In consequence of this definition the
binomial theorem can be stated by saying that the sequence
is of binomial type.
* The sequence of "
lower factorials" is defined by
(In the theory of special
functions, this same notation denotes
upper factorials, but this present usage is universal among
combinatorialists.) The
product is understood to be 1 if ''n'' = 0, since it is in that case an
empty product
In mathematics, an empty product, or nullary product or vacuous product, is the result of multiplication, multiplying no factors. It is by convention equal to the multiplicative identity (assuming there is an identity for the multiplication operat ...
. This polynomial sequence is of binomial type.
* Similarly the "
upper factorials"
are a polynomial sequence of binomial type.
* The
Abel polynomialsare a polynomial sequence of binomial type.
* The
Touchard polynomialswhere
is the number of
partitions of a set of
size
Size in general is the Magnitude (mathematics), magnitude or dimensions of a thing. More specifically, ''geometrical size'' (or ''spatial size'') can refer to three geometrical measures: length, area, or volume. Length can be generalized ...
into
disjoint non-empty subsets
In mathematics, a set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subse ...
, is a polynomial sequence of binomial type.
Eric Temple Bell called these the "exponential polynomials" and that term is also sometimes seen in the literature. The
coefficients
In mathematics, a coefficient is a multiplicative factor involved in some term of a polynomial, a series, or any other type of expression. It may be a number without units, in which case it is known as a numerical factor. It may also be a ...
are "
Stirling numbers of the second kind". This sequence has a curious connection with the
Poisson distribution
In probability theory and statistics, the Poisson distribution () is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time if these events occur with a known const ...
: If
is a
random variable
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a Mathematics, mathematical formalization of a quantity or object which depends on randomness, random events. The term 'random variable' in its mathema ...
with a Poisson distribution with
expected value
In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first Moment (mathematics), moment) is a generalization of the weighted average. Informa ...
then
. In particular, when
, we see that the
th
moment of the Poisson distribution with expected value
is the number of partitions of a set of size
, called the
th
Bell number. This fact about the
th moment of that particular Poisson distribution is "
Dobinski's formula".
Characterization by delta operators
It can be shown that a polynomial sequence is of binomial type if and only if all three of the following conditions hold:
* The
linear transformation
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...
on the space of polynomials in ''x'' that is characterized by
is
shift-equivariant, and
* ''p''
0(''x'') = 1 for all ''x'', and
* ''p''
''n''(0) = 0 for ''n'' > 0.
(The statement that this operator is shift-equivariant is the same as saying that the polynomial sequence is a
Sheffer sequence; the set of sequences of binomial type is properly included within the set of Sheffer sequences.)
Delta operators
That linear transformation is clearly a
delta operator, i.e., a shift-equivariant linear transformation on the space of polynomials in ''x'' that reduces degrees of polynomials by 1. The most obvious examples of delta operators are
difference operators and
differentiation. It can be shown that every delta operator can be written as a
power series of the form
:
where ''D'' is differentiation (note that the
lower bound of
summation
In mathematics, summation is the addition of a sequence of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: functions, vectors, matrices, pol ...
is 1). Each delta operator ''Q'' has a unique sequence of "basic polynomials", i.e., a polynomial sequence satisfying
#
#
#
It was shown in 1973 by
Rota, Kahaner, and
Odlyzko, that a polynomial sequence is of binomial type if and only if it is the sequence of basic polynomials of some delta operator. Therefore, this paragraph amounts to a recipe for generating as many polynomial sequences of binomial type as one may wish.
Characterization by Bell polynomials
For any sequence ''a''
1, ''a''
2, ''a''
3, … of
scalars, let
:
where ''B''
''n'',''k''(''a''
1, …, ''a''
''n''−''k''+1) is the
Bell polynomial. Then this polynomial sequence is of binomial type. Note that for each ''n'' ≥ 1,
:
Here is the main result of this section:
Theorem: All polynomial sequences of binomial type are of this form.
A result in Mullin and Rota, repeated in Rota, Kahaner, and Odlyzko (see ''References'' below) states that every polynomial sequence
''n'' of binomial type is determined by the sequence
''n'', but those sources do not mention Bell polynomials.
This sequence of scalars is also related to the delta operator. Let
:
Then
:
where
, is the delta operator of this sequence.
Characterization by a convolution identity
For sequences ''a''
''n'', ''b''
''n'', ''n'' = 0, 1, 2, …, define a sort of
convolution
In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions f and g that produces a third function f*g, as the integral of the product of the two ...
by
:
Let
be the ''n''th term of the sequence
:
Then for any sequence ''a''
''i'', ''i'' = 0, 1, 2, ..., with ''a''
0 = 0, the sequence defined by ''p''
0(''x'') = 1 and
:
for ''n'' ≥ 1, is of binomial type, and every sequence of binomial type is of this form.
Characterization by generating functions
Polynomial sequences of binomial type are precisely those whose
generating functions are formal (not necessarily
convergent)
power series of the form
:
where ''f''(''t'') is a
formal power series
In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial su ...
whose
constant term is zero and whose first-degree term is not zero. It can be shown by the use of the power-series version of
Faà di Bruno's formula that
:
The delta operator of the sequence is the compositional inverse
, so that
:
A way to think about these generating functions
The coefficients in the product of two formal power series
:
and
:
are
:
(see also
Cauchy product
In mathematics, more specifically in mathematical analysis, the Cauchy product is the discrete convolution of two infinite series. It is named after the French mathematician Augustin-Louis Cauchy.
Definitions
The Cauchy product may apply to infin ...
). If we think of ''x'' as a parameter indexing a family of such power series, then the binomial identity says in effect that the power series indexed by ''x'' + ''y'' is the product of those indexed by ''x'' and by ''y''. Thus the ''x'' is the argument to a function that maps sums to products: an
exponential function
:
where ''f''(''t'') has the form given above.
Umbral composition of polynomial sequences
The set of all polynomial sequences of binomial type is a
group in which the group operation is "umbral composition" of polynomial sequences. That operation is defined as follows. Suppose and are polynomial sequences, and
:
Then the umbral composition ''p'' o ''q'' is the polynomial sequence whose ''n''th term is
:
(the subscript ''n'' appears in ''p''
''n'', since this is the ''n'' term of that sequence, but not in ''q'', since this refers to the sequence as a whole rather than one of its terms).
With the delta operator defined by a power series in ''D'' as above, the natural
bijection
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...
between delta operators and polynomial sequences of binomial type, also defined above, is a
group isomorphism
In abstract algebra, a group isomorphism is a function between two groups that sets up a bijection between the elements of the groups in a way that respects the given group operations. If there exists an isomorphism between two groups, then the ...
, in which the group operation on power series is formal composition of formal power series.
Cumulants and moments
The sequence κ
''n'' of coefficients of the first-degree terms in a polynomial sequence of binomial type may be termed the
cumulants of the polynomial sequence. It can be shown that the whole polynomial sequence of binomial type is determined by its cumulants, in a way discussed in the article titled ''
cumulant''. Thus
:
the ''n''th cumulant
and
:
the ''n''th moment.
These are "formal" cumulants and "formal"
moments, as opposed to cumulants of a
probability distribution
In probability theory and statistics, a probability distribution is a Function (mathematics), function that gives the probabilities of occurrence of possible events for an Experiment (probability theory), experiment. It is a mathematical descri ...
and moments of a probability distribution.
Let
:
be the (formal) cumulant-generating function. Then
:
is the delta operator associated with the polynomial sequence, i.e., we have
:
Applications
The concept of binomial type has applications in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
,
probability
Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
,
statistics
Statistics (from German language, German: ', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a s ...
, and a variety of other fields.
See also
*
List of factorial and binomial topics
*
Binomial-QMF (Daubechies wavelet filters)
References
*
G.-C. Rota, D. Kahaner, and
A. Odlyzko, "Finite Operator Calculus," ''Journal of Mathematical Analysis and its Applications'', vol. 42, no. 3, June 1973. Reprinted in the book with the same title, Academic Press, New York, 1975.
* R. Mullin and G.-C. Rota, "On the Foundations of Combinatorial Theory III: Theory of Binomial Enumeration," in ''Graph Theory and Its Applications'', edited by Bernard Harris, Academic Press, New York, 1970.
*
As the title suggests, the second of the above is explicitly about applications to
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
enumeration.
* di Bucchianico, Alessandro. ''Probabilistic and Analytical Aspects of the Umbral Calculus'', Amsterdam,
CWI, 1997.
* {{mathworld, urlname=Binomial-TypeSequence, title=Binomial-Type Sequence
Polynomials
Factorial and binomial topics