Faà di Bruno's formula
Encyclopedia
Faà di Bruno's formula is an identity in mathematics
generalizing the chain rule
to higher derivatives, named after , though he was not the first to state or prove the formula. In 1800, more than 50 years before Faà di Bruno, the French mathematician Louis François Antoine Arbogast stated the formula in a calculus textbook, considered the first published reference on the subject.
Perhaps the most well-known form of Faà di Bruno's formula says that
where the sum is over all n-tuple
s of nonnegative integers (m1, …, mn) satisfying the constraint
Sometimes, to give it a memorable pattern, it is written in a way in which the coefficients that have the combinatorial interpretation discussed below are less explicit:
Combining the terms with the same value of m1 + m2 + ... + mn = k and noticing that m j has to be zero for j > n − k + 1 leads to a somewhat simpler formula expressed in terms of Bell polynomials Bn,k(x1,...,xn−k+1):
where
The pattern is
The factor
corresponds to the partition 2 + 1 + 1 of the integer 4, in the obvious way. The factor 
that goes with it corresponds to the fact that there are three summands in that partition. The coefficient 6 that goes with those factors corresponds to the fact that there are exactly six partitions of a set of four members that break it into one part of size 2 and two parts of size 1.
Similarly, the factor
in the third line corresponds to the partition 2 + 2 of the integer 4, (4, because we are finding the fourth derivative), while 
corresponds to the fact that there are two summands (2 + 2) in that partition. The coefficient 3 corresponds to the fact that there are 3 ways of partitioning 4 objects into groups of 2 (4C2 ÷ 2). The same concept applies to the others.
of size n corresponding to the integer partition
of the integer n is equal to
These coefficients also arise in the Bell polynomials, which are relevant to the study of cumulant
s.
where (as above)
A further generalization, due to Tsoy-Wo Ma, considers the case where y is a vector-valued variable.
Example
The five terms in the following expression correspond in the obvious way to the five partitions of the set { 1, 2, 3 }, and in each case the order of the derivative of f is the number of parts in the partition:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
generalizing the chain rule
Chain rule
In calculus, the chain rule is a formula for computing the derivative of the composition of two or more functions. That is, if f is a function and g is a function, then the chain rule expresses the derivative of the composite function in terms of the derivatives of f and g.In integration, the...
to higher derivatives, named after , though he was not the first to state or prove the formula. In 1800, more than 50 years before Faà di Bruno, the French mathematician Louis François Antoine Arbogast stated the formula in a calculus textbook, considered the first published reference on the subject.
Perhaps the most well-known form of Faà di Bruno's formula says that
where the sum is over all n-tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
s of nonnegative integers (m1, …, mn) satisfying the constraint
Sometimes, to give it a memorable pattern, it is written in a way in which the coefficients that have the combinatorial interpretation discussed below are less explicit:
Combining the terms with the same value of m1 + m2 + ... + mn = k and noticing that m j has to be zero for j > n − k + 1 leads to a somewhat simpler formula expressed in terms of Bell polynomials Bn,k(x1,...,xn−k+1):
Combinatorial form
The formula has a "combinatorial" form:where
- π runs through the set Π of all partitions of the setPartition of a setIn mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
{ 1, ..., n },
- "B ∈ π" means the variable B runs through the list of all of the "blocks" of the partition π, and
- |A| denotes the cardinality of the set A (so that |π| is the number of blocks in the partition π and |B| is the size of the block B).
Explication via an example
The combinatorial form may initially seem forbidding, so let us examine a concrete case, and see what the pattern is:The pattern is
The factor
corresponds to the partition 2 + 1 + 1 of the integer 4, in the obvious way. The factor that goes with it corresponds to the fact that there are three summands in that partition. The coefficient 6 that goes with those factors corresponds to the fact that there are exactly six partitions of a set of four members that break it into one part of size 2 and two parts of size 1.Similarly, the factor
in the third line corresponds to the partition 2 + 2 of the integer 4, (4, because we are finding the fourth derivative), while corresponds to the fact that there are two summands (2 + 2) in that partition. The coefficient 3 corresponds to the fact that there are 3 ways of partitioning 4 objects into groups of 2 (4C2 ÷ 2). The same concept applies to the others.Combinatorics of the Faà di Bruno coefficients
These partition-counting Faà di Bruno coefficients have a "closed-form" expression. The number of partitions of a setPartition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
of size n corresponding to the integer partition
of the integer n is equal to
These coefficients also arise in the Bell polynomials, which are relevant to the study of cumulant
Cumulant
In probability theory and statistics, the cumulants κn of a probability distribution are a set of quantities that provide an alternative to the moments of the distribution. The moments determine the cumulants in the sense that any two probability distributions whose moments are identical will have...
s.
Multivariate version
Let y = g(x1, ..., xn). Then the following identity holds regardless of whether the n variables are all distinct, or all identical, or partitioned into several distinguishable classes of indistinguishable variables (if it seems opaque, see the very concrete example below):where (as above)
- π runs through the set Π of all partitions of the setPartition of a setIn mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
{ 1, ..., n },
- "B ∈ π" means the variable B runs through the list of all of the "blocks" of the partition π, and
- |A| denotes the cardinality of the set A (so that |π| is the number of blocks in the partition π and |B| is the size of the block B).
A further generalization, due to Tsoy-Wo Ma, considers the case where y is a vector-valued variable.
Example
The five terms in the following expression correspond in the obvious way to the five partitions of the set { 1, 2, 3 }, and in each case the order of the derivative of f is the number of parts in the partition:
-
-
-
-
-
-
-
If the three variables are indistinguishable from each other, then three of the five terms above are also indistinguishable from each other, and then we have the classic one-variable formula.
Formal power series version
In the formal power seriesFormal power seriesIn mathematics, formal power series are a generalization of polynomials as formal objects, where the number of terms is allowed to be infinite; this implies giving up the possibility to substitute arbitrary values for indeterminates...
we have the nth derivative at 0:
This should not be construed as the value of a function, since these series are purely formal; there is no such thing as convergence or divergence in this context.
If
and
and
then the coefficient cn (which would be the nth derivative of h evaluated at 0 if we were dealing with convergent series rather than formal power series) is given by
where π runs through the set of all partitions of the set { 1, ..., n } and B1, ..., Bk are the blocks of the partition π, and | Bj | is the number of members of the jth block, for j = 1, ..., k.
This version of the formula is particularly well suited to the purposes of combinatoricsCombinatoricsCombinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
.
We can also write
where Bn,k(a1,...,an−k+1) are Bell polynomials.
A special case
If f(x) = ex then all of the derivatives of f are the same, and are a factor common to every term. In case g(x) is a cumulant-generating function, then f(g(x)) is a moment-generating functionMoment-generating functionIn probability theory and statistics, the moment-generating function of any random variable is an alternative definition of its probability distribution. Thus, it provides the basis of an alternative route to analytical results compared with working directly with probability density functions or...
, and the polynomial in various derivatives of g is the polynomial that expresses the momentMoment (mathematics)In mathematics, a moment is, loosely speaking, a quantitative measure of the shape of a set of points. The "second moment", for example, is widely used and measures the "width" of a set of points in one dimension or in higher dimensions measures the shape of a cloud of points as it could be fit by...
s as functions of the cumulantCumulantIn probability theory and statistics, the cumulants κn of a probability distribution are a set of quantities that provide an alternative to the moments of the distribution. The moments determine the cumulants in the sense that any two probability distributions whose moments are identical will have...
s.
External links
-
-
-
-
-
-