World Library  
Flag as Inappropriate
Email this Article
 

Faà di Bruno's formula

Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives, named after Francesco Faà di Bruno (1855, 1857), 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,[1] considered the first published reference on the subject.[2]

Perhaps the most well-known form of Faà di Bruno's formula says that

{d^n \over dx^n} f(g(x))=\sum \frac{n!}{m_1!\,1!^{m_1}\,m_2!\,2!^{m_2}\,\cdots\,m_n!\,n!^{m_n}}\cdot f^{(m_1+\cdots+m_n)}(g(x))\cdot \prod_{j=1}^n\left(g^{(j)}(x)\right)^{m_j},

where the sum is over all n-tuples of nonnegative integers (m1, …, mn) 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:

{d^n \over dx^n} f(g(x)) =\sum \frac{n!}{m_1!\,m_2!\,\cdots\,m_n!}\cdot f^{(m_1+\cdots+m_n)}(g(x))\cdot \prod_{j=1}^n\left(\frac{g^{(j)}(x)}{j!}\right)^{m_j}.

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,...,xnk+1):

{d^n \over dx^n} f(g(x)) = \sum_{k=0}^n f^{(k)}(g(x))\cdot B_{n,k}\left(g'(x),g''(x),\dots,g^{(n-k+1)}(x)\right).

Contents

  • Combinatorial form 1
  • Explanation via an example 2
  • Combinatorics of the Faà di Bruno coefficients 3
  • Variations 4
    • Multivariate version 4.1
    • Formal power series version 4.2
    • A special case 4.3
  • Notes 5
  • References 6
  • External links 7

Combinatorial form

The formula has a "combinatorial" form:

{d^n \over dx^n} f(g(x))=(f\circ g)^{(n)}(x)=\sum_{\pi\in\Pi} f^{(\left|\pi\right|)}(g(x))\cdot\prod_{B\in\pi}g^{(\left|B\right|)}(x)

where

  • "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).

Explanation via an example

The combinatorial form may initially seem forbidding, so let us examine a concrete case, and see what the pattern is:

\begin{align} (f\circ g)''''(x) & = f''''(g(x))g'(x)^4 + 6f'''(g(x))g''(x)g'(x)^2 \\[8pt] & {} \quad+\; 3f''(g(x))g''(x)^2 + 4f''(g(x))g'''(x)g'(x) \\[8pt] & {} \quad+\; f'(g(x))g''''(x). \end{align}

The pattern is

\begin{align} g'(x)^4 & & \leftrightarrow & & 1+1+1+1 & & \leftrightarrow & & f''''(g(x)) & & \leftrightarrow & & 1 \\[12pt] g''(x)g'(x)^2 & & \leftrightarrow & & 2+1+1 & & \leftrightarrow & & f'''(g(x)) & & \leftrightarrow & & 6 \\[12pt] g''(x)^2 & & \leftrightarrow & & 2+2 & & \leftrightarrow & & f''(g(x)) & & \leftrightarrow & & 3 \\[12pt] g'''(x)g'(x) & & \leftrightarrow & & 3+1 & & \leftrightarrow & & f''(g(x)) & & \leftrightarrow & & 4 \\[12pt] g''''(x) & & \leftrightarrow & & 4 & & \leftrightarrow & & f'(g(x)) & & \leftrightarrow & & 1. \end{align}

The factor \scriptstyle g''(x)g'(x)^2 \; corresponds to the partition 2 + 1 + 1 of the integer 4, in the obvious way. The factor \scriptstyle 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 \scriptstyle 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 \scriptstyle 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{1}{2}\tbinom{4}{2}=3 ways of partitioning 4 objects into groups of 2. The same concept applies to the others.

A memorizable scheme is as follows:

\begin{align} & \frac{D^1(f\circ{}g)}{1!} & = \left(f^{(1)}\circ{}g\right)\frac{\frac{g^{(1)} }{1!} }{1!} \\[8pt] & \frac{D^2(f\circ g)}{2!} & = \left(f^{(1)}\circ{}g\right)\frac{\frac{g^{(2)} }{2!} }{1!} & {} + \left(f^{(2)}\circ{}g\right)\frac{\frac{g^{(1)} }{1!}\frac{g^{(1)} }{1!} }{2!} \\[8pt] & \frac{D^3(f\circ g)}{3!} & = \left(f^{(1)}\circ{}g\right)\frac{\frac{g^{(3)} }{3!} }{1!} & {} + \left(f^{(2)}\circ{}g\right)\frac{\frac{g^{(1)} }{1!} }{1!}\frac{\frac{g^{(2)} }{2!} }{1!} & {} + \left(f^{(3)}\circ{}g\right)\frac{\frac{g^{(1)} }{1!}\frac{g^{(1)} }{1!}\frac{g^{(1)} }{1!} }{3!} \\[8pt] & \frac{D^4(f\circ g)}{4!} & = \left(f^{(1)}\circ{}g\right)\frac{\frac{g^{(4)} }{4!} }{1!} & {} + \left(f^{(2)}\circ{}g\right)\left(\frac{\frac{g^{(1)} }{1!} }{1!}\frac{\frac{g^{(3)} }{3!} }{1!}+\frac{\frac{g^{(2)} }{2!}\frac{g^{(2)} }{2!} }{2!}\right) & {} + \left(f^{(3)}\circ{}g\right)\frac{\frac{g^{(1)} }{1!}\frac{g^{(1)} }{1!} }{2!}\frac{\frac{g^{(2)} }{2!} }{1!} & {} + \left(f^{(4)}\circ{}g\right)\frac{\frac{g^{(1)} }{1!}\frac{g^{(1)} }{1!}\frac{g^{(1)} }{1!}\frac{g^{(1)} }{1!} }{4!} \end{align}

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 of size n corresponding to the integer partition

\displaystyle n=\underbrace{1+\cdots+1}_{m_1} \,+\, \underbrace{2+\cdots+2}_{m_2} \,+\, \underbrace{3+\cdots+3}_{m_3}+\cdots

of the integer n is equal to

\frac{n!}{m_1!\,m_2!\,m_3!\,\cdots 1!^{m_1}\,2!^{m_2}\,3!^{m_3}\,\cdots}.

These coefficients also arise in the Bell polynomials, which are relevant to the study of cumulants.

Variations

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):[3]

{\partial^n \over \partial x_1 \cdots \partial x_n}f(y) = \sum_{\pi\in\Pi} f^{(\left|\pi\right|)}(y)\cdot\prod_{B\in\pi} {\partial^{\left|B\right|}y \over \prod_{j\in B} \partial x_j}

where (as above)

  • "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.[4] The general form, for variational calculus (Gâteaux differentials are the most general form of differential), was derived in 2012.[5]

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:

\begin{align} {\partial^3 \over \partial x_1\, \partial x_2\, \partial x_3}f(y) & = f'(y){\partial^3 y \over \partial x_1\, \partial x_2\, \partial x_3} \\[10pt] & {} + f''(y) \left( {\partial y \over \partial x_1} \cdot{\partial^2 y \over \partial x_2\, \partial x_3} +{\partial y \over \partial x_2} \cdot{\partial^2 y \over \partial x_1\, \partial x_3} + {\partial y \over \partial x_3} \cdot{\partial^2 y \over \partial x_1\, \partial x_2}\right) \\[10pt] & {} + f'''(y) {\partial y \over \partial x_1} \cdot{\partial y \over \partial x_2} \cdot{\partial y \over \partial x_3}. \end{align}

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_{n=0}^\infty {a_n} x^n and g(x)=\sum_{n=0}^\infty {b_n} x^n are formal power series and b_0 = 0.

Then the composition f \circ g is again a formal power series,

f(g(x))=\sum_{n=0}^\infty{c_n}x^n,

and the coefficient cn, for n ≥ 1, can be expressed as a sum over compositions of n or as an equivalent sum over partitions of n :

c_{n} = \sum_{\mathbf{i}\in \mathcal{C}_{n}} a_{k} b_{i_{1}} b_{i_{2}} \cdots b_{i_{k}},

where

\mathcal{C}_{n}=\{(i_1,i_2,\dots,i_k)\,:\ 1 \le k \le n,\ i_1+i_2+ \cdots + i_k=n\}

is the set of compositions of n with k denoting the number of parts,

or

c_{n} = \sum_{k=1}^{n} a_{k} \sum_{\mathbf{\pi}\in \mathcal{P}_{n,k}} \binom{k}{\pi_{1},\pi_{2}, ..., \pi_{n}} b_{1}^{\pi_{1}} b_{2}^{\pi_{2}}\cdots b_{n}^{\pi_{n}},

where

\mathcal{P}_{n,k}=\{(\pi_1,\pi_2,\dots,\pi_n)\,:\ \pi_1+\pi_2+ \cdots + \pi_n=k,\ \pi_{1}\cdot 1+\pi_{2}\cdot 2+ \cdots + \pi_{n}\cdot n = n \}

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 xn in (b_{1}x+b_{2}x^2+ \cdots)^{k} "by inspection", and the second form is then obtained by collecting like terms, or alternatively, by applying the multinomial theorem.

The special case f(x) = ex, g(x) = ∑n ≥ 1 an /n! xn gives the exponential formula. The special case f(x) = 1/(1-x), g(x) = ∑n ≥ 1 (-an ) xn gives an expression for the reciprocal of the formal power series n ≥ 0 an xn in the case a0 = 1 .

Stanley [6] gives a version for exponential power series. In the formal power series

f(x)=\sum_n {a_n \over n!}x^n,

we have the nth derivative at 0:

f^{(n)}(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_{n=0}^\infty {b_n \over n!} x^n

and

f(x)=\sum_{n=1}^\infty {a_n \over n!} x^n

and

g(f(x))=h(x)=\sum_{n=0}^\infty{c_n \over n!}x^n,

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

c_n=\sum_{\pi=\left\{\,B_1,\,\dots,\,B_k\,\right\}} a_{\left|B_1\right|}\cdots a_{\left|B_k\right|} b_k

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 combinatorics.

We can also write with respect to the notation above

g(f(x)) =b_0+ \sum_{n=1}^\infty {\sum_{k=1}^{n} b_k B_{n,k}(a_1,\dots,a_{n-k+1}) \over n!} x^n,

where Bn,k(a1,...,ank+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 function, and the polynomial in various derivatives of g is the polynomial that expresses the moments as functions of the cumulants.

Notes

  1. ^ Arbogast, L.F.A. (1800). Du calcul des derivations. Strasbourg: Levrault. 
  2. ^ Craik, A.D.D. (2005). "Prehistory of Faà di Bruno's Formula".  
  3. ^ Hardy, Michael (2006). "Combinatorics of Partial Derivatives". Electronic Journal of Combinatorics 13 (1): R1. 
  4. ^ Tsoy Wo Ma (2009). "Higher Chain Formula proved by Combinatorics". Electronic Journal of Combinatorics 16 (1): N21. 
  5. ^ Clark, Daniel; Houssineau, Jeremie (2012). "Hierarchical stochastic population processes".  
  6. ^ See the "compositional formula" in Chapter 5 of Stanley, Richard P. (1999) [1997]. Enumerative Combinatorics. Cambridge University Press.  

References

  • . Google books, Entirely freely available from  
  • Craik, Alex D. D. (February 2005), "Prehistory of Faà di Bruno's Formula",  .
  •  . Entirely freely available from Google books. 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.
  • Faà di Bruno, F. (1857), "Note sur une nouvelle formule de calcul differentiel",  . Entirely freely available from Google books.
  • Faà di Bruno, Francesco (1859), Théorie générale de l'élimination (in French), Paris: Leiber et Faraguet, pp. x+224 . Entirely freely available from Google books.
  • Fraenkel, L. E. (1978), "Formulae for high derivatives of composite functions",  
  • Johnson, Warren P. (March 2002), "The Curious History of Faà di Bruno's Formula" (PDF), .  
  •  
  • .  
  • T. A., (Tiburce Abadie, J. F. C.) (1850), "Sur la différentiation des fonctions de fonctions", : note that the author signs only as "T.A.", and the attribution to J. F. C. Tiburce Abadie is due again to Johnson. Faà di Bruno 1855, p. 228) is one of the precursors of Johnson (2002, available at NUMDAM. This paper, according to  
  • A., (Tiburce Abadie, J. F. C.) (1852), "Sur la différentiation des fonctions de fonctions. Séries de Burmann, de Lagrange, de Wronski", : note that the author signs only as "A.", and the attribution to J. F. C. Tiburce Abadie is due again to Johnson. Faà di Bruno 1855, p. 228) is one of the precursors of Johnson (2002, available at NUMDAM. This paper, according to  

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.