Faa di Bruno coefficients 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
 A: 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.
A: 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.
