# Faà di Bruno's Formula/Proof 2

## Theorem

Let $D_x^k u$ denote the $k$th derivative of a function $u$ with respect to $x$.

Then:

$\displaystyle D_x^n w = \sum_{j \mathop = 0}^n D_u^j w \sum_{\substack {\sum_{p \mathop \ge 1} k_p \mathop = j \\ \sum_{p \mathop \ge 1} p k_p \mathop = n \\ \forall p \mathop \ge 1: k_p \mathop \ge 0} } n! \prod_{m \mathop = 1}^n \dfrac {\left({D_x^m u}\right)^{k_m} } {k_m! \left({m!}\right)^{k_m} }$

## Proof

For convenience, let:

$w_j := D_u^j w$
$u_k := D_x^k u$

Then:

 $\ds D_x \left({w_j}\right)$ $=$ $\ds w_{j + 1} u_1$ Derivative of Composite Function $\ds D_x \left({u_k}\right)$ $=$ $\ds u_{k + 1}$ Definition of Higher Derivative

Thus:

 $\ds D_x^1 w$ $=$ $\ds w_1 u_1$ Derivative of Composite Function $\ds D_x^2 w$ $=$ $\ds \left({w_2 u_1 u_1 + w_1 u_2}\right)$ Derivative of Composite Function: Second Derivative $\ds D_x^3 w$ $=$ $\ds \left({\left({w_3 u_1 u_1 u_1 + w_2 u_2 u_1 + w_2 u_1 u_2}\right) + \left({w_2 u_1 u_2 + w_1 u_3}\right)}\right)$ Derivative of Composite Function: Third Derivative or directly

Analogously, let a corresponding tableau be set up of set partitions as follows:

 $\ds \mathcal D^1$ $=$ $\ds \set 1$ $\ds \mathcal D^2$ $=$ $\ds \set {\set 2 \mid \set 1} + \set {2, 1}$ $\ds \mathcal D^3$ $=$ $\ds \set {\set 3 \mid \set 2 \mid \set 1} + \set {\set {3, 2} \mid \set 1} + \set {\set 2 \mid \set {3, 1} } + \set {\set 3 \mid \set {2, 1} } + \set {3, 2, 1}$

Thus inspired, let $a_1 a_2 \cdots a_j$ denote a partition of the set $\set {1, 2, \ldots, n-1}$.

Let:

 $\ds \mathcal D a_1 a_2 \cdots a_j$ $:=$ $\ds \set n a_1 a_2 \cdots a_j$ $\ds$  $\, \ds + \,$ $\ds \left({a_1 \cup \set n}\right) a_2 \cdots a_j$ $\ds$  $\, \ds + \,$ $\ds a_1 \left({a_2 \cup \set n}\right) \cdots a_j$ $\ds$  $\, \ds + \,$ $\ds \cdots$ $\ds$  $\, \ds + \,$ $\ds a_1 a_2 \cdots \left({a_j \cup \set n}\right)$

This rule is isomorphic to:

 $\ds D_x \left({w_j u_{r_1} u_{r_2} \ldots u_{r_j} }\right)$ $=$ $\ds w_{j + 1} u_1 u_{r_1} u_{r_2} \ldots u_{r_j}$ $\ds$  $\, \ds + \,$ $\ds w_j u_1 u_{r_1 + 1} u_{r_2} \ldots u_{r_j}$ $\ds$  $\, \ds + \,$ $\ds w_j u_1 u_{r_1} u_{r_2 + 1} \ldots u_{r_j}$ $\ds$  $\, \ds + \,$ $\ds \cdots$ $\ds$  $\, \ds + \,$ $\ds w_j u_1 u_{r_1} u_{r_2} \ldots u_{r_j + 1}$

where the term $w_j u_{r_1} u_{r_2} \ldots u_{r_j}$ corresponds to a partition $a_1 a_2 \cdots a_j$.

Thus there exists a bijection from $\mathcal D^n$ to $D_x^n w$.

Thus, collecting like terms in $D_x^n w$, we obtain a sum of terms:

$c \left({k_1, k_2, \ldots}\right) w_j u_i^{k_1} u_2^{k_2} \ldots$

where:

$j = k_1 + k_2 + \cdots$

and:

$n = k_1 + 2 k_2 + \cdots$

and where:

$c \left({k_1, k_2, \ldots}\right)$ is the number of partitions of $\set {1, 2, \ldots, n}$ into $j$ subsets where there are $k_t$ subsets with $t$ elements.

Consider an array of $k_t$ boxes of capacity $t$.

The number of ways to put $n$ different elements into these boxes is the multinomial coefficient:

$\dbinom n {1, 1, \ldots, 1, 2, 2, \ldots, 2, 3, 3, \ldots, 3, 4, \ldots} = \dfrac {n!} {\left({1!}\right)^{k_1} \left({2!}\right)^{k_2} \left({3!}\right)^{k_3} \cdots}$

It remains to divide by $k_1! \, k_2! \, k_3! \ldots$ corresponding to the number of ways each group of $k_t$ can be permuted

Hence:

$c \left({k_1, k_2, \ldots}\right) = \dfrac {n!} {k_1! \left({1!}\right)^{k_1} \, k_2! \left({2!}\right)^{k_2} k_3! \left({3!}\right)^{k_3} \cdots}$

and the result follows.

$\blacksquare$

## Source of Name

This entry was named for Francesco Faà di Bruno.