# A Faà di Bruno’s formula with tensors

Recently, working on k-order perturbation in dynare, I had to compute high-order derivatives of composite vector-valued functions. In their 2004 mimeo « Solving Stochastic Dynamic Equilibrium Models: A k-Order Perturbation Approach », Michel Juillard and Ondra Kamenik mention a Faà di Bruno’s formula with tensors using the Einstein summation convention. There is neither a demonstration nor a source pointing to it despite the usefulness of such a formula. I have unsuccessfuly looked for an equivalent expression in the mathematical literature. Let’s take a peek at it.

I adopt the elegant terminology of Tsoy-Wo Ma in its 2009’s article « Higher Chain Formula Proved by Combinatorics. » published in The Electronic Journal of Combinatorics.

Consider a function $$h : x \in X \subset \mathbb{R}^{\nu} \overset{f}{\rightarrow} y \in Y \subset \mathbb{R}^{\mu} \overset{g}{\rightarrow} z \in \mathbb{R}$$ where $$X$$ and $$Y$$ are open sets.

I denote $$\mathbb{P}_n$$ the set of partitions of $$\{1,…,n\}$$ and $$P_\mu$$ the set of functions from a partition of $$\{1,…,n\}$$ into $$\{1,…,\mu\}$$.

Tsoy-Wo Ma demonstrates the following Lemma:

$$\frac{\partial^n z}{\partial t_1 … \partial t_n} = \sum_{P \in \mathbb{P}_n} \sum_{\lambda \in P_\mu} \left\{ \left(\prod_{B \in P} \frac{\partial}{\partial y_{\lambda(B)}} \right) z \right\} \left\{ \prod_{B \in P} \left[ \left( \prod_{b \in B} \frac{\partial}{\partial t_b}\right) y_{\lambda(B)} \right] \right\}$$

where $$t_i$$ denotes one of the variables $$x_1, …, x_{\nu}$$.

I denote $$\mathbb{P}_n^k$$ the partitions of $$\{1, …, n \}$$ with $$k$$ classes $$k \in \{ 1,…,n\}$$, which is a partition of $$\mathbb{P}_n$$. Thus, the formula above becomes

$$\frac{\partial^n z}{\partial t_1 … \partial t_n} = \sum_{k=1}^n \sum_{P \in \mathbb{P}_n^k} \sum_{\lambda \in P_\mu} \left\{ \left(\prod_{j = 1}^{k} \frac{\partial}{\partial y_{\lambda(P_j)}} \right) z \right\} \left\{ \prod_{j = 1}^{k} \left[ \left( \prod_{b \in P_j} \frac{\partial}{\partial t_b}\right) y_{\lambda(P_j)} \right] \right\}$$

where $$P_j$$ is the $$j$$-th block of partition $$P$$, $$j \in \{1,…,k\}$$.

Introducing the Einstein notation yields

$$\left[ h_{x^n} \right]_{t_1 … t_n} = \sum_{k=1}^n \sum_{P \in \mathbb{P}_n^k} \sum_{\lambda \in P_\mu} \left[ g_{y^k} \right]_{ \lambda (P_1) … \lambda (P_k) } \prod_{j = 1}^{k} \left[ f_{x^{\mid P_j \mid}}^{\lambda (P_j)} \right]_{t \left( P_j \right)}$$

where $$\mid P_j \mid$$ is the cardinal of the block $$P_j$$ and $$t \left( P_j \right)$$ is the collection of $$t$$ indexes the $$P_j$$ block contains.

Given $$P \in \mathbb{P}_n^k$$, note that summing over all $$\lambda \in P_\mu$$ is the same as summing over all tuples $$\left( \beta_1, …, \beta_k \right) \in \left\{1, …, \mu \right\}^k$$. Using the conventions of the Einstein notation, the following simplification arises

\begin{aligned}\sum_{\lambda \in P_\mu} \left[ g_{y^k} \right]_{ \lambda (P_1) … \lambda (P_k) } \prod_{j = 1}^{k} \left[ f_{x^{\mid P_j \mid}}^{\lambda (P_j)} \right]_{t \left( P_j \right)} &= \sum_{\beta_1, …, \beta_k} \left[ g_{y^k} \right]_{ \beta_1 … \beta_k } \prod_{j = 1}^{k} \left[ f_{x^{\mid P_j \mid}}^{\beta_j} \right]_{t \left( P_j \right)}\\ &= \left[ g_{y^k} \right]_{ \beta_1 … \beta_k } \left[ f_{x^{\mid P_1 \mid}} \right]_{t \left( P_1 \right)}^{\beta_1} … \left[ f_{x^{\mid P_k \mid}} \right]_{t \left( P_k \right)}^{\beta_k}\end{aligned}

As a result, the Faà di Bruno’s formula in tensor notation with the Einstein summation convention appears.
$$\left[ h_{x^n} \right]_{t_1 … t_n} = \sum_{k=1}^n \sum_{P \in \mathbb{P}_n^k} \left[ g_{y^k} \right]_{ \beta_1 … \beta_k } \left[ f_{x^{\mid P_1 \mid}} \right]_{t \left( P_1 \right)}^{\beta_1} … \left[ f_{x^{\mid P_k \mid}} \right]_{t \left( P_k \right)}^{\beta_k}$$ 