HOME

TheInfoList



OR:

Faà di Bruno's formula is an identity in
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
generalizing the
chain rule In calculus, the chain rule is a formula that expresses the derivative of the Function composition, 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 ...
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 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 f(g(x))=\sum \frac\cdot f^(g(x))\cdot \prod_^n\left(g^(x)\right)^, where the sum is over all n-
tuple In mathematics, a tuple is a finite sequence or ''ordered list'' of numbers or, more generally, mathematical objects, which are called the ''elements'' of the tuple. An -tuple is a tuple of elements, where is a non-negative integer. There is o ...
s of nonnegative integers (m_1,\ldots,m_n) satisfying the constraint 1\cdot m_1+2\cdot m_2+3\cdot m_3+\cdots+n\cdot m_n=n. 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: : f(g(x)) =\sum \frac\cdot f^(g(x))\cdot \prod_^n\left(\frac\right)^. Combining the terms with the same value of m_1+m_2+\cdots+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 partial (or incomplete) exponential Bell polynomials B_(x_1,\ldots,x_): : f(g(x)) = \sum_^n f^(g(x))\cdot B_\left(g'(x),g''(x),\dots,g^(x)\right). This formula works for all n \geq 0, however for n>0 the polynomials B_ are zero and thus summation in the formula can start with k=1.


Combinatorial form

The formula has a "combinatorial" form: : f(g(x))=(f\circ g)^(x)=\sum_ f^(g(x))\cdot\prod_g^(x) where * \pi runs through the set \Pi of all partitions of the set \, *"B\in\pi" means the variable B runs through the list of all of the "blocks" of the partition \pi, and *, A, denotes the cardinality of the set A (so that , \pi, is the number of blocks in the partition \pi and , B, is the size of the block B).


Example

The following is a concrete explanation of the combinatorial form for the n=4 case. : \begin (f\circ g)'(x) = & f'(g(x))g'(x)^4 + 6f(g(x))g''(x)g'(x)^2 \\ pt& +\; 3f''(g(x))g''(x)^2 + 4f''(g(x))g(x)g'(x) \\ pt& +\; f'(g(x))g'(x). \end The pattern is: : \begin g'(x)^4 & & \leftrightarrow & & 1+1+1+1 & & \leftrightarrow & & f'(g(x)) & & \leftrightarrow & & 1 \\ 2pt g''(x)g'(x)^2 & & \leftrightarrow & & 2+1+1 & & \leftrightarrow & & f(g(x)) & & \leftrightarrow & & 6 \\ 2ptg''(x)^2 & & \leftrightarrow & & 2+2 & & \leftrightarrow & & f''(g(x)) & & \leftrightarrow & & 3 \\ 2ptg(x)g'(x) & & \leftrightarrow & & 3+1 & & \leftrightarrow & & f''(g(x)) & & \leftrightarrow & & 4 \\ 2ptg'(x) & & \leftrightarrow & & 4 & & \leftrightarrow & & f'(g(x)) & & \leftrightarrow & & 1 \end The factor g''(x)g'(x)^2 corresponds to the partition 2 + 1 + 1 of the integer 4, in the obvious way. The factor f(g(x)) 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 g''(x)^2 in the third line corresponds to the partition 2 + 2 of the integer 4, (4, because we are finding the fourth derivative), while f''(g(x)) corresponds to the fact that there are ''two'' summands (2 + 2) in that partition. The coefficient 3 corresponds to the fact that there are \tfrac\tbinom=3 ways of partitioning 4 objects into groups of 2. The same concept applies to the others. A memorizable scheme is as follows: : \begin & \frac & = \left(f^\circg\right)\frac \\ pt& \frac & = \left(f^\circg\right)\frac & + \left(f^\circg\right)\frac \\ pt& \frac & = \left(f^\circg\right)\frac & + \left(f^\circg\right)\frac\frac & + \left(f^\circg\right)\frac \\ pt& \frac & = \left(f^\circg\right)\frac & + \left(f^\circg\right)\left(\frac\frac+\frac\right) & + \left(f^\circg\right)\frac\frac & + \left(f^\circg\right)\frac \end


Variations


Multivariate version

Let y=g(x_1,\dots,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): :f(y) = \sum_ f^(y)\cdot\prod_ where (as above) * \pi runs through the set \Pi of all partitions of the set \, *"B\in\pi" means the variable B runs through the list of all of the "blocks" of the partition \pi, and *, A, denotes the cardinality of the set A (so that , \pi, is the number of blocks in the partition \pi 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 or Gateaux derivative. ; 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: : \begin f(y) = & f'(y) \\ 0pt& + f''(y) \left( \cdot + \cdot + \cdot\right) \\ 0pt& + f(y) \cdot \cdot. \end 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 f(x)=\sum_^\infty x^n and g(x)=\sum_^\infty x^n are
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 su ...
and b_0 = 0. Then the composition f \circ g is again a formal
power series In mathematics, a power series (in one variable) is an infinite series of the form \sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots where ''a_n'' represents the coefficient of the ''n''th term and ''c'' is a co ...
, :f(g(x))=\sum_^\inftyx^n, where c_0=a_0 and the other coefficient c_n for n\geq 1 can be expressed as a sum over compositions of n or as an equivalent sum over integer partitions of n: :c_ = \sum_ a_ b_ b_ \cdots b_, where :\mathcal_=\ is the set of compositions of n with k denoting the number of parts, or :c_ = \sum_^ a_ \sum_ \binom b_^ b_^\cdots b_^, where :\mathcal_=\ 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 (b_x+b_x^2+ \cdots)^ "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)=\sum_\fraca_n x^n gives the exponential formula. The special case f(x)=1/(1-x), g(x)=\sum_ (-a_n) x^n gives an expression for the reciprocal of the formal power series \sum_ a_n x^n in the case a_0=1. StanleySee the "compositional formula" in Chapter 5 of gives a version for exponential power series. In the
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 su ...
:f(x)=\sum_n x^n, we have the nth derivative at 0: :f^(0)=a_n. 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 :g(x)=\sum_^\infty x^n and :f(x)=\sum_^\infty x^n and :g(f(x))=h(x)=\sum_^\inftyx^n, then the coefficient c_n (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 :c_n=\sum_ a_\cdots a_ b_k where \pi runs through the set of all partitions of the set \ and B_1,\ldots,B_k are the blocks of the partition \pi, and , B_j, is the number of members of the jth block, for j=1,\ldots,k. This version of the formula is particularly well suited to the purposes of
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
. We can also write with respect to the notation above :g(f(x)) = b_0+ \sum_^\infty \frac x^n, where B_(a_1,\ldots,a_) 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: : e^ = e^ B_ \left(g'(x),g''(x), \dots, g^(x)\right), where B_n(x) 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, and the polynomial in various derivatives of g is the polynomial that expresses the moments as functions of the cumulants.


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 that searches the full text of books and magazines that Google has scanned, converted to text using optical charac ...
. *. 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 that searches the full text of books and magazines that Google has scanned, converted to text using optical charac ...
. 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. *. 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 that searches the full text of books and magazines that Google has scanned, converted to text using optical charac ...
. *. 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 that searches the full text of books and magazines that Google has scanned, converted to text using optical charac ...
. * Flanders, Harley (2001) "From Ford to Faa",
American Mathematical Monthly ''The American Mathematical Monthly'' is a peer-reviewed scientific journal of mathematics. It was established by Benjamin Finkel in 1894 and is published by Taylor & Francis on behalf of the Mathematical Association of America. It is an exposi ...
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 mathematical analysis