# Faà di Bruno's formula

Faà di Bruno's formula

Faà di Bruno's formula is an identity in mathematics generalizing the chain rule to higher derivatives, named in honor of Francesco Faà di Bruno (1825&ndash;1888), who was (in chronological order) a military officer, a mathematician, and a priest, and was beatified by the Pope a century after his death. Perhaps the most well-known form of Faà di Bruno's formula says that

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

where the sum is over all "n"-tuples ("m"1, ..., "m""n") satisfying the constraint

:$1m_1+2m_2+3m_3+cdots+nm_n=n.,$

Sometimes, to give it a pleasing and memorable pattern, it is written in a way in which the coefficients that have the combinatorial interpretation discussed below are less explicit:

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

Combining the terms with the same value of $m_1+m_2+cdots+m_n=k$ leads to another somewhat simpler formula expressed in terms of Bell polynomials $B_\left\{n,k\right\}\left(x_1,dots,x_\left\{n-k+1\right\}\right)$:

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

Combinatorial form

The formula has a "combinatorial" form:

:$\left\{d^n over dx^n\right\} f\left(g\left(x\right)\right)=\left(fcirc g\right)^\left\{\left(n\right)\right\}\left(x\right)=sum_\left\{piinPi\right\} f^\left\{\left(left|pi ight|\right)\right\}\left(g\left(x\right)\right)cdotprod_\left\{Binpi\right\}g^\left\{\left(left|B ight|\right)\right\}\left(x\right)$

where

*π runs through the set Π of all partitions of the set { 1, ..., "n" },

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

Explication via an example

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

:

What is the pattern?

:

The factor $scriptstyle g"\left(x\right)g\text{'}\left(x\right)^2 ;$ corresponds to the partition 2 + 1 + 1 of the integer 4, in the obvious way. The factor $scriptstyle f"\text{'}\left(g\left(x\right)\right);$ 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"\left(x\right)^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"\left(g\left(x\right)\right) ,!$ corresponds to the fact that there are "two" summands (2 + 2) in that partition. The coefficient 3 corresponds to the fact that there are 3 ways of partitioning 4 objects into groups of 2 (4C2 ÷ 2). The same concept applies to the others.

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\left\{1+cdots+1\right\}_\left\{m_1\right\},+, underbrace\left\{2+cdots+2\right\}_\left\{m_2\right\} ,+, underbrace\left\{3+cdots+3\right\}_\left\{m_3\right\}+cdots$

of the integer "n" is equal to

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

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

A multivariable 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):

