Binomial type

• In consequence of this definition the binomial theorem can be stated by saying that the sequence { xⁿ : n = 0, 1, 2, ... } is of binomial type.
• The sequence of "lower factorials" is defined by

${\displaystyle (x)_{n}=x(x-1)(x-2)\cdot \cdots \cdot (x-n+1).}$

(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"

${\displaystyle x^{(n)}=x(x+1)(x+2)\cdot \cdots \cdot (x+n-1)}$

are a polynomial sequence of binomial type.

• The Abel polynomials

${\displaystyle p_{n}(x)=x(x-an)^{n-1}\,}$

are a polynomial sequence of binomial type.

• The Touchard polynomials

${\displaystyle p_{n}(x)=\sum _{k=1}^{n}S(n,k)x^{k}}$

where S(n, k) is the number of partitions of a set of size n into k 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 S(n, k ) are "Stirling numbers of the second kind". This sequence has a curious connection with the Poisson distribution: If X is a random variable with a Poisson distribution with expected value λ then E(Xⁿ) = p_n(λ). In particular, when λ = 1, we see that the nth moment of the Poisson distribution with expected value 1 is the number of partitions of a set of size n, called the nth Bell number. This fact about the nth moment of that particular Poisson distribution is "Dobinski's formula".

It can be shown that a polynomial sequence { p_n(x) : n = 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

${\displaystyle p_{n}(x)\mapsto np_{n-1}(x)}$

is shift-equivariant, and

• p₀(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.)

For any sequence a₁, a₂, a₃, ... of scalars, let

${\displaystyle p_{n}(x)=\sum _{k=1}^{n}B_{n,k}(a_{1},\dots ,a_{n-k+1})x^{k}}$

where B_n,k(a₁, ..., a_n−k+1) is the Bell polynomial. Then this polynomial sequence is of binomial type. Note that for each n ≥ 1,

${\displaystyle p_{n}'(0)=a_{n}.\,}$

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 { p_n(x) }_n of binomial type is determined by the sequence { p_n′(0) }_n, but those sources do not mention Bell polynomials.

This sequence of scalars is also related to the delta operator. Let

${\displaystyle P(t)=\sum _{n=1}^{\infty }{a_{n} \over n!}t^{n}.}$

Then

${\displaystyle P^{-1}\left({d \over dx}\right)\,}$

is the delta operator of this sequence.

For sequences a_n, b_n, n = 0, 1, 2, ..., define a sort of convolution by

${\displaystyle (a{\mathbin {\diamondsuit }}b)_{n}=\sum _{j=0}^{n}{n \choose j}a_{j}b_{n-j}.}$

Let ${\displaystyle a_{n}^{k\diamondsuit }\,}$ be the nth term of the sequence

${\displaystyle \underbrace {a{\mathbin {\diamondsuit }}\cdots {\mathbin {\diamondsuit }}a} _{k{\text{ factors}}}.\,}$

Then for any sequence a_i, i = 0, 1, 2, ..., with a₀ = 0, the sequence defined by p₀(x) = 1 and

${\displaystyle p_{n}(x)=\sum _{k=1}^{n}{a_{n}^{k\diamondsuit }x^{k} \over k!}\,}$

for n ≥ 1, is of binomial type, and every sequence of binomial type is of this form.

Polynomial sequences of binomial type are precisely those whose generating functions are formal (not necessarily convergent) power series of the form

${\displaystyle \sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n}=e^{xf(t)}}$

where f(t) is a formal power series 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

${\displaystyle f(t)=\sum _{n=1}^{\infty }{p_{n}\,'(0) \over n!}t^{n}.}$

The delta operator of the sequence is f⁻¹(D), so that

${\displaystyle f^{-1}(D)p_{n}(x)=np_{n-1}(x).}$

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 { p_n(x) : n = 0, 1, 2, 3, ... } and { q_n(x) : n = 0, 1, 2, 3, ... } are polynomial sequences, and

${\displaystyle p_{n}(x)=\sum _{k=0}^{n}a_{n,k}\,x^{k}.}$

Then the umbral composition p o q is the polynomial sequence whose nth term is

${\displaystyle (p_{n}\circ q)(x)=\sum _{k=0}^{n}a_{n,k}\,q_{k}(x)}$

(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 between delta operators and polynomial sequences of binomial type, also defined above, is a group isomorphism, in which the group operation on power series is formal composition of formal power series.

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

${\displaystyle p_{n}'(0)=\kappa _{n}=\,}$ the nth cumulant

and

${\displaystyle p_{n}(1)=\mu _{n}'=\,}$ the nth moment.

These are "formal" cumulants and "formal" moments, as opposed to cumulants of a probability distribution and moments of a probability distribution.

Let

${\displaystyle f(t)=\sum _{n=1}^{\infty }{\frac {\kappa _{n}}{n!}}t^{n}}$

be the (formal) cumulant-generating function. Then

${\displaystyle f^{-1}(D)\,}$

is the delta operator associated with the polynomial sequence, i.e., we have

${\displaystyle f^{-1}(D)p_{n}(x)=np_{n-1}(x).\,}$

The concept of binomial type has applications in combinatorics, probability, statistics, and a variety of other fields.

• List of factorial and binomial topics
• Binomial-QMF (Daubechies wavelet filters)

• 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 enumeration.

• di Bucchianico, Alessandro. Probabilistic and Analytical Aspects of the Umbral Calculus, Amsterdam, CWI, 1997.
• Weisstein, Eric W. "Binomial-Type Sequence". MathWorld.