Composita of Generating Functions

1. Definition of the Composita

The composita of a generating function \(F(x) = \sum_{n>0} f(n) x^n\) (with \(f(0) = 0\)) is the function of two variables \[ F^{\Delta}(n, k) = \sum_{\pi_k \in C_n} f(\lambda_1) f(\lambda_2) \cdots f(\lambda_k), \] where \(C_n\) is the set of all compositions of the integer \(n\), and \(\pi_k = (\lambda_1, \ldots, \lambda_k)\) is a composition of \(n\) into \(k\) parts with \(\sum_{i=1}^k \lambda_i = n\).

Definition (Kruchinin & Kruchinin, 2013). The composita \(F^{\Delta}(n,k)\) is the coefficient of \(x^n\) in \([F(x)]^k\): \[ [F(x)]^k = \sum_{n \ge k} F^{\Delta}(n,k) \, x^n. \] Equivalently, \(F^{\Delta}(n,k) = [x^n] F(x)^k\).

The composita generalizes the binomial coefficients. For example, the composita of \(F(x) = \frac{x}{1-x} = x + x^2 + x^3 + \cdots\) is precisely the Pascal triangle: \[ F^{\Delta}(n,k) = \binom{n-1}{k-1}. \]

Example (Pascal's triangle from composita). Since \(f(n) = 1\) for all \(n > 0\), the composita counts the number of compositions of \(n\) into \(k\) parts, which is \(\binom{n-1}{k-1}\): \[ \begin{array}{cccccc} & & & 1 \\ & & 1 & & 1 \\ & 1 & & 2 & & 1 \\ 1 & & 3 & & 3 & & 1 \\ 1 & & 4 & & 6 & & 4 & & 1 \end{array} \]

2. Recurrence Formula

Theorem (Recurrence for the Composita). For a generating function \(F(x) = \sum_{n>0} f(n) x^n\), the composita satisfies \[ F^{\Delta}(n,k) = \begin{cases} f(n), & \text{if } k = 1, \\[4pt] \displaystyle\sum_{i=1}^{n-k+1} f(i) \, F^{\Delta}(n-i, k-1), & \text{if } k \le n. \end{cases} \]

Proof sketch

For \(k=1\), the only composition is \(\pi_1 = (n)\), so \(F^{\Delta}(n,1) = f(n)\). For \(k>1\), group all compositions by their first part \(\lambda_1 = i\). The sum over the remaining \(k-1\) parts is \(F^{\Delta}(n-i, k-1)\). Summing over \(i = 1, \ldots, n-k+1\) (since at least \(k-1\) parts of size 1 remain) gives the recurrence.

Special values:

\(F^{\Delta}(n,n) = f(1)^n\) (all parts are 1)
\(F^{\Delta}(n,1) = f(n)\) (single part of size \(n\))
\(F^{\Delta}(n,k) = 0\) if \(k > n\) or \(k < 1\)

3. Composita Calculator

Enter the coefficients \(f(n)\) of your generating function \(F(x) = \sum_{n>0} f(n) x^n\). The composita triangle \(F^{\Delta}(n,k)\) will be computed below.

\(f(1)\)

\(f(2)\)

\(f(3)\)

\(f(4)\)

\(f(5)\)

Max \(n\)

Presets: \(x/(1-x)\) • \(x+x^2\) • \(x+x^2+x^3\) • \(e^x-1\)

4. Composition of Generating Functions

Theorem (Composition via Composita). Let \(F(x) = \sum_{n>0} f(n) x^n\) and \(R(x) = \sum_{n \ge 0} r(n) x^n\). Then the composition \(A(x) = R(F(x))\) has coefficients \[ a(n) = \begin{cases} r(0), & n = 0, \\ \displaystyle\sum_{k=1}^{n} F^{\Delta}(n,k) \, r(k), & n > 0. \end{cases} \]

This theorem is the workhorse for solving iterative functional equations. For \(A(A(x)) = F(x)\), we need the composita of the composition formula: \[ A^{\Delta}(n,k) = \sum_{m=k}^{n} F^{\Delta}(n,m) \, G^{\Delta}(m,k) \] when \(A(x) = G(F(x))\). Setting \(G = A\) and using \(A(A(x)) = F(x)\) gives a triangular system for the unknown coefficients \(a(n)\).

Example: Catalan numbers. The Catalan generating function \(C(x) = \frac{1-\sqrt{1-4x}}{2x}\) satisfies \(C(x) = 1 + x C(x)^2\). Using the composita approach, one finds \(C_x^{\Delta}(n,k) = \frac{k}{n} \binom{2n-k-1}{n-1}\), yielding the Catalan numbers \(C_n = \frac{1}{n+1}\binom{2n}{n}\).