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.
- 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
-
↑ 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