3
$\begingroup$

I am trying to get the pattern of the Faa di Bruno's formula of the chain rule for higher derivatives. The only thing which I don't understand is how to get the coefficients of the various terms.

For example, let $y=g(x)$. Now $(f\circ g)''''(x)=f''''(y)y'^4+6f'''(y)y''y'^2+3f''(y)y''^2+4f''(y)y'''y'+f'(y)g''''$.

Here we note that that each term corresponds with a partition of $4$. The first term has four $y'$ terms in it and so it corresponds with $1+1+1+1$ (this sum has four terms and hence fourth derivative of $f(y)$ is there). The second term has a $y''$ and two $y'$ terms in it and so corresponds with $2+1+1$ (this sum has 3 terms and hence third derivative of $f(y)$ is there) and so on. But how can the pattern of the coefficients be expressed now?

Thanks

  • 0
    One may wonder why you did not google this! :-D The two answers so far are a link to mathworld and to the Wikipedia page on the subject, both of which Google is quite good at finding.2013-03-24

2 Answers 2

2

One way to make things clearer is to try "labeling" the derivative tickmarks on $g$ as you bring them in, and not combining any terms.

Ie, instead of writing $g'$, we might write $g^A$ or $g^B$ or $g^C$, which would all mean the same thing, ($g^A = g^B = g^C = g'$). Second derivatives $g''$ might, for example, be written $g^{AB}$ or $g^{AC}$ or whatever, depending on the process in which the derivatives were build up.

For the first derivative we "bring in" derivatives of $g$ labeled by $A$, \begin{align} \frac{d}{dt}f(g) &= f'(g)g^A, \\ &\sim (A). \end{align} For the second derivative we "bring in" derivatives labeled by $B$, \begin{align} \frac{d^2}{dt^2} f(g) &= f''(g)g^Ag^B + f'(g)g^{AB} \\ &\sim (A)(B) + (AB). \end{align} For the third derivative we use label $C$, \begin{align} \frac{d^3}{dt^3} f(g) &= f'''(g)g^Ag^Bg^C + f''(g)g^{AC}g^B + f''(g)g^Ag^{BC} + f''(g)g^{AB}g^C + f'(g)g^{ABC} \\ &\sim (A)(B)(C) + (AC)(B) + (A)(BC) + (AB)(C) + (ABC). \end{align}

It looks like each term in the $k$'th derivative corresponds to a distinct partition of a $k$ element set. To see why this is, let's suppose we have been computing these derivatives for a while, and we start to differentiate a term like the following, $f^{(6)}(g)g^{AC}g^{BDF}g^{E}.$

When we bring in the next derivative ($G$), it could be by itself from the chain rule with differentiating $f$, or it could go into any of the already existing groups, \begin{align} \frac{d}{dt} f^{(6)}(g)g^{AC}g^{BDF}g^{E} &= f^{(7)}(g)g^{AC}g^{BDF}g^{E}g^{G} \quad\quad\text{bring }G\text{ in by itself} \\ &+ f^{(6)}(g)g^{ACG}g^{BDF}g^{E} \quad\quad\text{bring }G\text{ into the first group}\\ &+ f^{(6)}(g)g^{AC}g^{BDFG}g^{E} \quad\quad\text{bring }G\text{ into the second group}\\ &+ f^{(6)}(g)g^{ACG}g^{BDF}g^{EG} \quad\quad\text{bring }G\text{ into the third group} \end{align}

What we are doing is taking a partition $(AC)(BDF)(E)$ of the set $\{A,B,C,D,E,F\}$, and generating all possible extensions of the partition to the set with a new element, $\{A,B,C,D,E,F,G\}$.

Now that's for 1 term, but we have to do this partition extension for all terms. If the terms in the $6$'th derivative are in 1-1 correspondence with the set of all partitions of a $6$ element set, and for each partition we generate all possible extensions, then what we end out with is the set of all partitions on a $7$ element set.

So, through an inductive argument of this form we can see that the terms in the $k$'th derivative are in one-to-one correspondence with the partitions of a $k$ element set. $\frac{d^n}{dt^n}f(g) = \sum_{\substack{\text{all partitions }p \\ \text{ of an }n\text{ element set}}} f^{(\text{# of parts in }p)}(g)g^{\text{part }1\text{ in }p}g^{\text{part }2\text{ in }p} \dots g^{\text{part }n\text{ in }p}$ However, due to the extraneous labeling, many of these terms are the same. Since the elements are $A,B,C,\dots$ indistinguishable, we can reduce the sum to, $\sum_{\substack{\text{all partitions }m \\ \text{ of an }n\text{ element set with} \\ \text{indistinguishable elements}}} \left(\substack{\text{# of partitions} \\ \text{of a distinguishable set}\\ \text{that have the form of } m} \right)f^{(\text{# of parts in }m)}(g)g^{\text{part }1\text{ in }m}g^{\text{part }2\text{ in }m} \dots g^{\text{part }n\text{ in }m},$ So the problem boils down to finding the number of partitions of a distinguishable set that correspond to a particular partition $m$ of an indistinguishable set, and this aspect of the question has been answered already by NikolajK.

1

The wikipedia page on the formua explains it: You get the coefficients as the number of way you can put $n+m+\dots k$ things in boxes of $n,m,\dots,k$.

Call the things $A,B,C,D$...

$\bullet\ \ 1+1+1+1:\ (A,B,C,D)\ \Longrightarrow \ 1$

$\bullet\ \ 2+1+1: \ (\{A,B\},C,D),(\{A,C\},B,D)(\{A,D\},B,D)(\{B,C\},A,D)(\{A,B\},C,D)(\{A,B\},C,D)\ \Longrightarrow \ 6$

$\bullet\ \ 2+2:\ (\{A,B\},\{C,D\}),(\{A,C\},\{B,D\}),(\{A,D\},\{B,C\})\ \Longrightarrow \ 3$

$\bullet\ \ 3+1:\ (\{A,B,C\},D),(\{A,B,D\},C),(\{A,C,D\},B),(\{B,C,D\},A)\ \Longrightarrow \ 4$

$\bullet\ \ 4:\ (\{A,B,C,C\},D)\ \Longrightarrow \ 1.$

A closed way to express them is via the Bell polynomials.