In mathematics, a polynomial sequence, i.e., a sequence of polynomials indexed by non-negative integers <math display="inline">\left\{0, 1, 2, 3, \ldots \right\}</math> in which the index of each polynomial equals its degree, is said to be of binomial type if it satisfies the sequence of identities

:<math>p_n(x+y)=\sum_{k=0}^n{n \choose k}\, p_k(x)\, p_{n-k}(y).</math>

Many such sequences exist. The set of all such sequences forms a Lie group 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 <math>\{x^n : n= 0, 1, 2, \ldots \}</math> is of binomial type.
  • The sequence of "lower factorials" is defined by <math display="block">(x)_n=x(x-1)(x-2)\cdot\cdots\cdot(x-n+1).</math> (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. This polynomial sequence is of binomial type.
  • Similarly the "upper factorials" <math display="block">x^{(n)}=x(x+1)(x+2)\cdot\cdots\cdot(x+n-1)</math> are a polynomial sequence of binomial type.
  • The Abel polynomials <math display="block">p_n(x)=x(x-an)^{n-1} </math> are a polynomial sequence of binomial type.
  • The Touchard polynomials <math display="block">p_n(x)=\sum_{k=0}^n S(n,k)x^k</math> where <math>S(n,k)</math> is the number of partitions of a set of size <math>n</math> into <math>k</math> disjoint non-empty subsets, 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 <math>S(n,k)</math> are "Stirling numbers of the second kind". This sequence has a curious connection with the Poisson distribution: If <math>X</math> is a random variable with a Poisson distribution with expected value <math>\lambda</math> then <math>E(X^n)= p_n(\lambda)</math>. In particular, when <math>\lambda = 1</math>, we see that the <math>n</math>th moment of the Poisson distribution with expected value <math>1</math> is the number of partitions of a set of size <math>n</math>, called the <math>n</math>th Bell number. This fact about the <math>n</math>th moment of that particular Poisson distribution is "Dobinski's formula".

Characterization by delta operators

It can be shown that a polynomial sequence { p<sub>n</sub>(x): n&nbsp;= 0, 1, 2, … } is of binomial type if and only if all three of the following conditions hold:

  • The linear transformation on the space of polynomials in x that is characterized by <math display="block">p_n(x) \mapsto n p_{n-1}(x)</math> is shift-equivariant, and
  • p<sub>0</sub>(x) = 1 for all x, and
  • p<sub>n</sub>(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: <math>Q=\sum_{n=1}^\infty c_n D^n</math> where D is differentiation (note that the lower bound of summation is 1). Each delta operator Q has a unique sequence of "basic polynomials", i.e., a polynomial sequence satisfying

  1. <math>p_0(x)=1,</math>
  2. <math>p_n(0)=0\quad{\rm for\ }n\geq 1,{\rm\ and}</math>
  3. <math>Qp_n(x)=np_{n-1}(x). </math>

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<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, … of scalars, let

:<math>p_n(x)=\sum_{k=1}^n B_{n,k}(a_1,\dots,a_{n-k+1}) x^k</math>

where B<sub>n,k</sub>(a<sub>1</sub>, …, a<sub>n&minus;k+1</sub>) is the Bell polynomial. Then this polynomial sequence is of binomial type. Note that for each n ≥ 1,

:<math>p_n'(0)=a_n.</math>

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