Namespaces
Variants
Actions

Difference between revisions of "Bell polynomial"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
The Bell polynomials (studied extensively by E.T. Bell [[#References|[a2]]]) arise naturally from differentiating a [[Composite function|composite function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102501.png" /> times, but in this context they predate Bell since they are implicit in the work of F. Faà di Bruno [[#References|[a4]]]. Accounts of Faà di Bruno's formula, however, often fail to mention any connection with Bell polynomials. The polynomials also occur in other places without being referred to by name; in [[#References|[a1]]] (Table 24.2), for example, the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102502.png" /> are coefficients of partial Bell polynomials, but are not identified as such.
+
<!--
 +
b1102501.png
 +
$#A+1 = 103 n = 0
 +
$#C+1 = 103 : ~/encyclopedia/old_files/data/B110/B.1100250 Bell polynomial
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102503.png" /> and let
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102504.png" /></td> </tr></table>
+
The Bell polynomials (studied extensively by E.T. Bell [[#References|[a2]]]) arise naturally from differentiating a [[Composite function|composite function]]  $  n $
 +
times, but in this context they predate Bell since they are implicit in the work of F. Faà di Bruno [[#References|[a4]]]. Accounts of Faà di Bruno's formula, however, often fail to mention any connection with Bell polynomials. The polynomials also occur in other places without being referred to by name; in [[#References|[a1]]] (Table 24.2), for example, the numbers  $  M _ {3} $
 +
are coefficients of partial Bell polynomials, but are not identified as such.
 +
 
 +
Suppose that  $  h ( t ) = f ( g ( t ) ) $
 +
and let
 +
 
 +
$$
 +
h _ {n} = {
 +
\frac{d  ^ {n} h }{d t  ^ {n} }
 +
} ,  f _ {n} = {
 +
\frac{d  ^ {n} f }{d g  ^ {n} }
 +
} ,  g _ {n} = {
 +
\frac{d  ^ {n} g }{d t  ^ {n} }
 +
} ;
 +
$$
  
 
then by repeated application of the chain rule:
 
then by repeated application of the chain rule:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102505.png" /></td> </tr></table>
+
$$
 +
h _ {0} = f _ {0} ,  h _ {1} = f _ {1} g _ {1} ,  h _ {2} = f _ {1} g _ {2} + f _ {2} g _ {1}  ^ {2} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102506.png" /></td> </tr></table>
+
$$
 +
h _ {3} = f _ {1} g _ {3} + f _ {2} ( 3g _ {1} g _ {2} ) + f _ {3} g _ {1}  ^ {3} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102507.png" /></td> </tr></table>
+
$$
 +
h _ {4} = f _ {1} g _ {4} + f _ {2} ( 3g _ {2}  ^ {2} + 4g _ {1} g _ {3} ) + f _ {3} ( 6g _ {1}  ^ {2} g _ {2} ) + f _ {4} g _ {1}  ^ {4} .
 +
$$
  
 
In general,
 
In general,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102508.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
$$ \tag{a1 }
 +
h _ {n} = \sum _ {k = 1 } ^ { n }  f _ {k} B _ {n,k }  ( g _ {1} \dots g _ {n - k + 1 }  ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b1102509.png" /> is a homogeneous polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025010.png" /> and weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025011.png" /> in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025012.png" />, known as a (partial) Bell polynomial (see [[#References|[a3]]] for a table for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025013.png" />); it has integral coefficients. Because of the homogeneity, for fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025014.png" /> all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025015.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025016.png" />) can be determined uniquely even if the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025017.png" /> are omitted. Hence the (complete) Bell polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025018.png" /> is usually defined for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025019.png" /> by
+
where $  B _ {n,k }  $
 +
is a homogeneous polynomial of degree $  k $
 +
and weight $  n $
 +
in the $  g _ {m} $,  
 +
known as a (partial) Bell polynomial (see [[#References|[a3]]] for a table for $  1 \leq  k \leq  n \leq  12 $);  
 +
it has integral coefficients. Because of the homogeneity, for fixed $  n $
 +
all $  B _ {n,k }  $(
 +
$  k = 1 \dots n $)  
 +
can be determined uniquely even if the $  f _ {k} $
 +
are omitted. Hence the (complete) Bell polynomial $  Y _ {n} $
 +
is usually defined for $  n \geq  1 $
 +
by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025020.png" /></td> </tr></table>
+
$$
 +
Y _ {n} ( g _ {1} \dots g _ {n} ) = \sum _ {k = 1 } ^ { n }  B _ {n,k }  ( g _ {1} \dots g _ {n - k + 1 }  ) .
 +
$$
  
 
In [[#References|[a7]]], however, the term Bell polynomial is used for
 
In [[#References|[a7]]], however, the term Bell polynomial is used for
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025021.png" /></td> </tr></table>
+
$$
 +
A _ {n} ( f;g _ {1} , \dots,g _ {n - k + 1 }  ) = h _ {n} ,
 +
$$
  
so the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025022.png" /> are included in the definition.
+
so the $  f _ {k} $
 +
are included in the definition.
  
The following definitions are also made: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025024.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025025.png" />), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025026.png" />.
+
The following definitions are also made: $  B _ {0,0 }  = 1 $,
 +
$  B _ {0,k }  = 0 $(
 +
$  k \geq  1 $),  
 +
$  Y _ {0} = 1 $.
  
Although the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025027.png" /> were introduced as derivatives, the Bell polynomials themselves, considered purely as polynomials in the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025028.png" /> are independent of the initial functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025030.png" />. Hence information can be deduced from special choices such as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025031.png" />, which gives
+
Although the $  g _ {n} $
 +
were introduced as derivatives, the Bell polynomials themselves, considered purely as polynomials in the variables $  g _ {1} ,g _ {2} , \dots $
 +
are independent of the initial functions $  g ( t ) $
 +
and $  f ( g ) $.  
 +
Hence information can be deduced from special choices such as $  f ( g ) = e  ^ {g} $,  
 +
which gives
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025032.png" /></td> </tr></table>
+
$$
 +
Y _ {n} ( g _ {1} , \dots,g _ {n} ) = e ^ {- g } {
 +
\frac{d  ^ {n} e  ^ {g} }{d t  ^ {n} }
 +
} .
 +
$$
  
An alternative approach which gives the same polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025033.png" /> is adopted in [[#References|[a3]]], where they are defined as coefficients in the expansion of the two-variable [[Generating function|generating function]]
+
An alternative approach which gives the same polynomials $  B _ {n,k }  $
 +
is adopted in [[#References|[a3]]], where they are defined as coefficients in the expansion of the two-variable [[Generating function|generating function]]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025034.png" /></td> </tr></table>
+
$$
 +
\Phi ( t,u ) = { \mathop{\rm exp} } \left ( u \sum _ {m = 1 } ^  \infty  {
 +
\frac{g _ {m} t  ^ {m} }{m! }
 +
} \right ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025035.png" /></td> </tr></table>
+
$$
 +
=  
 +
1 + \sum _ {n = 1 } ^  \infty  \sum _ {k = 1 } ^ { n }  B _ {n,k }  ( g _ {1} , \dots,g _ {n - k + 1 }  ) {
 +
\frac{u  ^ {k} t  ^ {n} }{n! }
 +
} .
 +
$$
  
This approach obviates the earlier assumption that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025036.png" /> are derivatives.
+
This approach obviates the earlier assumption that the $  g _ {m} $
 +
are derivatives.
  
 
The generating function for the complete polynomials is
 
The generating function for the complete polynomials is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025037.png" /></td> </tr></table>
+
$$
 +
\Phi ( t,1 ) = { \mathop{\rm exp} } \left ( \sum _ {m = 1 } ^  \infty  {
 +
\frac{g _ {m} t  ^ {m} }{m! }
 +
} \right ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025038.png" /></td> </tr></table>
+
$$
 +
=  
 +
1 + \sum _ {n = 1 } ^  \infty  Y _ {n} ( g _ {1} , \dots,g _ {n} ) {
 +
\frac{t  ^ {n} }{n! }
 +
} .
 +
$$
  
Explicit formulas are known for Bell polynomials and they are examples of partition polynomials (multivariable polynomials which can be expressed as a sum of monomials, where the sum is over a set of partitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025039.png" />; cf. also [[Partition|Partition]]). The partial polynomial
+
Explicit formulas are known for Bell polynomials and they are examples of partition polynomials (multivariable polynomials which can be expressed as a sum of monomials, where the sum is over a set of partitions of $  n $;  
 +
cf. also [[Partition|Partition]]). The partial polynomial
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025040.png" /></td> </tr></table>
+
$$
 +
B _ {n,k }  ( g _ {1} , \dots,g _ {n - k + 1 }  ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025041.png" /></td> </tr></table>
+
$$
 +
=  
 +
\sum {
 +
\frac{n! }{c _ {1} ! \dots c _ {n - k + 1 }  ! }
 +
} \left ( {
 +
\frac{g _ {1} }{1! }
 +
} \right ) ^ {c _ {1} } \dots \left ( {
 +
\frac{g _ {n - k + 1 }  }{( n - k + 1 ) ! }
 +
} \right ) ^ {c _ {n - k + 1 }  } ,
 +
$$
  
where the sum is over all partitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025042.png" /> into exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025043.png" /> non-negative parts, i.e., over all solutions in non-negative integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025044.png" /> of the two equations
+
where the sum is over all partitions of $  n $
 +
into exactly $  k $
 +
non-negative parts, i.e., over all solutions in non-negative integers $  c _ {r} $
 +
of the two equations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025045.png" /></td> </tr></table>
+
$$
 +
c _ {1} + 2c _ {2} + \dots + ( n - k + 1 ) c _ {n - k + 1 }  = n,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025046.png" /></td> </tr></table>
+
$$
 +
c _ {1} + c _ {2} + \dots + c _ {n - k + 1 }  = k.
 +
$$
  
Since, for each fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025047.png" />, there can be no parts of size greater than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025048.png" />, the formula is often stated in the simpler looking, but equivalent, form (where necessarily <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025049.png" />):
+
Since, for each fixed $  k $,  
 +
there can be no parts of size greater than $  n - k + 1 $,  
 +
the formula is often stated in the simpler looking, but equivalent, form (where necessarily $  c _ {n - k + 2 }  = \dots = c _ {n} = 0 $):
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025050.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
+
$$ \tag{a2 }
 +
B _ {n,k }  ( g _ {1} , \dots,g _ {n - k + 1 }  ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025051.png" /></td> </tr></table>
+
$$
 +
=  
 +
\sum {
 +
\frac{n! }{c _ {1} ! \dots c _ {n} ! }
 +
} \left ( {
 +
\frac{g _ {1} }{1! }
 +
} \right ) ^ {c _ {1} } \dots \left ( {
 +
\frac{g _ {n} }{n! }
 +
} \right ) ^ {c _ {n} } ,
 +
$$
  
 
where the sum is over all solutions in non-negative integers of the equations
 
where the sum is over all solutions in non-negative integers of the equations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025052.png" /></td> </tr></table>
+
$$
 +
c _ {1} + 2c _ {2} + \dots + nc _ {n} = n,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025053.png" /></td> </tr></table>
+
$$
 +
c _ {1} + c _ {2} + \dots + c _ {n} = k.
 +
$$
  
 
The complete polynomial
 
The complete polynomial
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025054.png" /></td> </tr></table>
+
$$
 +
Y _ {n} ( g _ {1} , \dots,g _ {n} ) = \sum {
 +
\frac{n! }{c _ {1} ! \dots c _ {n} ! }
 +
} \left ( {
 +
\frac{g _ {1} }{1! }
 +
} \right ) ^ {c _ {1} } \dots ( {
 +
\frac{g _ {n} }{n! }
 +
} ) ^ {c _ {n} } ,
 +
$$
  
where the sum is over all partitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025055.png" /> into arbitrarily many non-negative parts, i.e., over all non-negative integer solutions of the single equation
+
where the sum is over all partitions of $  n $
 +
into arbitrarily many non-negative parts, i.e., over all non-negative integer solutions of the single equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025056.png" /></td> </tr></table>
+
$$
 +
c _ {1} + 2c _ {2} + \dots + nc _ {n} = n.
 +
$$
  
 
There are many recurrence relations for Bell polynomials, as well as formulas connecting them with other special polynomials and numbers; the following is a small selection, and others may be found in [[#References|[a3]]], [[#References|[a7]]], [[#References|[a8]]].
 
There are many recurrence relations for Bell polynomials, as well as formulas connecting them with other special polynomials and numbers; the following is a small selection, and others may be found in [[#References|[a3]]], [[#References|[a7]]], [[#References|[a8]]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025057.png" /></td> </tr></table>
+
$$
 +
kB _ {n,k }  ( g _ {1} , \dots,g _ {n - k + 1 }  ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025058.png" /></td> </tr></table>
+
$$
 +
=  
 +
\sum _ {r = k - 1 } ^ { {n }  - 1 } \left ( \begin{array}{c}
 +
n \\
 +
r
 +
\end{array}
 +
\right ) g _ {n - r }  B _ {r,k - 1 }  ( g _ {1} \dots g _ {r - k + 2 }  ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025059.png" /></td> </tr></table>
+
$$
 +
B _ {n,k }  ( 1, \dots,n - k + 1 ) = \left ( \begin{array}{c}
 +
n \\
 +
k
 +
\end{array}
 +
\right ) k ^ {n - k } ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025060.png" /></td> </tr></table>
+
$$
 +
B _ {n,k }  ( 0!, \dots, ( n - k ) ! ) = \left | {s ( n,k ) } \right | ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025061.png" /></td> </tr></table>
+
$$
 +
B _ {n,k }  ( 1, \dots,1 ) = S ( n,k ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025062.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025063.png" /> are Stirling numbers of the first and second kinds (cf. [[Combinatorial analysis|Combinatorial analysis]]), respectively;
+
where $  s ( n,k ) $
 +
and $  S ( n,k ) $
 +
are Stirling numbers of the first and second kinds (cf. [[Combinatorial analysis|Combinatorial analysis]]), respectively;
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025064.png" /></td> </tr></table>
+
$$
 +
B _ {n,k }  ( 1!, \dots, ( n - k + 1 ) ! ) = \left | {L _ {n,k }  } \right | ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025065.png" /> is the [[Lah number|Lah number]];
+
where $  L _ {n,k }  $
 +
is the [[Lah number|Lah number]];
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025066.png" /></td> </tr></table>
+
$$
 +
Y _ {n} ( 1, \dots,1 ) = B _ {n} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025067.png" /> are the [[Bell numbers|Bell numbers]].
+
where $  B _ {n} $
 +
are the [[Bell numbers|Bell numbers]].
  
Combining equations (a1) and (a2) gives Faà di Bruno's formula for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025068.png" />th derivative of a composite function:
+
Combining equations (a1) and (a2) gives Faà di Bruno's formula for the $  n $
 +
th derivative of a composite function:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025069.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{d  ^ {n} }{d t  ^ {n} }
 +
} f ( g ( t ) ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025070.png" /></td> </tr></table>
+
$$
 +
=  
 +
\sum {
 +
\frac{n! }{c _ {1} ! \dots c _ {n} ! }
 +
}  {
 +
\frac{d  ^ {k} f }{d g  ^ {k} }
 +
} \left ( {
 +
\frac{g  ^  \prime  }{1! }
 +
} \right ) ^ {c _ {1} } \dots \left ( {
 +
\frac{g ^ {( n ) } }{n! }
 +
} \right ) ^ {c _ {n} } ,
 +
$$
  
 
summed over all solutions in non-negative integers of
 
summed over all solutions in non-negative integers of
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025071.png" /></td> </tr></table>
+
$$
 +
c _ {1} + 2c _ {2} + \dots + nc _ {n} = n,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025072.png" /></td> </tr></table>
+
$$
 +
c _ {1} + c _ {2} + \dots + c _ {n} = k.
 +
$$
  
 
(For a generalization to functions of several variables, see [[#References|[a5]]].)
 
(For a generalization to functions of several variables, see [[#References|[a5]]].)
Line 117: Line 290:
 
The formula can be used, in particular, to express functions of power series as power series. If
 
The formula can be used, in particular, to express functions of power series as power series. If
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025073.png" /></td> </tr></table>
+
$$
 +
g ( t ) = \sum _ {n = 0 } ^  \infty  {
 +
\frac{a _ {n} t  ^ {n} }{n! }
 +
}
 +
$$
  
 
and
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025074.png" /></td> </tr></table>
+
$$
 +
h ( t ) = f ( g ( t ) ) = \sum _ {n = 0 } ^  \infty  {
 +
\frac{b _ {n} t  ^ {n} }{n! }
 +
} ,
 +
$$
  
 
then
 
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025075.png" /></td> </tr></table>
+
$$
 +
a _ {n} = g ^ {( n ) } ( 0 ) ,  b _ {n} = h ^ {( n ) } ( 0 ) ,
 +
$$
  
and Faà di Bruno's formula can be used to find <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025076.png" />. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025077.png" />, then
+
and Faà di Bruno's formula can be used to find b _ {n} $.  
 +
For example, if $  f ( g ) = { \mathop{\rm ln} } g $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025078.png" /></td> </tr></table>
+
$$
 +
f ^ {( k ) } = ( - 1 ) ^ {k - 1 } ( k - 1 ) !g ^ {- k } \quad ( k \geq  1 ) .
 +
$$
  
Hence, applying the formula and evaluating the result at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025079.png" /> gives
+
Hence, applying the formula and evaluating the result at $  t = 0 $
 +
gives
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025080.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>
+
$$ \tag{a3 }
 +
b _ {n} = h ^ {( n ) } ( 0 ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025081.png" /></td> </tr></table>
+
$$
 +
=  
 +
\sum _ {k = 1 } ^ { n }  ( - 1 ) ^ {k - 1 } ( k - 1 ) ! a _ {0} ^ {- k } B _ {n,k }  ( a _ {1} , \dots ,a _ {n - k + 1 }  ) {
 +
\frac{t  ^ {n} }{n! }
 +
} .
 +
$$
  
Thus, provided that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025082.png" />,
+
Thus, provided that $  a _ {0} > 0 $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025083.png" /></td> </tr></table>
+
$$
 +
{ \mathop{\rm ln} } \left ( \sum _ {n = 0 } ^  \infty  {
 +
\frac{a _ {n} t  ^ {n} }{n! }
 +
} \right ) = { \mathop{\rm ln} } a _ {0} +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025084.png" /></td> </tr></table>
+
$$
 +
+
 +
\sum _ {n = 1 } ^  \infty  \sum _ {k = 1 } ^ { n }  ( - 1 ) ^ {k - 1 } ( k - 1 ) ! a _ {0} ^ {- k } B _ {n,k }  ( a _ {1} , \dots ,a _ {n - k + 1 }  ) {
 +
\frac{t  ^ {n} }{n! }
 +
} .
 +
$$
  
A special case of (a3) is used [[#References|[a6]]] to express the cumulants (semi-invariants, cf. [[Semi-invariant(2)|Semi-invariant]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025085.png" /> of a [[Probability distribution|probability distribution]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025086.png" /> in terms of its moments (cf. [[Moment|Moment]])
+
A special case of (a3) is used [[#References|[a6]]] to express the cumulants (semi-invariants, cf. [[Semi-invariant(2)|Semi-invariant]]) $  \kappa _ {n} $
 +
of a [[Probability distribution|probability distribution]] $  \{ p _ {0} ,p _ {1} , \dots \} $
 +
in terms of its moments (cf. [[Moment|Moment]])
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025087.png" /></td> </tr></table>
+
$$
 +
m _ {n} = \sum _ {r = 0 } ^  \infty  r  ^ {n} p _ {r} \quad ( n \geq  1 ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025088.png" /></td> </tr></table>
+
$$
 +
m _ {0} = \sum _ {r = 0 } ^  \infty  p _ {r} = 1.
 +
$$
  
 
The probability generating function of the distribution is
 
The probability generating function of the distribution is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025089.png" /></td> </tr></table>
+
$$
 +
G ( z ) = \sum _ {r = 0 } ^  \infty  p _ {r} z  ^ {r} ,
 +
$$
  
 
and it is easy to show that
 
and it is easy to show that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025090.png" /></td> </tr></table>
+
$$
 +
G ( e  ^ {t} ) = \sum _ {n = 0 } ^  \infty  {
 +
\frac{m _ {n} t  ^ {n} }{n! }
 +
} .
 +
$$
  
The cumulants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025091.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025092.png" />) and their exponential generating function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025093.png" /> are defined in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025094.png" /> by
+
The cumulants $  \kappa _ {n} $(
 +
$  n \geq  1 $)  
 +
and their exponential generating function $  L ( t ) $
 +
are defined in terms of $  G ( e  ^ {t} ) $
 +
by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025095.png" /></td> </tr></table>
+
$$
 +
L ( t ) = \sum _ {n = 1 } ^  \infty  {
 +
\frac{\kappa _ {n} t  ^ {n} }{n! }
 +
} = { \mathop{\rm ln} } G ( e  ^ {t} ) = { \mathop{\rm ln} } \sum _ {n = 0 } ^  \infty  {
 +
\frac{m _ {n} t  ^ {n} }{n! }
 +
} .
 +
$$
  
Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025096.png" />, it follows from (a3) that
+
Since $  m _ {0} = 1 $,  
 +
it follows from (a3) that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025097.png" /></td> </tr></table>
+
$$
 +
\kappa _ {n} = \sum _ {k = 1 } ^ { n }  ( - 1 ) ^ {k - 1 } ( k - 1 ) ! B _ {n,k }  ( m _ {1} \dots m _ {n - k + 1 }  ) .
 +
$$
  
 
Similarly, starting from
 
Similarly, starting from
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025098.png" /></td> </tr></table>
+
$$
 +
G ( e  ^ {t} ) = \sum _ {n = 0 } ^  \infty  {
 +
\frac{m _ {n} t  ^ {n} }{n! }
 +
} = e ^ {L ( t ) } = { \mathop{\rm exp} } \left ( \sum _ {n = 1 } ^  \infty  {
 +
\frac{\kappa _ {n} t  ^ {n} }{n! }
 +
} \right ) ,
 +
$$
  
and applying Faà di Bruno's formula with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b11025099.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b110250100.png" /> (and noting that in this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b110250101.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b110250102.png" />), the inverse relation expressing moments in terms of cumulants reduces to
+
and applying Faà di Bruno's formula with $  f ( g ) = e  ^ {g} $
 +
and $  g ( t ) = \sum { {\kappa _ {n} t  ^ {n} } / {n! } } $(
 +
and noting that in this case $  h ^ {( k ) } ( 0 ) = 1 $
 +
for all $  k \geq  1 $),  
 +
the inverse relation expressing moments in terms of cumulants reduces to
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110250/b110250103.png" /></td> </tr></table>
+
$$
 +
m _ {n} = Y _ {n} ( \kappa _ {1} , \dots, \kappa _ {n} ) .
 +
$$
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Abramowitz,  I. Stegun,  "Handbook of mathematical functions" , Dover, reprint  (1965)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.T. Bell,  "Exponential polynomials"  ''Ann. of Math.'' , '''35'''  (1934)  pp. 258–277</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L. Comtet,  "Advanced combinatorics" , Reidel  (1974)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  F. Faà di Bruno,  "Note sur une nouvelle formule du calcul différentiel"  ''Quart. J. Math.'' , '''1'''  (1855)  pp. 359–360</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  I.J. Good,  "The multivariate saddlepoint method and chi-squared for the multinomial distribution"  ''Ann. Math. Stat.'' , '''32'''  (1961)  pp. 535–548</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E. Lukács,  "Applications of Faà di Bruno's formula in mathematical statistics"  ''Amer. Math. Monthly'' , '''62'''  (1955)  pp. 340–348</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J. Riordan,  "Combinatorial identities" , Wiley  (1968)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  S. Roman,  "The umbral calculus" , Acad. Press  (1984)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Abramowitz,  I. Stegun,  "Handbook of mathematical functions" , Dover, reprint  (1965)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.T. Bell,  "Exponential polynomials"  ''Ann. of Math.'' , '''35'''  (1934)  pp. 258–277</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L. Comtet,  "Advanced combinatorics" , Reidel  (1974)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  F. Faà di Bruno,  "Note sur une nouvelle formule du calcul différentiel"  ''Quart. J. Math.'' , '''1'''  (1855)  pp. 359–360</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  I.J. Good,  "The multivariate saddlepoint method and chi-squared for the multinomial distribution"  ''Ann. Math. Stat.'' , '''32'''  (1961)  pp. 535–548</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E. Lukács,  "Applications of Faà di Bruno's formula in mathematical statistics"  ''Amer. Math. Monthly'' , '''62'''  (1955)  pp. 340–348</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J. Riordan,  "Combinatorial identities" , Wiley  (1968)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  S. Roman,  "The umbral calculus" , Acad. Press  (1984)</TD></TR></table>

Latest revision as of 10:58, 29 May 2020


The Bell polynomials (studied extensively by E.T. Bell [a2]) arise naturally from differentiating a composite function $ n $ times, but in this context they predate Bell since they are implicit in the work of F. Faà di Bruno [a4]. Accounts of Faà di Bruno's formula, however, often fail to mention any connection with Bell polynomials. The polynomials also occur in other places without being referred to by name; in [a1] (Table 24.2), for example, the numbers $ M _ {3} $ are coefficients of partial Bell polynomials, but are not identified as such.

Suppose that $ h ( t ) = f ( g ( t ) ) $ and let

$$ h _ {n} = { \frac{d ^ {n} h }{d t ^ {n} } } , f _ {n} = { \frac{d ^ {n} f }{d g ^ {n} } } , g _ {n} = { \frac{d ^ {n} g }{d t ^ {n} } } ; $$

then by repeated application of the chain rule:

$$ h _ {0} = f _ {0} , h _ {1} = f _ {1} g _ {1} , h _ {2} = f _ {1} g _ {2} + f _ {2} g _ {1} ^ {2} , $$

$$ h _ {3} = f _ {1} g _ {3} + f _ {2} ( 3g _ {1} g _ {2} ) + f _ {3} g _ {1} ^ {3} , $$

$$ h _ {4} = f _ {1} g _ {4} + f _ {2} ( 3g _ {2} ^ {2} + 4g _ {1} g _ {3} ) + f _ {3} ( 6g _ {1} ^ {2} g _ {2} ) + f _ {4} g _ {1} ^ {4} . $$

In general,

$$ \tag{a1 } h _ {n} = \sum _ {k = 1 } ^ { n } f _ {k} B _ {n,k } ( g _ {1} \dots g _ {n - k + 1 } ) , $$

where $ B _ {n,k } $ is a homogeneous polynomial of degree $ k $ and weight $ n $ in the $ g _ {m} $, known as a (partial) Bell polynomial (see [a3] for a table for $ 1 \leq k \leq n \leq 12 $); it has integral coefficients. Because of the homogeneity, for fixed $ n $ all $ B _ {n,k } $( $ k = 1 \dots n $) can be determined uniquely even if the $ f _ {k} $ are omitted. Hence the (complete) Bell polynomial $ Y _ {n} $ is usually defined for $ n \geq 1 $ by

$$ Y _ {n} ( g _ {1} \dots g _ {n} ) = \sum _ {k = 1 } ^ { n } B _ {n,k } ( g _ {1} \dots g _ {n - k + 1 } ) . $$

In [a7], however, the term Bell polynomial is used for

$$ A _ {n} ( f;g _ {1} , \dots,g _ {n - k + 1 } ) = h _ {n} , $$

so the $ f _ {k} $ are included in the definition.

The following definitions are also made: $ B _ {0,0 } = 1 $, $ B _ {0,k } = 0 $( $ k \geq 1 $), $ Y _ {0} = 1 $.

Although the $ g _ {n} $ were introduced as derivatives, the Bell polynomials themselves, considered purely as polynomials in the variables $ g _ {1} ,g _ {2} , \dots $ are independent of the initial functions $ g ( t ) $ and $ f ( g ) $. Hence information can be deduced from special choices such as $ f ( g ) = e ^ {g} $, which gives

$$ Y _ {n} ( g _ {1} , \dots,g _ {n} ) = e ^ {- g } { \frac{d ^ {n} e ^ {g} }{d t ^ {n} } } . $$

An alternative approach which gives the same polynomials $ B _ {n,k } $ is adopted in [a3], where they are defined as coefficients in the expansion of the two-variable generating function

$$ \Phi ( t,u ) = { \mathop{\rm exp} } \left ( u \sum _ {m = 1 } ^ \infty { \frac{g _ {m} t ^ {m} }{m! } } \right ) = $$

$$ = 1 + \sum _ {n = 1 } ^ \infty \sum _ {k = 1 } ^ { n } B _ {n,k } ( g _ {1} , \dots,g _ {n - k + 1 } ) { \frac{u ^ {k} t ^ {n} }{n! } } . $$

This approach obviates the earlier assumption that the $ g _ {m} $ are derivatives.

The generating function for the complete polynomials is

$$ \Phi ( t,1 ) = { \mathop{\rm exp} } \left ( \sum _ {m = 1 } ^ \infty { \frac{g _ {m} t ^ {m} }{m! } } \right ) = $$

$$ = 1 + \sum _ {n = 1 } ^ \infty Y _ {n} ( g _ {1} , \dots,g _ {n} ) { \frac{t ^ {n} }{n! } } . $$

Explicit formulas are known for Bell polynomials and they are examples of partition polynomials (multivariable polynomials which can be expressed as a sum of monomials, where the sum is over a set of partitions of $ n $; cf. also Partition). The partial polynomial

$$ B _ {n,k } ( g _ {1} , \dots,g _ {n - k + 1 } ) = $$

$$ = \sum { \frac{n! }{c _ {1} ! \dots c _ {n - k + 1 } ! } } \left ( { \frac{g _ {1} }{1! } } \right ) ^ {c _ {1} } \dots \left ( { \frac{g _ {n - k + 1 } }{( n - k + 1 ) ! } } \right ) ^ {c _ {n - k + 1 } } , $$

where the sum is over all partitions of $ n $ into exactly $ k $ non-negative parts, i.e., over all solutions in non-negative integers $ c _ {r} $ of the two equations

$$ c _ {1} + 2c _ {2} + \dots + ( n - k + 1 ) c _ {n - k + 1 } = n, $$

$$ c _ {1} + c _ {2} + \dots + c _ {n - k + 1 } = k. $$

Since, for each fixed $ k $, there can be no parts of size greater than $ n - k + 1 $, the formula is often stated in the simpler looking, but equivalent, form (where necessarily $ c _ {n - k + 2 } = \dots = c _ {n} = 0 $):

$$ \tag{a2 } B _ {n,k } ( g _ {1} , \dots,g _ {n - k + 1 } ) = $$

$$ = \sum { \frac{n! }{c _ {1} ! \dots c _ {n} ! } } \left ( { \frac{g _ {1} }{1! } } \right ) ^ {c _ {1} } \dots \left ( { \frac{g _ {n} }{n! } } \right ) ^ {c _ {n} } , $$

where the sum is over all solutions in non-negative integers of the equations

$$ c _ {1} + 2c _ {2} + \dots + nc _ {n} = n, $$

$$ c _ {1} + c _ {2} + \dots + c _ {n} = k. $$

The complete polynomial

$$ Y _ {n} ( g _ {1} , \dots,g _ {n} ) = \sum { \frac{n! }{c _ {1} ! \dots c _ {n} ! } } \left ( { \frac{g _ {1} }{1! } } \right ) ^ {c _ {1} } \dots ( { \frac{g _ {n} }{n! } } ) ^ {c _ {n} } , $$

where the sum is over all partitions of $ n $ into arbitrarily many non-negative parts, i.e., over all non-negative integer solutions of the single equation

$$ c _ {1} + 2c _ {2} + \dots + nc _ {n} = n. $$

There are many recurrence relations for Bell polynomials, as well as formulas connecting them with other special polynomials and numbers; the following is a small selection, and others may be found in [a3], [a7], [a8].

$$ kB _ {n,k } ( g _ {1} , \dots,g _ {n - k + 1 } ) = $$

$$ = \sum _ {r = k - 1 } ^ { {n } - 1 } \left ( \begin{array}{c} n \\ r \end{array} \right ) g _ {n - r } B _ {r,k - 1 } ( g _ {1} \dots g _ {r - k + 2 } ) , $$

$$ B _ {n,k } ( 1, \dots,n - k + 1 ) = \left ( \begin{array}{c} n \\ k \end{array} \right ) k ^ {n - k } , $$

$$ B _ {n,k } ( 0!, \dots, ( n - k ) ! ) = \left | {s ( n,k ) } \right | , $$

$$ B _ {n,k } ( 1, \dots,1 ) = S ( n,k ) , $$

where $ s ( n,k ) $ and $ S ( n,k ) $ are Stirling numbers of the first and second kinds (cf. Combinatorial analysis), respectively;

$$ B _ {n,k } ( 1!, \dots, ( n - k + 1 ) ! ) = \left | {L _ {n,k } } \right | , $$

where $ L _ {n,k } $ is the Lah number;

$$ Y _ {n} ( 1, \dots,1 ) = B _ {n} , $$

where $ B _ {n} $ are the Bell numbers.

Combining equations (a1) and (a2) gives Faà di Bruno's formula for the $ n $ th derivative of a composite function:

$$ { \frac{d ^ {n} }{d t ^ {n} } } f ( g ( t ) ) = $$

$$ = \sum { \frac{n! }{c _ {1} ! \dots c _ {n} ! } } { \frac{d ^ {k} f }{d g ^ {k} } } \left ( { \frac{g ^ \prime }{1! } } \right ) ^ {c _ {1} } \dots \left ( { \frac{g ^ {( n ) } }{n! } } \right ) ^ {c _ {n} } , $$

summed over all solutions in non-negative integers of

$$ c _ {1} + 2c _ {2} + \dots + nc _ {n} = n, $$

$$ c _ {1} + c _ {2} + \dots + c _ {n} = k. $$

(For a generalization to functions of several variables, see [a5].)

The formula can be used, in particular, to express functions of power series as power series. If

$$ g ( t ) = \sum _ {n = 0 } ^ \infty { \frac{a _ {n} t ^ {n} }{n! } } $$

and

$$ h ( t ) = f ( g ( t ) ) = \sum _ {n = 0 } ^ \infty { \frac{b _ {n} t ^ {n} }{n! } } , $$

then

$$ a _ {n} = g ^ {( n ) } ( 0 ) , b _ {n} = h ^ {( n ) } ( 0 ) , $$

and Faà di Bruno's formula can be used to find $ b _ {n} $. For example, if $ f ( g ) = { \mathop{\rm ln} } g $, then

$$ f ^ {( k ) } = ( - 1 ) ^ {k - 1 } ( k - 1 ) !g ^ {- k } \quad ( k \geq 1 ) . $$

Hence, applying the formula and evaluating the result at $ t = 0 $ gives

$$ \tag{a3 } b _ {n} = h ^ {( n ) } ( 0 ) = $$

$$ = \sum _ {k = 1 } ^ { n } ( - 1 ) ^ {k - 1 } ( k - 1 ) ! a _ {0} ^ {- k } B _ {n,k } ( a _ {1} , \dots ,a _ {n - k + 1 } ) { \frac{t ^ {n} }{n! } } . $$

Thus, provided that $ a _ {0} > 0 $,

$$ { \mathop{\rm ln} } \left ( \sum _ {n = 0 } ^ \infty { \frac{a _ {n} t ^ {n} }{n! } } \right ) = { \mathop{\rm ln} } a _ {0} + $$

$$ + \sum _ {n = 1 } ^ \infty \sum _ {k = 1 } ^ { n } ( - 1 ) ^ {k - 1 } ( k - 1 ) ! a _ {0} ^ {- k } B _ {n,k } ( a _ {1} , \dots ,a _ {n - k + 1 } ) { \frac{t ^ {n} }{n! } } . $$

A special case of (a3) is used [a6] to express the cumulants (semi-invariants, cf. Semi-invariant) $ \kappa _ {n} $ of a probability distribution $ \{ p _ {0} ,p _ {1} , \dots \} $ in terms of its moments (cf. Moment)

$$ m _ {n} = \sum _ {r = 0 } ^ \infty r ^ {n} p _ {r} \quad ( n \geq 1 ) , $$

$$ m _ {0} = \sum _ {r = 0 } ^ \infty p _ {r} = 1. $$

The probability generating function of the distribution is

$$ G ( z ) = \sum _ {r = 0 } ^ \infty p _ {r} z ^ {r} , $$

and it is easy to show that

$$ G ( e ^ {t} ) = \sum _ {n = 0 } ^ \infty { \frac{m _ {n} t ^ {n} }{n! } } . $$

The cumulants $ \kappa _ {n} $( $ n \geq 1 $) and their exponential generating function $ L ( t ) $ are defined in terms of $ G ( e ^ {t} ) $ by

$$ L ( t ) = \sum _ {n = 1 } ^ \infty { \frac{\kappa _ {n} t ^ {n} }{n! } } = { \mathop{\rm ln} } G ( e ^ {t} ) = { \mathop{\rm ln} } \sum _ {n = 0 } ^ \infty { \frac{m _ {n} t ^ {n} }{n! } } . $$

Since $ m _ {0} = 1 $, it follows from (a3) that

$$ \kappa _ {n} = \sum _ {k = 1 } ^ { n } ( - 1 ) ^ {k - 1 } ( k - 1 ) ! B _ {n,k } ( m _ {1} \dots m _ {n - k + 1 } ) . $$

Similarly, starting from

$$ G ( e ^ {t} ) = \sum _ {n = 0 } ^ \infty { \frac{m _ {n} t ^ {n} }{n! } } = e ^ {L ( t ) } = { \mathop{\rm exp} } \left ( \sum _ {n = 1 } ^ \infty { \frac{\kappa _ {n} t ^ {n} }{n! } } \right ) , $$

and applying Faà di Bruno's formula with $ f ( g ) = e ^ {g} $ and $ g ( t ) = \sum { {\kappa _ {n} t ^ {n} } / {n! } } $( and noting that in this case $ h ^ {( k ) } ( 0 ) = 1 $ for all $ k \geq 1 $), the inverse relation expressing moments in terms of cumulants reduces to

$$ m _ {n} = Y _ {n} ( \kappa _ {1} , \dots, \kappa _ {n} ) . $$

References

[a1] M. Abramowitz, I. Stegun, "Handbook of mathematical functions" , Dover, reprint (1965)
[a2] E.T. Bell, "Exponential polynomials" Ann. of Math. , 35 (1934) pp. 258–277
[a3] L. Comtet, "Advanced combinatorics" , Reidel (1974)
[a4] F. Faà di Bruno, "Note sur une nouvelle formule du calcul différentiel" Quart. J. Math. , 1 (1855) pp. 359–360
[a5] I.J. Good, "The multivariate saddlepoint method and chi-squared for the multinomial distribution" Ann. Math. Stat. , 32 (1961) pp. 535–548
[a6] E. Lukács, "Applications of Faà di Bruno's formula in mathematical statistics" Amer. Math. Monthly , 62 (1955) pp. 340–348
[a7] J. Riordan, "Combinatorial identities" , Wiley (1968)
[a8] S. Roman, "The umbral calculus" , Acad. Press (1984)
How to Cite This Entry:
Bell polynomial. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bell_polynomial&oldid=17635
This article was adapted from an original article by E.K. Lloyd (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article