Bell polynomial

from Wikipedia, the free encyclopedia

In the mathematical branch of combinatorics , the Bell polynomials , named after Eric Temple Bell , denote the following triangular arrangement of polynomials

,

where the sum is formed over all sequences of non-negative integers such that

      and       .

The Bell polynomial is a polynomial in variables . Its coefficients are whole numbers .

Complete Bell polynomials

The sum

is sometimes called the tes complete Bell polynomial . For better differentiation from the complete Bell polynomials, the polynomials defined above are sometimes referred to as incomplete or partial Bell polynomials.

The complete Bell polynomials satisfy the following equation

Recursive representations

A recursive definition of the Bell polynomials is:

,
For ,
For

and

For .

The complete Bell polynomials can be defined recursively as follows

and

for .

They also satisfy the following recursive differential formula:

Combinatorial meaning

A non-negative integer is given as the number of elements of the set to be partitioned.

If the whole number (= a quantity of the size) is broken down into a sum of summands (= partitions) , in which the summand (= the partition size) occurs once, twice and the summand times, then the number corresponds to the possible partition ations that can be formed with a -elementary set, the coefficient of the monomial in the Bell polynomial that can be assigned to the partition sizes . is then the polynomial of all monomials with the total degree and the quantity .

The names (actually: the numbers) of the indefinite
act only as a post for pinning the number
of partitions in the partitioning that exactly summand   Elements should have
as an exponent of the power .

An exponent of 1 is usually not noted. If the exponent is 0, then the whole power is suppressed. The largest partition size in partitions is which partition size occurs exactly . The smallest partition size (= 1) then occurs exactly once in this partitioning .

The preferred order of the monomials in the Bell polynomial is the lexicographically ascending order with the lowest rank for , so occurs occurs .

Examples
  • for .
  • for .
  • for .
  • Furthermore is
,
because it
(Monom ) There are 6 ways to partition a set of elements into partitions with 1 and 5 elements,
(Monom ) 15 ways are to partition a lot of elements into partitions with 2 and 4 elements, and it
(Monom ) 10 ways to partition a lot of elements into partitions with 3 and 3 elements.
  • Another example is
because it
(Monom ) there are 15 ways to partition a set of elements into partitions with 1, 1 and 4 elements each,
(Monom ) 60 ways to partition a lot of elements into partitions of 1, 2 and 3 elements each, and there
(Monom ) 15 possibilities exist to partition a set of elements into partitions with 2, 2 and 2 elements each.

properties

Bell polynomials and Stirling numbers

The value of the Bell polynomial when all are equal to 1 is a Stirling number of the second kind

.

The sum

corresponding to the th Bell number representing the number of possible partitions of a quantity with describes elements.

Folding identity

A kind of convolution can be defined for consequences and :

,

where the limits are the sum and instead of and .

Be the th term of the sequence

,

then applies:

.

The convolutional identity can be used to compute single Bell polynomials. The calculation of results from

and accordingly,

Applications

Formula by Faà di Bruno

The Faà di Bruno's formula can use the Bell polynomials as follows expressed are:

A power series version of Faà di Bruno's formula can be set up in a similar way . Accepted

Then

The complete Bell polynomials appear in the exponential function of a formal power series :

.

Moments and accumulators

The sum

is the th moment of a probability distribution whose first are cumulants . In other words, the th moment is the th complete Bell polynomial evaluated on the first cumulant.

Representation of polynomial sequences with binomial properties

For any (scalar) sequence: let

.

This polynomial sequence satisfies the binomial property, i. H.

for . It is true that all polynomial sequences which satisfy the binomial property are of this form.

For the inverse of the composition of the formal power series

arises for everyone

with the above polynomials with coefficients in .

literature

  • Eric Temple Bell : Partition Polynomials . In: Annals of Mathematics . tape 29 , no. 1/4 , 1927, pp. 38-46 , doi : 10.2307 / 1967979 , JSTOR : 1967979 .
  • Louis Comtet: Advanced Combinatorics: The Art of Finite and Infinite Expansions . Reidel Publishing Company, Dordrecht, Holland / Boston, US 1974.
  • Steven Roman : The Umbral Calculus . Academic Press, 1984, ISBN 0-08-087430-4 ( 123library.org ).
  • Vassily G. Voinov, Mikhail S. Nikulin: On power series, Bell polynomials, Hardy-Ramanujan-Rademacher problem and its statistical applications . In: Cybernetics . tape 30 , no. 3 , 1994, ISSN  0023-5954 , pp. 343–358 ( kybernetika.cz [PDF]).
  • George Andrews : The Theory of Partitions (=  Cambridge Mathematical Library ). 1st edition. Cambridge University Press, 1998, ISBN 0-521-63766-X , pp. 204-211 .
  • Silvia Noschese, Paolo E. Ricci: Differentiation of Multivariable Composite Functions and Bell Polynomials . In: Journal of Computational Analysis and Applications . tape 5 , no. 3 , 2003, p. 333-340 , doi : 10.1023 / A: 1023227705558 .
  • Moncef Abbas, Sadek Bouroubi: On new identities for Bell's polynomial . In: Disc. Math . tape 293 , 2005, pp. 5-10 , doi : 10.1016 / j.disc.2004.08.023 .
  • Khristo N. Boyadzhiev: Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals . In: Abstract and Applied Analysis . 2009, doi : 10.1155 / 2009/168672 .
  • Martin Griffiths: Families of sequences from a class of multinomial sums . In: Journal of Integer Sequences . tape 15 , 2012 ( cs.uwaterloo.ca ).

Individual evidence

  1. Nikita Alexeev, Anna Pologova, Max A. Alekseyev: Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs . In: Journal of Computational Biology . 24, No. 2, 2017, pp. 93-105. arxiv : 1503.05285 . doi : 10.1089 / cmb.2016.0190 . , sect. 4.2