:$\left\{partial^n over partial x_1 cdots partial x_n\right\}f\left(y\right)= sum_\left\{piinPi\right\} f^\left\{\left(left|pi ight|\right)\right\}\left(y\right)cdotprod_\left\{Binpi\right\}\left\{partial^\left\{left|B ighty over prod_\left\{jin B\right\} partial x_j\right\}$

where (as above)

*π runs through the set Π of all partitions of the set { 1, ..., "n" },

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

See "Hardy, Michael, " [http://www.combinatorics.org/Volume_13/PDF/v13i1r1.pdf Combinatorics of Partial Derivatives] ", [http://www.combinatorics.org Electronic Journal of Combinatorics] , 13 (2006), #R1.

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:

:$\left\{partial^3 over partial x_1, partial x_2, partial x_3\right\}f\left(y\right)= f\text{'}\left(y\right)\left\{partial^3 y over partial x_1, partial x_2, partial x_3\right\}$

::::$\left\{\right\} + f"\left(y\right) left\left( \left\{partial y over partial x_1\right\}cdot\left\{partial^2 y over partial x_2, partial x_3\right\}+\left\{partial y over partial x_2\right\}cdot\left\{partial^2 y over partial x_1, partial x_3\right\}+ \left\{partial y over partial x_3\right\}cdot\left\{partial^2 y over partial x_1, partial x_2\right\} ight\right)$

:::::$\left\{\right\} + f"\text{'}\left(y\right) \left\{partial y over partial x_1\right\}cdot\left\{partial y over partial x_2\right\}cdot\left\{partial y over partial x_3\right\}.$

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

In the formal power series

:$f\left(x\right)=sum_n \left\{a_n over n!\right\}x^n,$

we have the "n"th derivative at 0:

:$f^\left\{\left(n\right)\right\}\left(0\right)=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\left(x\right)=sum_\left\{n=1\right\}^infty \left\{b_n over n!\right\} x^n$

and

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

and

:$g\left(f\left(x\right)\right)=h\left(x\right)=sum_\left\{n=1\right\}^infty\left\{c_n over n!\right\}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_\left\{pi=left\left\{,B_1,,dots,,B_k, ight a_\left\{left|B_1 ightcdots a_\left\{left|B_k ight b_k$

where π runs through the set of all partitions of the set { 1, ..., "n" } 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. See the "compositional formula" in Chapter 5 of " [http://www-math.mit.edu/~rstan/ec/ Enumerative Combinatorics, Volumes 1 and 2] ", Richard P. Stanley, Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1N.

We can also write

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

where the expressions

:$B_\left\{n,k\right\}\left(a_1,dots,a_\left\{n-k+1\right\}\right)$

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

* W.P. Johnson, "The Curious History of Faà di Bruno's Formula", "American Mathematical Monthly", Vol. 109, March 2002, 217-234, [http://www.maa.org/news/monthly217-234.pdf online]
* [http://mathworld.wolfram.com/FaadiBrunosFormula.html Faà di Bruno's Formula on Mathworld]

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Faà di Bruno — is the name of an Italian noble family based in the areas of Asti, Casale, and Alessandria, which provided the Counts (later Marquises) of Bruno. Prominent members included:* Giovanni Matteo Faà di Bruno was a musician of some importance from… …   Wikipedia

• Formule de Faà di Bruno — En mathématiques, et plus précisément en analyse, la formule de Faà di Bruno est une identité généralisant la règle de dérivation des fonctions composées au cas des dérivées d ordre supérieur. Elle a été le plus souvent attribué au mathématicien… …   Wikipédia en Français

• Francesco Faà di Bruno — (29 March, 1825–27 March, 1888) was an Italian mathematician and priest, born at Alessandria. He was of noble birth, [The twelfth child of Luigi Faà, marchese of Bruno, conte of Carentino, signore of Fontanile and patrizio of Alessandria, and of… …   Wikipedia

• Francesco Faà di Bruno — (* 29. März 1825 in Alessandria; † 27. März 1888 in Turin) war ein italienischer Offizier, Mathematiker, Ingenieur, Erfinder, Erzieher …   Deutsch Wikipedia

• 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… …   Wikipedia

• Bell polynomials — In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are a triangular array of polynomials given by the sum extending over all sequences j1, j2, j3, ..., jn−k+1 of non negative integers such that …   Wikipedia

• Chain rule — For other uses, see Chain rule (disambiguation). Topics in Calculus Fundamental theorem Limits of functions Continuity Mean value theorem Differential calculus  Derivative Change of variables Implicit differentiation …   Wikipedia

• Scientific phenomena named after people — This is a list of scientific phenomena and concepts named after people (eponymous phenomena). For other lists of eponyms, see eponym. NOTOC A* Abderhalden ninhydrin reaction Emil Abderhalden * Abney effect, Abney s law of additivity William de… …   Wikipedia

• Lagrange inversion theorem — In mathematical analysis, the Lagrange inversion theorem, also known as the Lagrange Bürmann formula, gives the Taylor series expansion of the inverse function of an analytic function. Theorem statementSuppose the dependence between the variables …   Wikipedia

• Фаа-ди-Бруно — Фаа ди Бруно, Франческо Франческо Фаа ди Бруно Франческо Фаа ди Бруно (итал. Francesco Faà di Bruno, 1825 1888) итальянский математик и священник …   Википедия