HOME

TheInfoList



OR:

In
combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Bell polynomials, named in honor of
Eric Temple Bell Eric Temple Bell (7 February 1883 – 21 December 1960) was a Scottish-born mathematician and science fiction writer who lived in the United States for most of his life. He published non-fiction using his given name and fiction as John Tain ...
, are used in the study of set partitions. They are related to
Stirling Stirling (; sco, Stirlin; gd, Sruighlea ) is a city in central Scotland, northeast of Glasgow and north-west of Edinburgh. The market town, surrounded by rich farmland, grew up connecting the royal citadel, the medieval old town with its me ...
and
Bell numbers In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy ...
. They also occur in many applications, such as in the
Faà di Bruno's formula Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives. It is named after , although he was not the first to state or prove the formula. In 1800, more than 50 years before Faà di Bruno, the French ...
.


Definitions


Exponential Bell polynomials

The ''partial'' or ''incomplete'' exponential Bell polynomials are a
triangular array In mathematics and computing, a triangular array of numbers, polynomials, or the like, is a doubly indexed sequence in which each row is only as long as the row's own index. That is, the ''i''th row contains only ''i'' elements. Examples Notable ...
of polynomials given by :B_(x_1,x_2,\dots,x_) = \sum \left(\right)^\left(\right)^\cdots\left(\right)^, where the sum is taken over all sequences ''j''1, ''j''2, ''j''3, ..., ''j''''n''−''k''+1 of non-negative integers such that these two conditions are satisfied: :j_1 + j_2 + \cdots + j_ = k, :j_1 + 2 j_2 + 3 j_3 + \cdots + (n-k+1)j_ = n. The sum :B_n(x_1,\dots,x_n)=\sum_^n B_(x_1,x_2,\dots,x_) is called the ''n''th ''complete exponential Bell polynomial''.


Ordinary Bell polynomials

Likewise, the partial ''ordinary'' Bell polynomial is defined by :\hat_(x_1,x_2,\ldots,x_) = \sum \frac x_1^ x_2^ \cdots x_^, where the sum runs over all sequences ''j''1, ''j''2, ''j''3, ..., ''j''''n''−''k''+1 of non-negative integers such that :j_1 + j_2 + \cdots + j_ = k, :j_1 + 2 j_2 + \cdots + (n-k+1)j_ = n. The ordinary Bell polynomials can be expressed in the terms of exponential Bell polynomials: :\hat_(x_1,x_2,\ldots,x_) = \fracB_(1!\cdot x_1,2!\cdot x_2,\ldots,(n-k+1)!\cdot x_). In general, Bell polynomial refers to the exponential Bell polynomial, unless otherwise explicitly stated.


Combinatorial meaning

