Editing Binomial type

{{Use American English|date = March 2019}}
{{Short description|Type of polynomial sequence}}
{{no footnotes|date=March 2013}}
In [[mathematics]], a [[polynomial sequence]], i.e., a sequence of [[polynomial]]s [[indexed family|indexed]] by non-negative [[Integer|integers]] <math display="inline">\left\{0, 1, 2, 3, \ldots \right\}</math> in which the index of each polynomial equals its [[Degree of a polynomial|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 (mathematics)|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 polynomial]]s. 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 factorial]]s" 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 [[Function (mathematics)|functions]], this same notation denotes [[upper factorial]]s, but this present usage is universal among [[combinatorics|combinatorialists]].) The [[Product (mathematics)|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.{{sfn|Roman|2008|p=488-489|loc=ch. 19}}
* Similarly the "[[upper factorial]]s"<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 [[Partition of a set|partitions of a set]] of [[cardinality|size]] <math>n</math> into <math>k</math> [[Disjoint sets|disjoint]] [[non-empty]] [[Subset|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 [[Coefficient|coefficients]] <math>S(n,k)</math> are "[[Stirling number]]s 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 [[Factorial moment|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 numbers|Bell number]].  This fact about the <math>n</math>th moment of that particular Poisson distribution is "[[Bell numbers|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 operator]]s{{sfn|Roman|2008|p=488-489|loc=ch. 19}} and [[Differentiation (calculus)|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
#<math>p_0(x)=1,</math>
#<math>p_n(0)=0\quad{\rm for\ }n\geq 1,{\rm\ and}</math>
#<math>Qp_n(x)=np_{n-1}(x). </math>
It was shown in 1973 by [[Gian-Carlo Rota|Rota]], Kahaner, and [[Andrew Odlyzko|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 [[Scalar (mathematics)|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 polynomials|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 (see ''References'' below) states that every polynomial sequence {&nbsp;''p''<sub>''n''</sub>(''x'')&nbsp;}<sub>''n''</sub> of binomial type is determined by the sequence {&nbsp;''p''<sub>''n''</sub>&prime;(0)&nbsp;}<sub>''n''</sub>, but those sources do not mention Bell polynomials.

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

:<math>P(t)=\sum_{n=1}^\infty {a_n \over n!} t^n.</math>

Then

:<math>P^{-1}\left({d \over dx}\right),</math>

where <math>P^{-1}(P(x)) = P(P^{-1}(x)) = 1</math>, is the delta operator of this sequence.

==Characterization by a convolution identity==
For sequences ''a''<sub>''n''</sub>, ''b''<sub>''n''</sub>, ''n'' = 0, 1, 2, …, define a sort of [[convolution]] by

:<math>(a \mathbin{\diamondsuit} b)_n = \sum_{j=0}^n {n \choose j} a_j b_{n-j}.</math>

Let <math>a_n^{k\diamondsuit}</math> be the ''n''th term of the sequence

:<math>\underbrace{a\mathbin{\diamondsuit}\cdots\mathbin{\diamondsuit} a}_{k\text{ factors}}.</math>

Then for any sequence ''a''<sub>''i''</sub>, ''i'' = 0, 1, 2, ..., with ''a''<sub>0</sub> = 0, the sequence defined by ''p''<sub>0</sub>(''x'') = 1 and

:<math>p_n(x) = \sum_{k=1}^n {a_n^{k\diamondsuit} x^k \over k!}\,</math>

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 function]]s are formal (not necessarily [[Convergent series|convergent]]) [[power series]] of the form

:<math>\sum_{n=0}^\infty {p_n(x) \over n!}t^n = e^{x f(t)}</math>

where ''f''(''t'') is a [[formal power series]] whose [[constant term]] is zero and whose first-degree term is not zero.{{sfn|Roman|2008|p=482-483|loc=ch. 19}} It can be shown by the use of the power-series version of [[Faà di Bruno's formula]] that

:<math>f(t)=\sum_{n=1}^\infty {p_n'(0) \over n!}t^n.</math>

The delta operator of the sequence is the compositional inverse <math>f^{-1}(D)</math>, so that

:<math>f^{-1}(D)p_n(x)=np_{n-1}(x).</math>

===A way to think about these generating functions===
The coefficients in the product of two formal power series

:<math>\sum_{n=0}^\infty {a_n \over n!}t^n</math>

and

:<math>\sum_{n=0}^\infty {b_n \over n!}t^n</math>

are

:<math>c_n=\sum_{k=0}^n {n \choose k} a_k b_{n-k}</math>

(see also [[Cauchy product]]).  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]]

:<math>g(t)^x=e^{x f(t)}</math>

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 (mathematics)|group]] in which the group operation is "umbral composition" of polynomial sequences.  That operation is defined as follows.  Suppose { ''p''<sub>''n''</sub>(''x'') : ''n'' = 0, 1, 2, 3, ... } and { ''q''<sub>''n''</sub>(''x'') : ''n'' = 0, 1, 2, 3, ... } are polynomial sequences, and

:<math>p_n(x)=\sum_{k=0}^n a_{n,k}\, x^k.</math>

Then the umbral composition ''p'' o ''q'' is the polynomial sequence whose ''n''th term is

:<math>(p_n\circ q)(x)=\sum_{k=0}^n a_{n,k}\, q_k(x)</math>

(the subscript ''n'' appears in ''p''<sub>''n''</sub>, 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.

==Cumulants and moments==
The sequence κ<sub>''n''</sub> of coefficients of the first-degree terms in a polynomial sequence of binomial type may be termed the [[cumulant]]s 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

:<math> p_n'(0)=\kappa_n= </math> the ''n''th cumulant

and

:<math> p_n(1)=\mu_n'= </math> the ''n''th moment.

These are "formal" cumulants and "formal" [[moment (mathematics)|moments]], as opposed to cumulants of a [[probability distribution]] and moments of a probability distribution.

Let

:<math>f(t)=\sum_{n=1}^\infty\frac{\kappa_n}{n!}t^n</math>

be the (formal) cumulant-generating function.  Then

:<math>f^{-1}(D) </math>

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

:<math>f^{-1}(D)p_n(x)=n p_{n-1}(x). </math>

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

==See also==
* [[List of factorial and binomial topics]]
* [[Binomial-QMF]] (Daubechies wavelet filters)

==References==
* [[Gian-Carlo Rota|G.-C. Rota]], D. Kahaner, and [[Andrew Odlyzko|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.
*{{cite book
 | last       = Roman
 | first      = Stephen
 | title      = Advanced Linear Algebra
 | edition    = Third
 | series     =[[Graduate Texts in Mathematics]] 
 | publisher  = Springer
 | date       = 2008
 | pages      = 
 | isbn       = 978-0-387-72828-5
 |author-link =Steven Roman
}}

As the title suggests, the second of the above is explicitly about applications to [[combinatorics|combinatorial]] enumeration.

* di Bucchianico, Alessandro.  ''Probabilistic and Analytical Aspects of the Umbral Calculus'', Amsterdam, [[Centrum Wiskunde & Informatica|CWI]], 1997.
* {{mathworld|urlname=Binomial-TypeSequence|title=Binomial-Type Sequence}}

[[Category:Polynomials]]
[[Category:Factorial and binomial topics]]