Faà di Bruno's formula is an identity in
mathematics generalizing the
chain rule
In calculus, the chain rule is a formula that expresses the derivative of the composition of two differentiable functions and in terms of the derivatives of and . More precisely, if h=f\circ g is the function such that h(x)=f(g(x)) for every , ...
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 mathematician
Louis François Antoine Arbogast
Louis François Antoine Arbogast (4 October 1759 – 8 April 1803) was a French mathematician. He was born at Mutzig in Alsace and died at Strasbourg, where he was professor. He wrote on series and the derivatives known by his name: he was the ...
had stated the formula in a calculus textbook, which is considered to be 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
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of nonnegative integers (''m''
1, ..., ''m''
''n'') 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 ''m''
1 + ''m''
2 + ... + ''m''
''n'' = ''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 ''B''
''n'',''k''(''x''
1,...,''x''
''n''−''k''+1):
:
Combinatorial form
The formula has a "combinatorial" form:
:
where
* runs through the set Π of all
partitions of the set ,
*"''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'').
Example
The following is a concrete explanation of the combinatorial form for the case.
:
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
ways of partitioning 4 objects into groups of 2. The same concept applies to the others.
A memorizable scheme is as follows:
:
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 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'' corresponding to 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 the integer ''n'' is equal to
:
These coefficients also arise in the
Bell polynomials, which are relevant to the study of
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.
Variations
Multivariate version
Let ''y'' = ''g''(''x''
1, ..., ''x''
''n''). 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 set ,
*"''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'').
More general versions hold for cases where the all functions are vector- and even
Banach-space-valued. In this case one needs to consider the
Fréchet derivative
In mathematics, the Fréchet derivative is a derivative defined on normed spaces. Named after Maurice Fréchet, it is commonly used to generalize the derivative of a real-valued function of a single real variable to the case of a vector-valued ...
or
Gateaux derivative
In mathematics, the Gateaux differential or Gateaux derivative is a generalization of the concept of directional derivative in differential calculus. Named after René Gateaux, a French mathematician who died young in World War I, it is defined ...
.
; Example
The five terms in the following expression correspond in the obvious way to the five partitions of the set , 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
Suppose
and
are
formal power series and
.
Then the composition
is again a formal power series,
:
where ''c''
0 = ''a''
0 and the other coefficient ''c''
''n'' for ''n'' ≥ 1
can be expressed as a sum over
compositions
Composition or Compositions may refer to:
Arts and literature
* Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
of ''n'' or as an equivalent sum over
partitions
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 ''n'':
:
where
:
is the set of compositions of ''n'' with ''k'' denoting the number of parts,
or
:
where
:
is the set of partitions of ''n'' into ''k'' parts, in frequency-of-parts form.
The first form is obtained by picking out the coefficient of ''x''
''n''
in
"by inspection", and the second form
is then obtained by collecting like terms, or alternatively, by applying the
multinomial theorem
In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials.
Theorem
For any positive integer ...
.
The special case ''f''(''x'') = ''e''
''x'', ''g''(''x'') = Σ
''n'' ≥ 1 ''a''
''n'' /''n''! ''x''
''n'' gives the
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 st ...
.
The special case ''f''(''x'') = 1/(1 − ''x''), ''g''(''x'') = Σ
''n'' ≥ 1 (−''a''
''n'') ''x''
''n'' gives an expression for the
reciprocal
Reciprocal may refer to:
In mathematics
* Multiplicative inverse, in mathematics, the number 1/''x'', which multiplied by ''x'' gives the product 1, also known as a ''reciprocal''
* Reciprocal polynomial, a polynomial obtained from another pol ...
of the formal power series Σ
''n'' ≥ 0 ''a''
''n'' ''x''
''n'' in the case ''a''
0 = 1.
Stanley
[See the "compositional formula" in Chapter 5 of ]
gives a version for exponential power series.
In the
formal power series
:
we have the ''n''th 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 ''c''
''n'' (which would be the ''n''th 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 and ''B''
1, ..., ''B''
''k'' are the blocks of the partition , and , ''B''
''j'' , is the number of members of the ''j''th block, for ''j'' = 1, ..., ''k''.
This version of the formula is particularly well suited to the purposes of
combinatorics.
We can also write with respect to the notation above
:
where ''B''
''n'',''k''(''a''
1,...,''a''
''n''−''k''+1) are
Bell polynomials.
A special case
If ''f''(''x'') = ''e''
''x'', then all of the derivatives of ''f'' are the same and are a factor common to every term:
:
where
is the ''n''th
complete exponential Bell polynomial.
In case ''g''(''x'') is a
cumulant-generating function, then ''f''(''g''(''x'')) is a
moment-generating function
In probability theory and statistics, the moment-generating function of a real-valued random variable is an alternative specification of its probability distribution. Thus, it provides the basis of an alternative route to analytical results compare ...
, and the polynomial in various derivatives of ''g'' is the polynomial that expresses the
moments as functions of the
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.
See also
*
*
*
*
*
*
*
*
*
Notes
References
Historical surveys and essays
*. "''The mathematical work''" is an essay on the mathematical activity, describing both the research and teaching activity of Francesco Faà di Bruno.
*.
*.
Research works
*, Entirely freely available from
Google books
Google Books (previously known as Google Book Search, Google Print, and by its code-name Project Ocean) is a service from Google Inc. that searches the full text of books and magazines that Google has scanned, converted to text using optical ...
.
*. Entirely freely available from
Google books
Google Books (previously known as Google Book Search, Google Print, and by its code-name Project Ocean) is a service from Google Inc. that searches the full text of books and magazines that Google has scanned, converted to text using optical ...
. A well-known paper where Francesco Faà di Bruno presents the two versions of the formula that now bears his name, published in the journal founded by
Barnaba Tortolini
Barnaba Tortolini (19 November 1808 – 24 August 1874) was a 19th-century Italian priest and mathematician who played an early active role in advancing the scientific unification of the Italian states. He founded the first Italian scientific ...
.
*. Entirely freely available from
Google books
Google Books (previously known as Google Book Search, Google Print, and by its code-name Project Ocean) is a service from Google Inc. that searches the full text of books and magazines that Google has scanned, converted to text using optical ...
.
*. Entirely freely available from
Google books
Google Books (previously known as Google Book Search, Google Print, and by its code-name Project Ocean) is a service from Google Inc. that searches the full text of books and magazines that Google has scanned, converted to text using optical ...
.
*
Flanders, Harley (2001) "From Ford to Faa",
American Mathematical Monthly 108(6): 558–61
*.
*
*.
*, available a
NUMDAM This paper, according to is one of the precursors of : note that the author signs only as "T.A.", and the attribution to J. F. C. Tiburce Abadie is due again to Johnson.
*, available a
NUMDAM This paper, according to is one of the precursors of : note that the author signs only as "A.", and the attribution to J. F. C. Tiburce Abadie is due again to Johnson.
External links
*
{{DEFAULTSORT:Faa de Bruno's formula
Differentiation rules
Differential calculus
Differential algebra
Enumerative combinatorics
Factorial and binomial topics
Theorems in analysis