The exponential Bell polynomial encodes the information related to the ways a set can be partitioned. For example, if we consider a set , it can be partitioned into two non-empty, non-overlapping subsets, which is also referred to as parts or blocks, in 3 different ways: : : : Thus, we can encode the information regarding these partitions as :B_(x_1,x_2) = 3 x_1 x_2. Here, the subscripts of ''B''3,2 tells us that we are considering the partitioning of set with 3 elements into 2 blocks. The subscript of each ''x''i indicates the presence of block with ''i'' elements (or block of size ''i'') in a given partition. So here, ''x''2 indicates the presence of a block with two elements. Similarly, ''x''1 indicates the presence of a block with a single element. The exponent of ''x''ij indicates that there are ''j'' such blocks of size ''i'' in a single partition. Here, since both ''x''1 and ''x''2 has exponent 1, it indicates that there is only one such block in a given partition. The coefficient of the
monomial In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called power product, is a product of powers of variables with nonnegative integer expone ...
indicates how many such partitions there are. For our case, there are 3 partitions of a set with 3 elements into 2 blocks, where in each partition the elements are divided into two blocks of sizes 1 and 2. Since any set can be divided into a single block in only one way, the above interpretation would mean that ''B''''n'',1 = ''x''''n''. Similarly, since there is only one way that a set with ''n'' elements be divided into ''n'' singletons, ''B''''n'',''n'' = ''x''1''n''. As a more complicated example, consider :B_(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2. This tells us that if a set with 6 elements is divided into 2 blocks, then we can have 6 partitions with blocks of size 1 and 5, 15 partitions with blocks of size 4 and 2, and 10 partitions with 2 blocks of size 3. The sum of the subscripts in a monomial is equal to the total number of elements. Thus, the number of monomials that appear in the partial Bell polynomial is equal to the number of ways the integer ''n'' can be expressed as a summation of ''k'' positive integers. This is the same as the
integer partition In number theory and combinatorics, a partition of a positive integer , also called an integer partition, is a way of writing as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same part ...
of ''n'' into ''k'' parts. For instance, in the above examples, the integer 3 can be partitioned into two parts as 2+1 only. Thus, there is only one monomial in ''B''3,2. However, the integer 6 can be partitioned into two parts as 5+1, 4+2, and 3+3. Thus, there are three monomials in ''B''6,2. Indeed, the subscripts of the variables in a monomial are the same as those given by the integer partition, indicating the sizes of the different blocks. The total number of monomials appearing in a complete Bell polynomial ''Bn'' is thus equal to the total number of integer partitions of ''n''. Also the degree of each monomial, which is the sum of the exponents of each variable in the monomial, is equal to the number of blocks the set is divided into. That is, ''j''1 + ''j''2 + ... = ''k'' . Thus, given a complete Bell polynomial ''Bn'', we can separate the partial Bell polynomial ''Bn,k'' by collecting all those monomials with degree ''k''. Finally, if we disregard the sizes of the blocks and put all ''x''''i'' = ''x'', then the summation of the coefficients of the partial Bell polynomial ''B''''n'',''k'' will give the total number of ways that a set with ''n'' elements can be partitioned into ''k'' blocks, which is the same as the
Stirling numbers of the second kind In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) or \textstyle \lef ...
. Also, the summation of all the coefficients of the complete Bell polynomial ''Bn'' will give us the total number of ways a set with ''n'' elements can be partitioned into non-overlapping subsets, which is the same as the Bell number. In general, if the integer ''n'' is partitioned into a sum in which "1" appears ''j''1 times, "2" appears ''j''2 times, and so on, then the number of
partitions of a set Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...
of size ''n'' that collapse to that partition of the integer ''n'' when the members of the set become indistinguishable is the corresponding coefficient in the polynomial.


Examples

For example, we have :B_(x_1,x_2,x_3,x_4,x_5)=6x_5x_1+15x_4x_2+10x_3^2 because the ways to partition a set of 6 elements as 2 blocks are :6 ways to partition a set of 6 as 5 + 1, :15 ways to partition a set of 6 as 4 + 2, and :10 ways to partition a set of 6 as 3 + 3. Similarly, :B_(x_1,x_2,x_3,x_4)=15x_4x_1^2+60x_3x_2x_1+15x_2^3 because the ways to partition a set of 6 elements as 3 blocks are :15 ways to partition a set of 6 as 4 + 1 + 1, :60 ways to partition a set of 6 as 3 + 2 + 1, and :15 ways to partition a set of 6 as 2 + 2 + 2.


Properties


Generating function

The exponential partial Bell polynomials can be defined by the double series expansion of its generating function: : \begin \Phi(t,u) &= \exp\left( u \sum_^\infty x_j \frac \right) = \sum_ B_(x_1,\ldots,x_) \frac u^k\\ &= 1 + \sum_^\infty \frac \sum_^n u^k B_(x_1,\ldots,x_). \end In other words, by what amounts to the same, by the series expansion of the ''k''-th power: : \frac\left( \sum_^\infty x_j \frac \right)^k = \sum_^\infty B_(x_1,\ldots,x_) \frac, \qquad k = 0, 1, 2, \ldots The complete exponential Bell polynomial is defined by \Phi(t,1), or in other words: : \Phi(t,1) = \exp\left( \sum_^\infty x_j \frac \right) = \sum_^\infty B_n(x_1,\ldots, x_n) \frac. Thus, the ''n''-th complete Bell polynomial is given by : B_n(x_1,\ldots, x_n) = \left. \left(\frac\right)^n \exp\left( \sum_^n x_j \frac \right) \_. Likewise, the ''ordinary'' partial Bell polynomial can be defined by the generating function : \hat(t,u) = \exp \left( u \sum_^\infty x_j t^j \right) = \sum_ \hat_(x_1,\ldots,x_) t^n \frac. Or, equivalently, by series expansion of the ''k''-th power: :\left(\sum_^\infty x_j t^j\right)^k = \sum_^\infty \hat_(x_1, \ldots, x_) t^n. See also generating function transformations for Bell polynomial generating function expansions of compositions of sequence
generating functions In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series ...
and powers,
logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number  to the base  is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
s, and
exponentials Exponential may refer to any of several mathematical topics related to exponentiation, including: *Exponential function, also: **Matrix exponential, the matrix analogue to the above * Exponential decay, decrease at a rate proportional to value *Exp ...
of a sequence generating function. Each of these formulas is cited in the respective sections of Comtet.


Recurrence relations

The complete Bell polynomials can be recurrently defined as : B_(x_1, \ldots, x_) = \sum_^n B_(x_1, \ldots, x_) x_ with the initial value B_0 = 1. The partial Bell polynomials can also be computed efficiently by a recurrence relation: : B_ = \sum_^ \binom x_i B_, where : B_ = 1; : B_ = 0 \text n \geq 1; : B_ = 0 \text k \geq 1. The complete Bell polynomials also satisfy the following recurrence differential formula: : \begin B_n(x_1, \ldots, x_n) = \frac \left \sum_^n_\right._&_\sum_^_(i-1)_\binom_x_j_x_\frac_\\[5pt&_\left.__+_\sum_^n_\sum_^_\frac_\frac_\right._\\[5pt.html" ;"title="pt.html" ;"title="\sum_^n \right. & \sum_^ (i-1) \binom x_j x_\frac \\[5pt">\sum_^n \right. & \sum_^ (i-1) \binom x_j x_\frac \\[5pt& \left. + \sum_^n \sum_^ \frac \frac \right. \\[5pt">pt.html" ;"title="\sum_^n \right. & \sum_^ (i-1) \binom x_j x_\frac \\[5pt">\sum_^n \right. & \sum_^ (i-1) \binom x_j x_\frac \\[5pt& \left. + \sum_^n \sum_^ \frac \frac \right. \\[5pt& \left. + \sum_^n x_i \frac \right]. \end


Derivatives

The partial derivatives of the complete Bell polynomials are given by : \frac (x_1, \ldots, x_) = \binom B_(x_1, \ldots, x_). Similarly, the partial derivatives of the partial Bell polynomials are given by : \frac (x_1, \ldots, x_) = \binom B_(x_1, \ldots, x_). If the arguments of the Bell polynomials are one-dimensional functions, the chain rule can be used to obtain : \frac \left(B_(a_1(x), \cdots, a_(x))\right) = \sum_^ \binom a_i'(x) B_(a_1(x), \cdots, a_(x)).


Determinant forms

The complete Bell polynomial can be expressed as
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
s: :B_n(x_1,\dots,x_n) = \det\begin x_1 & x_2 & x_3 & x_4 & \cdots & \cdots & x_n \\ \\ -1 & x_1 & x_2 & x_3 & \cdots & \cdots & x_ \\ \\ 0 & -1 & x_1 & x_2 & \cdots & \cdots & x_ \\ \\ 0 & 0 & -1 & x_1 & \cdots & \cdots & x_ \\ \\ 0 & 0 & 0 & -1 & \cdots & \cdots & x_ \\ \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ \\ 0 & 0 & 0 & 0 & \cdots & -1 & x_1 \end and :B_n(x_1,\dots,x_n) = \det\begin \frac & \frac & \frac & \frac & \cdots & \cdots & \frac \\ \\ -1 & \frac & \frac & \frac & \cdots & \cdots & \frac \\ \\ 0 & -2 & \frac & \frac & \cdots & \cdots & \frac \\ \\ 0 & 0 & -3 & \frac & \cdots & \cdots & \frac \\ \\ 0 & 0 & 0 & -4 & \cdots & \cdots & \frac \\ \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ \\ 0 & 0 & 0 & 0 & \cdots & -(n-1) & \frac \end.


Stirling numbers and Bell numbers

The value of the Bell polynomial ''B''''n'',''k''(''x''1,''x''2,...) on the sequence of
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
s equals an unsigned Stirling number of the first kind: :B_(0!,1!,\dots,(n-k)!)=c(n,k)=, s(n,k), = \left
right Rights are law, legal, social, or ethics, ethical principles of Liberty, freedom or entitlement; that is, rights are the fundamental normative rules about what is allowed of people or owed to people according to some legal system, social convent ...
The sum of these values gives the value of the complete Bell polynomial on the sequence of factorials: :B_n(0!,1!,\dots,(n-1)!)=\sum_^n B_(0!,1!,\dots,(n-k)!) = \sum_^n \left
right Rights are law, legal, social, or ethics, ethical principles of Liberty, freedom or entitlement; that is, rights are the fundamental normative rules about what is allowed of people or owed to people according to some legal system, social convent ...
= n!. The value of the Bell polynomial ''B''''n'',''k''(''x''1,''x''2,...) on the sequence of ones equals a
Stirling number of the second kind In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to Partition of a set, partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) ...
: :B_(1,1,\dots,1)=S(n,k)=\left\. The sum of these values gives the value of the complete Bell polynomial on the sequence of ones: :B_n(1,1,\dots,1)=\sum_^n B_(1,1,\dots,1) = \sum_^n \left\, which is the ''n''th
Bell number In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy ...
.


Inverse relations

If we define :y_n = \sum_^n B_(x_1,\ldots,x_), then we have the inverse relationship :x_n = \sum_^n (-1)^ (k-1)! B_(y_1,\ldots,y_).


Touchard polynomials

Touchard polynomial T_n(x) = \sum_^n \left\\cdot x^k can be expressed as the value of the complete Bell polynomial on all arguments being ''x'': : T_n(x) = B_n(x,x,\dots,x).


Convolution identity

For sequences ''x''''n'', ''y''''n'', ''n'' = 1, 2, ..., define a
convolution In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
by: :(x \mathbin y)_n = \sum_^ x_j y_. The bounds of summation are 1 and ''n'' − 1, not 0 and ''n'' . Let x_n^\, be the ''n''th term of the sequence :\displaystyle\underbrace_.\, Then :B_(x_1,\dots,x_) = .\, For example, let us compute B_(x_1,x_2) . We have : x = ( x_1 \ , \ x_2 \ , \ x_3 \ , \ x_4 \ , \dots ) : x \mathbin x = ( 0,\ 2 x_1^2 \ ,\ 6 x_1 x_2 \ , \ 8 x_1 x_3 + 6 x_2^2 \ , \dots ) : x \mathbin x \mathbin x = ( 0 \ ,\ 0 \ , \ 6 x_1^3 \ , \ 36 x_1^2 x_2 \ , \dots ) and thus, : B_(x_1,x_2) = \frac = 6 x_1^2 x_2.


Other identities

* B_(1!,2!,\ldots,(n-k+1)!) = \binom \frac = L(n,k) which gives the
Lah number In mathematics, the Lah numbers, discovered by Ivo Lah in 1954, are coefficients expressing rising factorials in terms of falling factorials. They are also the coefficients of the nth derivatives of e^. Unsigned Lah numbers have an interesti ...
. * B_(1,2,3,\ldots,n-k+1) = \binom k^ which gives the idempotent number. * B_(-x_1,x_2,-x_3,\ldots,(-1)^x_) = (-1)^n B_(x_1,x_2,x_3,\ldots,x_) and B_n(-x_1,x_2,-x_3,\ldots,(-1)^x_n) = (-1)^n B_n(x_1,x_2,x_3,\ldots,x_n). * The complete Bell polynomials satisfy the binomial type relation: *: B_n(x_1 + y_1, \ldots, x_n + y_n) = \sum_^n B_(x_1, \ldots, x_)B_i(y_1, \ldots, y_i), *: B_\Bigl(\frac, \frac, \ldots\Bigr) = \frac B_(\ldots, 0, 0, x_, x_, \ldots). :This corrects the omission of the factor (q!)^k in Comtet's book. * When 1 \le a < n, :B_(x_1, \ldots, x_) = \sum_^\frac\binom(x_1)^ B_\Bigl(\frac, \frac, \ldots, \frac\Bigr). * Special cases of partial Bell polynomials: : \begin B_(x_1, \ldots, x_n) = & x_n \\ ptB_(x_1, \ldots, x_) = & \frac\sum_^ \binom x_kx_ \\ ptB_(x_1) = & (x_1)^n \\ ptB_(x_1, x_2) = & \binom(x_1)^x_2 \\ ptB_(x_1, x_2, x_3) = & \binom(x_1)^x_3 + 3\binom(x_1)^(x_2)^2 \\ ptB_(x_1, x_2, x_3, x_4) = & \binom(x_1)^x_4 + 10\binom(x_1)^x_2x_3 + 15\binom(x_1)^(x_2)^3\\ ptB_(x_1, x_2, x_3, x_4, x_5) = & \binom(x_1)^x_5 + 5\binom(x_1)^\bigl x_2x_4 + 2(x_3)^2\bigr+ 105\binom(x_1)^(x_2)^2x_3\\ & + 105\binom(x_1)^(x_2)^4. \end


Examples

The first few complete Bell polynomials are: : \begin B_0 = & 1, \\ pt B_1(x_1) = & x_1, \\ ptB_2(x_1,x_2) = & x_1^2 + x_2, \\ ptB_3(x_1,x_2,x_3) = & x_1^3 + 3x_1 x_2 + x_3, \\ ptB_4(x_1,x_2,x_3,x_4) = & x_1^4 + 6 x_1^2 x_2 + 4 x_1 x_3 + 3 x_2^2 + x_4, \\ ptB_5(x_1,x_2,x_3,x_4,x_5) = & x_1^5 + 10 x_2 x_1^3 + 15 x_2^2 x_1 + 10 x_3 x_1^2 + 10 x_3 x_2 + 5 x_4 x_1 + x_5 \\ ptB_6(x_1,x_2,x_3,x_4,x_5,x_6) = & x_1^6 + 15 x_2 x_1^4 + 20 x_3 x_1^3 + 45 x_2^2 x_1^2 + 15 x_2^3 + 60 x_3 x_2 x_1 \\ & + 15 x_4 x_1^2 + 10 x_3^2 + 15 x_4 x_2 + 6 x_5 x_1 + x_6, \\ ptB_7(x_1,x_2,x_3,x_4,x_5,x_6,x_7) = & x_1^7 + 21 x_1^5 x_2 + 35 x_1^4 x_3 + 105 x_1^3 x_2^2 + 35 x_1^3 x_4 \\ & + 210 x_1^2 x_2 x_3 + 105 x_1 x_2^3 + 21 x_1^2 x_5 + 105 x_1 x_2 x_4 \\ & + 70 x_1 x_3^2 + 105 x_2^2 x_3 + 7 x_1 x_6 + 21 x_2 x_5 + 35 x_3 x_4 + x_7. \end


Applications


Faà di Bruno's formula

Faà di Bruno's formula Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives. It is named after , although he was not the first to state or prove the formula. In 1800, more than 50 years before Faà di Bruno, the French ...
may be stated in terms of Bell polynomials as follows: : f(g(x)) = \sum_^n f^(g(x)) B_ \left(g'(x),g''(x), \dots, g^(x)\right). Similarly, a power-series version of Faà di Bruno's formula may be stated using Bell polynomials as follows. Suppose :f(x)=\sum_^\infty x^n \qquad \text \qquad g(x) = \sum_^\infty x^n. Then :g(f(x)) = \sum_^\infty \frac x^n. In particular, the complete Bell polynomials appear in the exponential of a
formal power series In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sum ...
: :\exp\left(\sum_^\infty x^i \right) = \sum_^\infty x^n, which also represents the
exponential generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series ...
of the complete Bell polynomials on a fixed sequence of arguments a_1, a_2, \dots.


Reversion of series

Let two functions ''f'' and ''g'' be expressed in formal power series as :f(w) = \sum_^\infty f_k \frac, \qquad \text \qquad g(z) = \sum_^\infty g_k \frac, such that ''g'' is the compositional inverse of ''f'' defined by ''g''(''f''(''w'')) = ''w'' or ''f''(''g''(''z'')) = ''z''. If ''f''0 = 0 and ''f''1 ≠ 0, then an explicit form of the coefficients of the inverse can be given in term of Bell polynomials as : g_n = \frac \sum_^ (-1)^k n^ B_(\hat_1,\hat_2,\ldots,\hat_), \qquad n \geq 2, with \hat_k = \frac, and n^ = n(n+1)\cdots (n+k-1) is the rising factorial, and g_1 = \frac.


Asymptotic expansion of Laplace-type integrals

Consider the integral of the form :I(\lambda) = \int_a^b e^ g(x) \, \mathrmx, where (''a'',''b'') is a real (finite or infinite) interval, λ is a large positive parameter and the functions ''f'' and ''g'' are continuous. Let ''f'' have a single minimum in 'a'',''b''which occurs at ''x'' = ''a''. Assume that as ''x'' → ''a''+, : f(x) \sim f(a) + \sum_^\infty a_k (x-a)^, : g(x) \sim \sum_^\infty b_k (x-a)^, with ''α'' > 0, Re(''β'') > 0; and that the expansion of ''f'' can be term wise differentiated. Then, Laplace–Erdelyi theorem states that the asymptotic expansion of the integral ''I''(''λ'') is given by : I(\lambda) \sim e^ \sum_^\infty \Gamma \Big(\frac \Big) \frac \qquad \text \quad \lambda \rightarrow \infty, where the coefficients ''cn'' are expressible in terms of ''an'' and ''bn'' using partial ''ordinary'' Bell polynomials, as given by Campbell–Froman–Walles–Wojdylo formula: : c_n = \frac \sum_^n b_ \sum_^k \binom \frac \hat_(a_1,a_2,\ldots,a_).


Symmetric polynomials

The
elementary symmetric polynomial In mathematics, specifically in commutative algebra, the elementary symmetric polynomials are one type of basic building block for symmetric polynomials, in the sense that any symmetric polynomial can be expressed as a polynomial in elementary sy ...
e_n and the
power sum symmetric polynomial In mathematics, specifically in commutative algebra, the power sum symmetric polynomials are a type of basic building block for symmetric polynomials, in the sense that every symmetric polynomial with rational coefficients can be expressed as a su ...
p_n can be related to each other using Bell polynomials as: : \begin e_n & = \frac\; B_(p_1, -1! p_2, 2! p_3, -3! p_4, \ldots, (-1)^(n-1)! p_n ) \\ & = \frac\; B_(-p_1, -1! p_2, -2! p_3, -3! p_4, \ldots, -(n-1)! p_n ), \end : \begin p_n & = \frac \sum_^n (-1)^ (k-1)!\; B_(e_1,2! e_2, 3! e_3,\ldots,(n-k+1)! e_) \\ & = (-1)^n\; n\; \sum_^n \frac \; \hat_(-e_1,\dots,-e_). \end These formulae allow one to express the coefficients of monic polynomials in terms of the Bell polynomials of its zeroes. For instance, together with
Cayley–Hamilton theorem In linear algebra, the Cayley–Hamilton theorem (named after the mathematicians Arthur Cayley and William Rowan Hamilton) states that every square matrix over a commutative ring (such as the real or complex numbers or the integers) satisfies ...
they lead to expression of the determinant of a ''n'' × ''n'' square matrix ''A'' in terms of the traces of its powers: : \det (A) = \frac B_n(s_1, s_2, \ldots, s_n), ~\qquad \text s_k = - (k - 1)! \operatorname(A^k).


Cycle index of symmetric groups

The
cycle index Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in soc ...
of the
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
S_n can be expressed in terms of complete Bell polynomials as follows: : Z(S_n) = \frac.


Moments and cumulants

The sum :\mu_n' = B_n(\kappa_1,\dots,\kappa_n)=\sum_^n B_(\kappa_1,\dots,\kappa_) is the ''n''th raw moment of a
probability distribution In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
whose first ''n''
cumulant In probability theory and statistics, the cumulants of a probability distribution are a set of quantities that provide an alternative to the '' moments'' of the distribution. Any two probability distributions whose moments are identical will have ...
s are ''κ''1, ..., ''κ''''n''. In other words, the ''n''th moment is the ''n''th complete Bell polynomial evaluated at the first ''n'' cumulants. Likewise, the ''n''th cumulant can be given in terms of the moments as :\kappa_n = \sum_^n (-1)^ (k-1)! B_(\mu'_1,\ldots,\mu'_).


