# Faà di Bruno's formula

Part of a series of articles about :
Calculus :
$\int _{a}^{b}f'(t)\,dt=f(b)-f(a)$ :
Fundamental theorem
Limits
Continuity
Rolle's theorem
Mean value theorem
Inverse function theorem :
Differential
Definitions
Derivative (generalizations)
Differential
infinitesimal
of a function
total
Concepts
Differentiation notation
Second derivative
Implicit differentiation
Logarithmic differentiation
Related rates
Taylor's theorem
Rules and identities
Sum
Product
Chain
Power
Quotient
L'Hôpital's rule
Inverse
General Leibniz
Faà di Bruno's formula
Reynolds :
Integral
Lists of integrals
Integral transform
Leibniz integral rule
Definitions
Antiderivative
Integral (improper)
Riemann integral
Lebesgue integration
Contour integration
Integral of inverse functions
Integration by
Parts
Discs
Cylindrical shells
Substitution (trigonometric, tangent half-angle, Euler)
Euler's formula
Partial fractions (Heaviside's method)
Changing order
Reduction formulae
Differentiating under the integral sign
Risch algorithm :
Series
Geometric (arithmetico-geometric)
Harmonic
Alternating
Power
Binomial
Taylor
Convergence tests
Summand limit (term test)
Ratio
Root
Integral
Direct comparison
Limit comparison
Alternating series
Cauchy condensation
Dirichlet
Abel :
Vector
Gradient
Divergence
Curl
Laplacian
Directional derivative
Identities
Theorems
Gradient
Green's
Stokes'
Divergence
generalized Stokes
Helmholtz decomposition :
Multivariable
Formalisms
Matrix
Tensor
Exterior
Geometric
Definitions
Partial derivative
Multiple integral
Line integral
Surface integral
Volume integral
Jacobian
Hessian :
Advanced
Calculus on Euclidean space
Generalized functions
Limit of distributions :
Specialized
Fractional
Malliavin
Stochastic
Variations :
Miscellanea
Precalculus
History
Glossary
List of topics
Integration Bee
Mathematical analysis
Nonstandard analysis :
vte :
Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives. It is named after Francesco Faà di Bruno (1855, 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, 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
${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 $(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:
    ${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 $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_{n,k}(x_{1},\ldots ,x_{n-k+1})$, $n\geq 1$:
    ${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).$

## 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
* $\pi$ runs through the set $\Pi$ of all partitions of the set $\{1,\ldots ,n\}$,
* "$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{aligned}(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{aligned}}$
The pattern is:
    ${\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}}$
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 {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{aligned}&{\frac {D^{1}(f\circg)}{1!}}&=\left(f^{(1)}\circg\right){\frac {\frac {g^{(1)}}{1!}}{1!}}\\[8pt]&{\frac {D^{2}(f\circ g)}{2!}}&=\left(f^{(1)}\circg\right){\frac {\frac {g^{(2)}}{2!}}{1!}}&+\left(f^{(2)}\circg\right){\frac {{\frac {g^{(1)}}{1!}}{\frac {g^{(1)}}{1!}}}{2!}}\\[8pt]&{\frac {D^{3}(f\circ g)}{3!}}&=\left(f^{(1)}\circg\right){\frac {\frac {g^{(3)}}{3!}}{1!}}&+\left(f^{(2)}\circg\right){\frac {\frac {g^{(1)}}{1!}}{1!}}{\frac {\frac {g^{(2)}}{2!}}{1!}}&+\left(f^{(3)}\circg\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)}\circg\right){\frac {\frac {g^{(4)}}{4!}}{1!}}&+\left(f^{(2)}\circg\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)}\circg\right){\frac {{\frac {g^{(1)}}{1!}}{\frac {g^{(1)}}{1!}}}{2!}}{\frac {\frac {g^{(2)}}{2!}}{1!}}&+\left(f^{(4)}\circg\right){\frac {{\frac {g^{(1)}}{1!}}{\frac {g^{(1)}}{1!}}{\frac {g^{(1)}}{1!}}{\frac {g^{(1)}}{1!}}}{4!}}\end{aligned}}$

## 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):
    ${\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)
* $\pi$ runs through the set $\Pi$ of all partitions of the set $\{1,\ldots ,n\}$,
* "$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 $\{1,2,3\}$, and in each case the order of the derivative of $f$ is the number of parts in the partition:
    ${\begin{aligned}{\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{aligned}}$
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},$
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_{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\leq k\leq 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},\ldots ,\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 $x^{n}$ 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)=e^{x}$, $g(x)=\sum _{n\geq 1}{\frac {1}{n!}}a_{n}x^{n}$ gives the exponential formula. The special case $f(x)=1/(1-x)$, $g(x)=\sum _{n\geq 1}(-a_{n})x^{n}$ gives an expression for the reciprocal of the formal power series $\sum _{n\geq 0}a_{n}x^{n}$ in the case $a_{0}=1$.
Stanley gives a version for exponential power series. In the formal power series
    $f(x)=\sum _{n}{\frac {a_{n}}{n!}}x^{n},$
we have the $n$th 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 }{\frac {b_{n}}{n!}}x^{n}$
and
    $f(x)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n!}}x^{n}$
and
    $g(f(x))=h(x)=\sum _{n=0}^{\infty }{\frac {c_{n}}{n!}}x^{n},$
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
    $c_{n}=\sum _{\pi =\left\{B_{1},\ldots ,B_{k}\right\}}a_{\left|B_{1}\right|}\cdots a_{\left|B_{k}\right|}b_{k}$
where $\pi$ runs through the set of all partitions of the set $\{1,\ldots ,n\}$ and $B_{1},\ldots ,B_{k}$ are the blocks of the partition $\pi$, and $|B_{j}|$ is the number of members of the $j$th block, for $j=1,\ldots ,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 }{\frac {\sum _{k=1}^{n}b_{k}B_{n,k}(a_{1},\ldots ,a_{n-k+1})}{n!}}x^{n},$
where $B_{n,k}(a_{1},\ldots ,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:
    ${d^{n} \over dx^{n}}e^{g(x)}=e^{g(x)}B_{n}\left(g'(x),g''(x),\dots ,g^{(n)}(x)\right),$
where $B_{n}(x)$ is the nth 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.