View source for Faà di Bruno's formula

{{short description|Generalized chain rule in calculus}}
{{Calculus |Differential}}
'''Faà di Bruno's formula''' is an identity in [[mathematics]] generalizing the [[chain rule]] to higher derivatives. It is named after {{harvs|txt|authorlink=Francesco Faà di Bruno|first=Francesco|last= Faà di Bruno|year=1855|year2=1857}}, 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,<ref>{{harv|Arbogast|1800}}.</ref> which is considered to be the first published reference on the subject.<ref>According to {{harvtxt|Craik|2005|pp=120–122}}: see also the analysis of Arbogast's work by {{harvtxt|Johnson|2002|p=230}}.</ref>

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

<math display=block>{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},</math>

where the sum is over all <math>n</math>-[[tuple]]s of nonnegative integers <math>(m_1,\ldots,m_n)</math> satisfying the constraint

<math display=block>1\cdot m_1+2\cdot m_2+3\cdot m_3+\cdots+n\cdot m_n=n.</math>

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:

:<math>{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}.</math>

Combining the terms with the same value of <math>m_1+m_2+\cdots+m_n=k</math>
and noticing that <math>m_j</math> has to be zero for <math>j>n-k+1</math> leads to a somewhat simpler formula expressed in terms of partial (or incomplete) exponential [[Bell polynomials]] 
<math>B_{n,k}(x_1,\ldots,x_{n-k+1})</math>, <math>n \geq 1</math>:

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

== Combinatorial form ==

The formula has a "combinatorial" form:

:<math>{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)</math>

where

* <math>\pi</math> runs through the set <math>\Pi</math> of all [[partition of a set|partitions of the set]] <math>\{1,\ldots,n\}</math>,
*"<math>B\in\pi</math>" means the variable <math>B</math> runs through the list of all of the "blocks" of the partition <math>\pi</math>, and
*<math>|A|</math> denotes the cardinality of the set <math>A</math> (so that <math>|\pi|</math> is the number of blocks in the partition <math>\pi</math> and <math>|B|</math> is the size of the block <math>B</math>).

==Example==
The following is a concrete explanation of the combinatorial form for the <math>n=4</math> case.

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

The pattern is:

:<math>
\begin{array}{cccccc}
  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{array}
</math>

The factor <math>g''(x)g'(x)^2 </math> corresponds to the partition 2 + 1 + 1 of the integer 4, in the obvious way.  The factor <math>f'''(g(x))</math> 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 <math>g''(x)^2 </math> in the third line corresponds to the partition 2 + 2 of the integer 4, (4, because we are finding the fourth derivative), while <math>f''(g(x)) </math> corresponds to the fact that there are ''two'' summands (2&nbsp;+&nbsp;2) in that partition. The coefficient 3 corresponds to the fact that there are <math>\tfrac{1}{2}\tbinom{4}{2}=3</math> ways of partitioning 4 objects into groups of&nbsp;2. The same concept applies to the others.

A memorizable scheme is as follows:

: <math>\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}</math>

==Variations==

===Multivariate version===