Hermite polynomials

Hermite polynomials can be expressed in terms of Bell polynomials as :\operatorname_n(x) = B_n(x,-1,0,\ldots,0), where ''x''''i'' = 0 for all ''i'' > 2; thus allowing for a combinatorial interpretation of the coefficients of the Hermite polynomials. This can be seen by comparing the generating function of the Hermite polynomials :\exp \left(xt-\frac \right) = \sum_^\infty \operatorname_n(x) \frac with that of Bell polynomials.


Representation of polynomial sequences of binomial type

For any sequence ''a''1, ''a''2, …, ''a''''n'' of scalars, let :p_n(x)=\sum_^n B_(a_1,\dots,a_) x^k. Then this polynomial sequence is of
binomial type In mathematics, a polynomial sequence, i.e., a sequence of polynomials indexed by non-negative integers \left\ in which the index of each polynomial equals its degree, is said to be of binomial type if it satisfies the sequence of identities :p_ ...
, i.e. it satisfies the binomial identity :p_n(x+y)=\sum_^n p_k(x) p_(y). :Example: For ''a''1 = … = ''a''''n'' = 1, the polynomials p_n(x) represent
Touchard polynomials The Touchard polynomials, studied by , also called the exponential polynomials or Bell polynomials, comprise a polynomial sequence of binomial type defined by :T_n(x)=\sum_^n S(n,k)x^k=\sum_^n \left\x^k, where S(n,k)=\left\is a Stirling numbe ...
. More generally, we have this result: :Theorem: All polynomial sequences of binomial type are of this form. If we define a formal power series :h(x)=\sum_^\infty x^k, then for all ''n'', :h^\left( \right) p_n(x) = n p_(x).


Software

Bell polynomials are implemented in: * Mathematica a
BellY
*
Maple ''Acer'' () is a genus of trees and shrubs commonly known as maples. The genus is placed in the family Sapindaceae.Stevens, P. F. (2001 onwards). Angiosperm Phylogeny Website. Version 9, June 2008 nd more or less continuously updated since http ...
a
IncompleteBellB
*
SageMath SageMath (previously Sage or SAGE, "System for Algebra and Geometry Experimentation") is a computer algebra system (CAS) with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, numbe ...
a
bell_polynomial


See also

* Bell matrix *
Exponential formula In combinatorial mathematics, the exponential formula (called the polymer expansion in physics) states that the exponential generating function for structures on finite sets is the exponential of the exponential generating function for connected str ...


Notes


References

* * * * * * (contains also elementary review of the concept Bell-polynomials) * * * * * * * * {{DEFAULTSORT:Bell Polynomials Enumerative combinatorics Polynomials