binomial type

Uses your system voice; voice and rate in settings.

Q4914496Snapshot

≈ 10 min read

Names in other languages

  • СрпскиПолиномски низ биномног типа
  • Englishbinomial type
  • EspañolTipo binomial
  • Françaistype binomial
  • 日本語二項型多項式列二項型, 陰合成

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, a polynomial sequence, i.e., a sequence of polynomials indexed by non-negative integers {0,1,2,3,…} in which the index of each polynomial equals its degree, is said to be of binomial type if it satisfies the sequence of identities

pn(x+y)=∑k=0n(nk)pk(x)pn−k(y).

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

edit edit source

Characterization by delta operators

edit edit source

It can be shown that a polynomial sequence { pn(x): n = 0, 1, 2, … } is of binomial type if and only if all three of the following conditions hold:

(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

edit edit source

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[1] and differentiation. It can be shown that every delta operator can be written as a power series of the form: Q=∑n=1∞cnDn 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. p0(x)=1,
  2. pn(0)=0for n≥1, and
  3. Qpn(x)=npn−1(x).

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.[2] Therefore, this paragraph amounts to a recipe for generating as many polynomial sequences of binomial type as one may wish.

Characterization by Bell polynomials

edit edit source

For any sequence a1, a2, a3, … of scalars, let

pn(x)=∑k=1nBn,k(a1,…,an−k+1)xk

where Bn,k(a1, …, an−k+1) is the Bell polynomial. Then this polynomial sequence is of binomial type. Note that for each n ≥ 1,

pn′(0)=an.

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[2] states that every polynomial sequence { pn(x) }n of binomial type is determined by the sequence { pn′(0) }n, but those sources do not mention Bell polynomials.

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

P(t)=∑n=1∞ann!tn.

Then

P−1(ddx),

where P−1(P(x))=P(P−1(x))=1, is the delta operator of this sequence.

Characterization by a convolution identity

edit edit source

For sequences an, bn, n = 0, 1, 2, …, define a sort of convolution by

(a♢b)n=∑j=0n(nj)ajbn−j.

Let ank♢ be the nth term of the sequence

a♢⋯♢a⏟k factors.

Then for any sequence ai, i = 0, 1, 2, ..., with a0 = 0, the sequence defined by p0(x) = 1 and

pn(x)=∑k=1nank♢xkk!

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

Characterization by generating functions

edit edit source

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

∑n=0∞pn(x)n!tn=exf(t)

where f(t) is a formal power series whose constant term is zero and whose first-degree term is not zero.[3] It can be shown by the use of the power-series version of Faà di Bruno's formula that

f(t)=∑n=1∞pn′(0)(n−1)!tn−1.

The delta operator of the sequence is the compositional inverse f−1(D), so that

f−1(D)pn(x)=npn−1(x).

A way to think about these generating functions

edit edit source

The coefficients in the product of two formal power series

∑n=0∞ann!tn

and

∑n=0∞bnn!tn

are

cn=∑k=0n(nk)akbn−k

(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

g(t)x=exf(t)

where f(t) has the form given above.

Umbral composition of polynomial sequences

edit edit source

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

pn(x)=∑k=0nan,kxk.

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

(pn∘q)(x)=∑k=0nan,kqk(x)

(the subscript n appears in pn, 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

edit edit source

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

pn′(0)=κn= the nth cumulant

and

pn(1)=μ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

f(t)=∑n=1∞κnn!tn

be the (formal) cumulant-generating function. Then

f−1(D)

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

f−1(D)pn(x)=npn−1(x).

Applications

edit edit source

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

See also

edit edit source

References

edit edit source
  1. ^ a b Roman 2008, p. 488-489, ch. 19.
  2. ^ a b 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.
  3. ^ Roman 2008, p. 482-483, ch. 19.
  • 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.
  • Roman, Stephen (2008). Advanced Linear Algebra. Graduate Texts in Mathematics (Third ed.). Springer. ISBN 978-0-387-72828-5.

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

Factorial and binomial topicsCombinatorial principlesCoreAddition principle · Rule of product · Binomial coefficient · Pascal's triangle · Central binomial coefficient · Vandermonde's identity · Binomial theorem · Binomial series · Binomial transform · Binomial type ·Twelvefold way · Abel's binomial theorem · Trinomial expansion · Pigeonhole principle · Inclusion–exclusion principleCombinatorics basicsCombination · Permutation · Multiset · Combinatorial number system · List of permutation topics · Antichain · Stars and bars (combinatorics)Identities, numbers, sequencesHockey-stick identity · Stirling number · Stirling transform · Catalan number · Fuss–Catalan number · Narayana numbers · Lah number · Gould's sequence · Jordan–Pólya number · Kempner function · Gaussian binomial coefficientMultinomial generalizationsMultinomial coefficient · Multinomial formula/theorem · Multinomial distribution · Pascal's pyramid · Pascal's simplex · Trinomial triangleDistributionsBinomial distribution · Negative binomial distribution · Hypergeometric distribution · Poisson distribution · Gamma distributionSpecial functions (connections)Gamma function · Beta function · Incomplete beta function · Incomplete gamma function · Pochhammer symbol (rising/falling) · Digamma function · Polygamma function · Multivariate gamma function · Hypergeometric series · Hypergeometric function identitiesFactorials & approximationsFactorial · Bhargava factorial · Exponential factorial · Hyperfactorial · Alternating factorial · Factorial moment · Factorial number system · Subfactorial · Superfactorial · Primorial · Lanczos approximation · Stirling's approximationStructures & arraysLozanić's triangle · Sierpinski triangle · Pascal matrix · Multiplicities of entries in Pascal's triangleOperators & calculus linksDifference operator · Difference polynomials · Table of Newtonian series · Faà di Bruno's formula · Taylor seriesTheorems & resultsStar of David theorem · Erdős–Ko–Rado theorem · Carlson's theorem · Mahler's theorem · Proof of Bertrand's postulate · Wilson's theorem · Wilson prime · De Polignac's formulaMethods & integralsEgorychev method · Nörlund–Rice integral · q-binomial identities · Binomial QMF

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370488942 under CC BY-SA 4.0; modifications have been made.