I'm trying to understand how the Faà di Bruno formula works.
Reading the example on the Wikipedia entry for computing $\frac{d^4}{dt^4}f(g(x))$, I understand that the computation involves summing over the partitions of $4$: $\{\{4\},\{3,1\},\{2,2\},\{2,1,1\},\{1,1,1,1\}\}$ and that that determines the combination of derivatives of $g$ that go in each term of the sum, but I'm having trouble understanding where the coefficients $\{1,6,3,4,1\}$ in the final sum $$(f\circ g)^{(4)}(x)= f''''(g(x))g'(x)^4+6f'''(g(x))g''(x)g'(x)^2+3f''(g(x))g''(x)^2+4f''(g(x))g'''(x)g'(x)+\; f'(g(x))g''''(x)$$ come from.
Consider the ways you can partition $n$ objects in blocks that have that exact distribution. So if $k_1\cdot 1+k_2\cdot 2\cdots +k_{n}\cdot n=n$ you have $$\frac{n!}{\prod _{i=1}^nk_i!\cdot (i!)^{k_i}},$$ this is because you esentially put the objects in a line, then permute the line and take out the blocks from left to right. Each block has no order, so you have to divide for the number of blocks and also, there is a symmetry on the number of blocks of the same length (Those are the $k_i$), you have to divide by that $k_i!$ to take out that symmetry.
For example, if $4=2+2$ then the number of ways to do this is $\frac{4!}{2!^2\cdot 2!}=\frac{24}{8}=3$ which corresponds to $f''(f(x))g''(x).$