Let <math>y=g(x_1,\dots,x_n)</math>. Then the following identity holds regardless of whether the <math>n</math> 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):<ref>{{cite journal |last=Hardy |first=Michael |title=Combinatorics of Partial Derivatives |journal=Electronic Journal of Combinatorics |volume=13 |issue=1 |year=2006 |pages=R1 |doi=10.37236/1027 |s2cid=478066 |url=http://www.combinatorics.org/Volume_13/Abstracts/v13i1r1.html|doi-access=free }}</ref>

:<math>{\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}</math>

where (as above)

* <math>\pi</math> runs through the set <math>\Pi</math> of all [[partition of a set|partitions of the set]] <math>\{1,\ldots,n\}</math>,
*"<math>B\in\pi</math>" means the variable <math>B</math> runs through the list of all of the "blocks" of the partition <math>\pi</math>, and
*<math>|A|</math> denotes the cardinality of the set <math>A</math> (so that <math>|\pi|</math> is the number of blocks in the partition <math>\pi</math> and 
<math>|B|</math> is the size of the block <math>B</math>).

More general versions hold for cases where the all functions are vector- and even [[Banach space|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 <math>\{1,2,3\}</math>, and in each case the order of the derivative of <math>f</math> is the number of parts in the partition:

:<math>
\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}
</math>

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===<!-- This section is linked from [[Formal power series]] -->
Suppose <math>f(x)=\sum_{n=0}^\infty {a_n} x^n</math> and <math>g(x)=\sum_{n=0}^\infty {b_n} x^n</math> are [[formal power series]] and <math>b_0 = 0</math>.

Then the composition <math>f \circ g</math> is again a formal [[power series]],
:<math>f(g(x))=\sum_{n=0}^\infty{c_n}x^n,</math>
where <math>c_0=a_0</math> and the other coefficient <math>c_n</math> for <math>n\geq 1</math> 
can be expressed as a sum over [[Composition (combinatorics)|compositions]] of <math>n</math> or as an equivalent sum over [[integer partition]]s of <math>n</math>:
:<math>c_{n} = \sum_{\mathbf{i}\in \mathcal{C}_{n}} a_{k} b_{i_{1}} b_{i_{2}} \cdots b_{i_{k}}, </math>
where 
:<math>\mathcal{C}_{n}=\{(i_1,i_2,\dots,i_k)\,:\ 1 \le k \le n,\ i_1+i_2+ \cdots + i_k=n\}</math>
is the set of compositions of <math>n</math> with <math>k</math> denoting the number of parts,

or
:<math>c_{n} = \sum_{k=1}^{n}  a_{k} \sum_{\mathbf{\pi}\in \mathcal{P}_{n,k}} \binom{k}{\pi_{1},\pi_{2}, \ldots, \pi_{n}} b_{1}^{\pi_{1}} b_{2}^{\pi_{2}}\cdots b_{n}^{\pi_{n}}, </math>
where
:<math>\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 \}</math>
is the set of partitions of <math>n</math> into <math>k</math> parts, in frequency-of-parts form.

The first form is obtained by picking out the  coefficient of <math>x^n</math>
in <math>(b_{1}x+b_{2}x^2+ \cdots)^{k} </math> "by inspection", and the second form
is then obtained by collecting like terms, or alternatively, by applying the [[multinomial theorem]].

The special case <math>f(x)=e^x</math>, <math>g(x)=\sum_{n\geq 1}\frac{1}{n!}a_n x^n</math> gives the [[exponential formula]].
The special case <math>f(x)=1/(1-x)</math>, <math>g(x)=\sum_{n\geq 1} (-a_n) x^n</math>
gives an expression for the [[Reciprocal (mathematics)|reciprocal]] of the formal power series 
<math>\sum_{n\geq 0} a_n x^n</math> in the case <math>a_0=1</math>.

Stanley<ref>See the "compositional formula" in Chapter 5 of {{cite book |last=Stanley |first=Richard P. |title=Enumerative Combinatorics |orig-year=1997 |year=1999 |isbn=978-0-521-55309-4|publisher=Cambridge University Press |url=http://www-math.mit.edu/~rstan/ec/}}</ref>
gives a version for exponential power series.
In the [[formal power series]]

:<math>f(x)=\sum_n {\frac{a_n}{n!}}x^n,</math>

we have the <math>n</math>th derivative at 0:

:<math>f^{(n)}(0)=a_n. </math>

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

:<math>g(x)=\sum_{n=0}^\infty {\frac{b_n}{n!}} x^n</math>

and

:<math>f(x)=\sum_{n=1}^\infty {\frac{a_n}{n!}} x^n</math>

and

:<math>g(f(x))=h(x)=\sum_{n=0}^\infty{\frac{c_n}{n!}}x^n,</math>

then the coefficient <math>c_n</math> (which would be the <math>n</math>th derivative of <math>h</math> evaluated at 0 if we were dealing with convergent series rather than formal power series) is given by

:<math>c_n=\sum_{\pi=\left\{B_1,\ldots,B_k\right\}} a_{\left|B_1\right|}\cdots a_{\left|B_k\right|} b_k</math>

where <math>\pi</math> runs through the set of all partitions of the set <math>\{1,\ldots,n\}</math> and <math>B_1,\ldots,B_k</math>
are the blocks of the partition <math>\pi</math>, and <math>|B_j|</math>
is the number of members of the <math>j</math>th block, for <math>j=1,\ldots,k</math>.

This version of the formula is particularly well suited to the purposes of [[combinatorics]].

We can also write with respect to the notation above

:<math>g(f(x)) = b_0+ \sum_{n=1}^\infty \frac{\sum_{k=1}^n b_k B_{n,k}(a_1,\ldots,a_{n-k+1})}{n!} x^n,</math>

where <math>B_{n,k}(a_1,\ldots,a_{n-k+1})</math> are [[Bell polynomials]].

===A special case===

If <math>f(x) = e^x</math>, then all of the derivatives of <math>f</math> are the same and are a factor common to every term:  

:<math>{d^n \over dx^n} e^{g(x)} =  e^{g(x)} B_{n} \left(g'(x),g''(x), \dots, g^{(n)}(x)\right),</math>

where <math>B_n(x)</math> is the ''n''th [[Bell polynomials|complete exponential Bell polynomial]].

In case <math>g(x)</math> is a [[cumulant-generating function]], then <math>f(g(x))</math>
is a [[moment-generating function]], and the polynomial in various derivatives of <math>g</math> is the polynomial that expresses the [[moment (mathematics)|moment]]s as functions of the [[cumulant]]s.

==See also==

* {{annotated link|Chain rule}}
* {{annotated link|Differentiation of trigonometric functions}}
* {{annotated link|Differentiation rules}}
* {{annotated link|General Leibniz rule}}
* {{annotated link|Inverse functions and differentiation}}
* {{annotated link|Linearity of differentiation}}
* {{annotated link|Product rule}}
* {{annotated link|Table of derivatives}}
* {{annotated link|Vector calculus identities}}

==Notes==
{{reflist|2}}

==References==

===Historical surveys and essays===
*{{Citation
  | last = Brigaglia
  | first = Aldo
  | editor-last = Giacardi
  | editor-first = Livia
  | contribution = L'Opera Matematica
  | title = Francesco Faà di Bruno. Ricerca scientifica insegnamento e divulgazione
  | place = [[Torino]]
  | language = it
  | publisher = Deputazione Subalpina di Storia Patria
  | year = 2004
  | series = Studi e fonti per la storia dell'Università di Torino
  | volume = XII
  | pages = 111–172}}. "''The mathematical work''" is an essay on the mathematical activity, describing both the research and teaching activity of Francesco Faà di Bruno.
*{{Citation
 | first=Alex D. D.
 | last=Craik 
 | title=Prehistory of Faà di Bruno's Formula 
 | journal=[[American Mathematical Monthly]] 
 | volume=112 
 | date=February 2005
 | pages=217–234 
 | issue=2 
 | jstor = 30037410
 | doi=10.2307/30037410
 | mr= 2121322 
 | zbl= 1088.01008
}}.
*{{Citation
  | last = Johnson
  | first = Warren P.
  | title = The Curious History of Faà di Bruno's Formula
  | journal = [[American Mathematical Monthly]]
  | volume = 109
  | issue = 3
  | pages = 217–234
  | date=March 2002
  | url = https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Johnson217-234.pdf
  | jstor = 2695352
  | doi = 10.2307/2695352
  | mr = 1903577
  | zbl = 1024.01010
| citeseerx = 10.1.1.109.4135
  }}.

===Research works===
*{{Citation
 | first = L. F. A.
 | last=Arbogast 
 | author-link= Louis François Antoine Arbogast
 | title=Du calcul des derivations
 | trans-title=On the calculus of derivatives
 | year=1800 
 | language=fr
 | publisher=Levrault 
 | place=Strasbourg 
 | url=https://books.google.com/books?id=YoPq8uCy5Y8C
 | pages= xxiii+404
}}, Entirely freely available from [[Google books]].
*{{Citation
 | first=F.
 | last=Faà di Bruno 
 | author-link=Francesco Faà di Bruno 
 | title= Sullo sviluppo delle funzioni
 | trans-title=On the development of the functions
 | language = it
 | journal= Annali di Scienze Matematiche e Fisiche
 | lccn=06036680
 | volume= 6
 | year= 1855
 | pages= 479–480
 | url = https://books.google.com/books?id=ddE3AAAAMAAJ&pg=PA479
}}. 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]].
*{{Citation
 | first=F.
 | last=Faà di Bruno
 | title= Note sur une nouvelle formule de calcul differentiel
 | trans-title=On a new formula of differential calculus
 | language = fr
 | journal= [[The Quarterly Journal of Pure and Applied Mathematics]]
 | volume= 1
 | year=1857 
 | pages= 359–360
 | url = https://books.google.com/books?id=7BELAAAAYAAJ&pg=PA359
}}. Entirely freely available from [[Google books]].
*{{Citation
 | first = Francesco
 | last= Faà di Bruno
 | title=Théorie générale de l'élimination
 | trans-title=General elimination theory
 | year=1859 
 | language= fr
 | publisher=Leiber et Faraguet 
 | place=Paris 
 | url=https://books.google.com/books?id=MZ0KAAAAYAAJ
 | pages= x+224
}}. Entirely freely available from [[Google books]].
* [[Harley Flanders|Flanders, Harley]] (2001) "From Ford to Faa", [[American Mathematical Monthly]]  108(6): 558–61 {{doi|10.2307/2695713}}
*{{Citation
  | last = Fraenkel
  | first = L. E.
  | title = Formulae for high derivatives of composite functions
  | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]]
  | volume = 83
  | issue = 2
  | pages =  159–165
  | year = 1978
  | doi = 10.1017/S0305004100054402
  | bibcode = 1978MPCPS..83..159F
 | mr = 0486377
  | zbl = 0388.46032
| s2cid = 121007038
 }}.
*{{Citation
  | last1 = Krantz
  | first1 = Steven G.
  | author1-link = Steven G. Krantz
  | last2 = Parks
  | first2 = Harold R.
  | author2-link = Harold R. Parks
  | title = A Primer of Real Analytic Functions
  | place = Boston
  | publisher = [[Birkhäuser Verlag]]
  | year = 2002
  | series = Birkhäuser Advanced Texts - Basler Lehrbücher
  | edition = Second
  | pages = xiv+205
  | url = https://books.google.com/books?id=i4vw2STJl2QC
  | mr = 1916029
  | zbl = 1015.26030
  | isbn = 978-0-8176-4264-8
}}
*{{Citation
  | last = Porteous
  | first = Ian R.
  | author-link = Ian Robertson Porteous
  | title = Geometric Differentiation
  | place = Cambridge
  | publisher = [[Cambridge University Press]]
  | year = 2001
  | edition = Second
  | chapter = Paragraph 4.3: Faà di Bruno's formula 
  | chapter-url = https://books.google.com/books?id=BNrW0UJ_UFcC&pg=PA83
  | pages = 83–85   <!-- | pages = xvi+333 -->
  | url = https://books.google.com/books?id=BNrW0UJ_UFcC
  | mr = 1871900
  | zbl = 1013.53001
  | isbn = 978-0-521-00264-6
}}.
*{{Citation
  | last = T. A. 
  | first = (Tiburce Abadie, J. F. C.)
  | title = Sur la différentiation des fonctions de fonctions
  | trans-title=On the derivation of functions
  | language = fr
  | journal = [[Nouvelles Annales de Mathématiques|Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale]]
  | series = Série 1
  | volume = 9
  | pages = 119–125 
  | year = 1850
  | url = http://www.numdam.org/item?id=NAM_1850_1_9__119_1
}}, available at [http://www.numdam.org NUMDAM]. This paper, according to {{harvtxt|Johnson|2002|p=228}} is one of the precursors of {{harvnb|Faà di Bruno|1855}}: note that the author signs only as "T.A.", and the attribution to J. F. C. Tiburce Abadie is due again to Johnson.
*{{Citation
  | last = A.
  | first = (Tiburce Abadie, J. F. C.)
  | title = Sur la différentiation des fonctions de fonctions. Séries de Burmann, de Lagrange, de Wronski
  | trans-title=On the derivation of functions. Burmann, Lagrange and Wronski series.
  | language = fr
  | journal = [[Nouvelles Annales de Mathématiques|Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale]]
  | series = Série 1
  | volume = 11
  | pages = 376–383  
  | year = 1852 
  | url = http://www.numdam.org/item?id=NAM_1852_1_11__376_1
}}, available at [http://www.numdam.org NUMDAM]. This paper, according to {{harvtxt|Johnson|2002|p=228}} is one of the precursors of {{harvnb|Faà di Bruno|1855}}: note that the author signs only as "A.", and the attribution to J. F. C. Tiburce Abadie is due again to Johnson.

==External links==
* {{MathWorld|urlname=FaadiBrunosFormula|title=Faa di Bruno's Formula}}
{{DEFAULTSORT:Faa de Bruno's formula}}
[[Category:Differentiation rules]]
[[Category:Differential calculus]]
[[Category:Differential algebra]]
[[Category:Enumerative combinatorics]]
[[Category:Factorial and binomial topics]]
[[Category:Theorems in analysis]]