Theorem: Faà di Bruno's Formula

Let $D_x^k u$ denote the $k$th derivative of a function $u$ {{WRT|Differentiation}} $x$.
Then:
:$\ds 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 {\paren {D_x^m u}^{k_m} } {k_m! \paren {m!}^{k_m} }$

Proof:
For convenience, let:
:$w_j := D_u^j w$
:$u_k := D_x^k u$
Then:
{{begin-eqn}}
{{eqn | l = \map {D_x} {w_j}
      | r = w_{j + 1} u_1
      | c = Derivative of Composite Function
}}
{{eqn | l = \map {D_x} {u_k}
      | r = u_{k + 1}
      | c = {{Defof|Higher Derivative}}
}}
{{end-eqn}}
Thus:
{{begin-eqn}}
{{eqn | l = D_x^1 w
      | r = w_1 u_1
      | c = Derivative of Composite Function
}}
{{eqn | l = D_x^2 w
      | r = \paren {w_2 u_1 u_1 + w_1 u_2}
      | c = Derivative of Composite Function: Second Derivative
}}
{{eqn | l = D_x^3 w
      | r = \paren {\paren {w_3 u_1 u_1 u_1 + w_2 u_2 u_1 + w_2 u_1 u_2} + \paren {w_2 u_1 u_2 + w_1 u_3} }
      | c = Derivative of Composite Function: Third Derivative or directly
}}
{{end-eqn}}
Analogously, let a corresponding tableau be set up of set partitions as follows:
{{begin-eqn}}
{{eqn | l = \DD^1
      | r = \set 1
      | c = 
}}
{{eqn | l = \DD^2
      | r = \set {\set 2 \mid \set 1} + \set {2, 1}
      | c = 
}}
{{eqn | l = \DD^3
      | r = \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}
      | c = 
}}
{{end-eqn}}
Thus inspired, let $a_1 a_2 \cdots a_j$ denote a partition of the set $\set {1, 2, \ldots, n-1}$.
Let:
{{begin-eqn}}
{{eqn | l = \DD a_1 a_2 \cdots a_j
      | o = :=
      | r = \set n a_1 a_2 \cdots a_j
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = \paren {a_1 \cup \set n} a_2 \cdots a_j 
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = a_1 \paren {a_2 \cup \set n} \cdots a_j 
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = \cdots
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = a_1 a_2 \cdots \paren {a_j \cup \set n}
      | c = 
}}
{{end-eqn}}
This rule is isomorphic to:
{{begin-eqn}}
{{eqn | l = \map {D_x} {w_j u_{r_1} u_{r_2} \ldots u_{r_j} }
      | r = w_{j + 1} u_1 u_{r_1} u_{r_2} \ldots u_{r_j}
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = w_j u_{r_1 + 1} u_{r_2} \ldots u_{r_j}
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = w_j u_{r_1} u_{r_2 + 1} \ldots u_{r_j}
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = \cdots
      | c = 
}}
{{eqn | ro= +
      | o = 
      | r = w_j u_{r_1} u_{r_2} \ldots u_{r_j + 1}
      | c = 
}}
{{end-eqn}}
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 $\DD^n$ to $D_x^n w$.
{{explain|Link this to Number of Set Partitions by Number of Components}}
Thus, collecting like terms in $D_x^n w$, we obtain a sum of terms:
:$\map c {k_1, k_2, \ldots} 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:
:$\map c {k_1, k_2, \ldots}$ 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!} {\paren {1!}^{k_1} \paren {2!}^{k_2} \paren {3!}^{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:
:$\map c {k_1, k_2, \ldots} = \dfrac {n!} {k_1! \paren {1!}^{k_1} \, k_2! \paren {2!}^{k_2} k_3! \paren {3!}^{k_3} \cdots}$
and the result follows.
{{qed}}