Lagrange inversion theorem

Правка en15, от adamant, 2022-06-25 21:00:57

Hi everyone!

There is a concept that is sometimes mentioned here and there. The Lagrange inversion theorem.

Let $$$x = f(y)$$$. We want to solve this equation for $$$y$$$. In other words, we want to find a function $$$g$$$ such that $$$y = g(x)$$$.

The Lagrange inversion theorem gives an explicit formula for the coefficients of $$$g(x)$$$ as a formal power series over $$$\mathbb K$$$:

$$$ \large k[x^k] g(x) = [x^{-1}] f^{-k}(x) $$$

In a special case $$$y = x \phi(y)$$$, that is $$$f(y) = \frac{y}{\phi(y)}$$$, which is common in combinatorics, it can also be formulated as

$$$ \large k[x^k] g(x) = [x^{k-1}] \phi^k(x) $$$

Finally, to avoid division one may use (see the comment by Elegia) the following formula

$$$ \large [x^n]g^k = [x^{-(k+1)}] f'(x) f^{-(n+1)}(x) $$$

which may be formulated for $$$y = x \phi(y)$$$ as

$$$ \large [x^n] g^k = [x^{n-k}] (\phi - x \phi')\phi^{n-1}. $$$

Prerequisites

Familiarity with the following:

It is required to have knowledge in the following:

  • Polynomials, formal power series and generating functions;
  • Basic notion of analytic functions (e.g. Taylor series);
  • Basic concepts of graph theory (graphs, trees, etc);
  • Basic concepts of set theory (describing graphs, trees, etc as sets, tuples, etc).

I mention the concept of fields, but you're not required to know them to understand the article. If you're not familiar with the notion of fields, assume that we're working in real numbers, that is, $$$\mathbb K = \mathbb R$$$.

It is recommended (but not required) to be familiar with combinatorial species, as they provide lots of intuition to how the equations on generating functions below are constructed.

Motivational examples

In my practice, most obvious use cases of the inversion theorem are related to the enumeration of trees.

Ordered trees

An ordered tree is a rooted tree in which an ordering of children is specified for each vertex.


All ordered trees on $$$n \in \{1,2,3,4\}$$$ vertices.

The task is, given $$$k$$$, to find the number of ordered trees on $$$n$$$ vertices such that every vertex is either a leaf or has at least $$$k$$$ children.

Ordered tree can be described recursively in the following manner:

$$$ \text{Tree} = (\text{Root}, \text{Tree}_1, \text{Tree}_2, \dots, \text{Tree}_k). $$$

In other words, as a set-theoretic object, an ordered tree can be represented as a $$$(k+1)$$$-tuple, such that the first element is its root and the next $$$k$$$ elements are its subtrees, which are also objects of the ordered tree class.

We can enumerate ordered $$$n$$$-tuples of arbitrary objects from class $$$A$$$ as $$$A^n(x)$$$. And to enumerate them for every $$$n \geq k$$$, we would need to sum up the functions, obtaining the generating function for the ordered sets of ordered trees:

$$$ A^k(x)+A^{k+1}(x)+A^{k+2}(x)+\dots = \frac{A^k(x)}{1-A(x)}. $$$

Let $$$T(x)$$$ be the generating function of ordered trees. Then it might be represented as

$$$ T(x) = x \cdot \left(1+\frac{T^k}{1-T}\right). $$$

For $$$k = 1$$$, the solution is generated by

$$$ T(x) = \frac{1-\sqrt{1-4x}}{2}, $$$

and for $$$k=2$$$, the solution is generated by

$$$ T(x) = \frac{1}{2} \left[1 - \sqrt{\frac{1-3x}{1+x}}\right]. $$$

But as $$$k$$$ grows, the explicit formula for $$$T(x)$$$ gets more and more complicated (see the solution Wolfram found for $$$k=4$$$).

Alternate approach is to express $$$x=f(T)$$$. Then the Lagrange inversion theorem would still allow us to compute coefficients.

$$$k$$$-ary trees

Another task of interest is to enumerate the $$$k$$$-ary trees.


A ternary tree

A $$$k$$$-ary tree is a tree in which every vertex is either a leaf or has exactly $$$k$$$ ordered children.

The generating function for $$$k$$$-ary trees adheres to the identity $$$T(x) = x \cdot (1+T^k)$$$.

Labeled trees

Yet another task is to enumerate labeled rooted trees. While an ordered tree is represented as a pair of the root vertex and the list of subtrees, unordered tree may be represented as a pair of the root vertex and the set of subtrees. In other words, the generating function of the rooted trees adheres to the equation $$$T(x) = x \cdot e^{T(x)}$$$.

The later follows from the exponential formula which states that the generating function for the class of sets of $$$T$$$ is $$$e^{T(x)}$$$.

Note that this equation only works for labeled trees, and their exponential generating function:

$$$ T(x) = \sum\limits_{k=0}^\infty \frac{a_k}{k!}x^k, $$$

where $$$a_k$$$ is the number of labeled trees.


Inversion theorem

Let $$$x = f(y)$$$. We want to solve this equation for $$$y$$$. In other words, we want to find a function $$$g$$$ such that $$$y = g(x)$$$.

This means that $$$x = f(g(x))$$$ and $$$y = g(f(y))$$$, so what we really want to find here is the functional inverse of $$$f$$$.

As it stands with generating functions, we're more interested in finding some expression for $$$g(x)$$$ as a formal power series, rather than closed elementary form (which may not exist). In doing so, we may use the Lagrange inversion theorem.

Formulation

Let $$$f,g$$$ be formal power series, such that $$$f(g(x)) = x$$$ and $$$f(0) = g(0) = 0$$$, then

$$$ \large \boxed{k[x^k] g^n(x) = n[x^{-n}]f^{-k}(x)} $$$

where $$$[x^k] f(x)$$$ denotes the coefficient near $$$x^k$$$ in $$$f(x)$$$. In particular the $$$g(x)$$$ itself is found as

$$$ \large \boxed{k[x^k] g(x) = [x^{-1}] f^{-k}(x)} $$$

$$$x^{-n}$$$ in the formulas above expects negative power of $$$x$$$ and $$$f^{-k}$$$ expects the existence of the multiplicative inverse for arbitrary formal power series $$$f(x)$$$, which is problematic. To mitigate this, we expand the domain of functions we're working with to formal Laurent series.

Def. 1. The set of formal Laurent series $$$\mathbb K((x))$$$ over $$$\mathbb K$$$ is defined as

$$$ \mathbb K((x)) = \left\{\sum\limits_{k = -N}^\infty a_k x^k \bigg| N \in \mathbb Z, a_k \in \mathbb K\right\}. $$$

In other words, formal Laurent series is a formal power series, which is also allowed to have finitely many terms $$$x^k$$$ with $$$k < 0$$$.

When $$$\mathbb K$$$ is a field, $$$\mathbb K((x))$$$ also form up a field. In particular, it means that for a formal Laurent series $$$A(x) \neq 0$$$ there always is a multiplicative inverse $$$A^{-1}(x)$$$ such that $$$A(x) A^{-1}(x) = 1$$$.

Explanation

Now that the formula is properly formulated, you may find the detailed proof below:

Proof

Note. Using the same reasoning, we can deduce it in even more general form for any analytic function $$$h(x)$$$:

$$$ \large \boxed{k[x^k] h(g(x)) = [x^{-1}] \frac{h'(x)}{f^k(x)}} $$$

In combinatorics

Quite often the equation that you deal with in combinatorics is formulated as $$$y = x \phi(y)$$$.

It is possible to get a simpler expression for such cases.

Equivalently, $$$y = x \phi(y)$$$ rewrites as

$$$ x = f(y) = \frac{y}{\phi(y)}. $$$

Since

$$$ [x^{-1}] f(x) = [x^{k-1}]\phi^k(x), $$$

we have a formula for $$$y = g(x)$$$:

$$$ \large \boxed{k[x^k] g(x) = [x^{k-1}] \phi^k(x)} $$$

It is especially convenient due to the fact that we don't need to actually deal with Laurent series.

More general result for this case is known as the Lagrange–Bürmann formula:

$$$ \large \boxed{k [x^k]h(g(x)) = [x^{k-1}] h'(x) \phi^k(x)} $$$

for any analytic function $$$h(x)$$$.

Cracking up the examples

Ordered trees

The equation is

$$$ T = x \cdot \left(1+\frac{T^k}{1-T}\right). $$$

It means that $$$n [x^n] T(x) = [T^{n-1}] \phi^n(T)$$$, where $$$\phi(T) = 1+\frac{T^k}{1-T}$$$. To compute it, we use the binomial formula:

$$$ [T^{n-1}]\left(1+\frac{T^k}{1-T}\right)^n = \sum\limits_{i=0}^n \binom{n}{i} [T^{n-1}]\frac{T^{ki}}{(1-T)^i}. $$$

Note that $$$[T^a]T^b f(T) = [T^{a-b}] f(T)$$$. And, knowing the expansion

$$$ \frac{1}{(1-x)^i} = \frac{1}{(i-1)!}\frac{\partial^{i-1}}{\partial x^{i-1}} (1-x)^{-1} = \sum\limits_{k=0}^\infty \frac{(k+1) \dots (k+i-1)}{(i-1)!} x^k = \sum\limits_{k=0}^\infty \binom{k+i- 1}{i - 1} x^k, $$$

we may rewrite it as

$$$ [x^n]T = \frac{1}{n}[T^{n-1}]\phi^n(T) = \frac{1}{n}\sum\limits_{i=0}^n \binom{n}{i} [T^{n-ki-1}] \frac{1}{(1-T)^i} = \frac{1}{n}\sum\limits_{i=0}^n \binom{n}{i} \binom{n-(k-1)i-2}{i - 1}. $$$

Indeed, computing first few terms for different $$$k$$$ we see that

Further $$$k$$$ are seemingly not present on OEIS.

$$$k$$$-ary trees

The equation is $$$T = x \cdot (1 + T^k)$$$. So, for this case $$$\phi(T) = 1+T^k$$$ and we need to find

$$$ [T^{n-1}]\phi^n(T) = [T^{n-1}](1+T^k)^n = [T^{n-1}] \sum\limits_{i=0}^n \binom{n}{i} T^{ki} $$$

The expression on the right only has coefficient near $$$T^{n-1}$$$ when $$$k$$$ divides $$$n-1$$$, in which cases the number of trees is

$$$ [x^{kt+1}] T(x) = \frac{1}{kt+1} \binom{kt+1}{t} $$$

for $$$n=kt+1$$$. Let's look on the generated sequences for different $$$k$$$:

  • $$$k=1$$$ yields $$$\frac{1}{t+1} \binom{t+1}{t}=1$$$. Indeed, there is only one $$$1$$$-ary tree (bamboo) for each possible number of vertices;
  • $$$k=2$$$ yields $$$\frac{1}{2t+1} \binom{2t+1}{t}$$$. This is actually the $$$t$$$-th Catalan number and another neat formula for them!
  • $$$k=3$$$ yields the number of ternary trees (A001764);
  • $$$k=4$$$ yields the number of quartic trees (A002293).

Labeled trees

The equation is $$$T = x e^T$$$. Let's find the coefficients with $$$\phi(T) = e^T$$$:

$$$ [T^{n-1}] \phi^n(T) = [T^{n-1}] e^{nT} = [T^{n-1}] \sum\limits_{k=0}^\infty \frac{n^k T^k}{k!}. $$$

From this follows that

$$$ [x^n]T(x) = \frac{1}{n} \frac{n^{n-1}}{(n-1)!} = \frac{n^{n-1}}{n!}. $$$

Note that we were specifically considering the exponential generating functions, thus the actual number of trees is $$$n! [x^n] T(x) = n^{n-1}$$$.

The function $$$T(x)$$$ can be expressed as $$$T(x) = -W(-x)$$$, where $$$W(x)$$$ is the Lambert W function (see e.g. here).

Теги tutorial, generating function, lagrange inversion

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en20 Английский adamant 2022-08-15 03:50:25 26
en19 Английский adamant 2022-06-25 21:06:56 13
en18 Английский adamant 2022-06-25 21:06:05 12
en17 Английский adamant 2022-06-25 21:04:50 2
en16 Английский adamant 2022-06-25 21:03:44 22
en15 Английский adamant 2022-06-25 21:00:57 350
en14 Английский adamant 2022-06-24 15:07:22 5
en13 Английский adamant 2022-06-24 15:06:35 1
en12 Английский adamant 2022-06-24 14:53:00 165
en11 Английский adamant 2022-06-24 14:48:34 142
en10 Английский adamant 2022-06-24 14:34:27 55
en9 Английский adamant 2022-06-24 13:47:03 36
en8 Английский adamant 2022-06-24 13:45:15 35
en7 Английский adamant 2022-06-24 13:34:59 172
en6 Английский adamant 2022-06-24 00:55:21 4
en5 Английский adamant 2022-06-24 00:54:35 37
en4 Английский adamant 2022-06-24 00:52:05 164
en3 Английский adamant 2022-06-24 00:44:01 9
en2 Английский adamant 2022-06-24 00:41:59 85
en1 Английский adamant 2022-06-24 00:31:49 11535 Initial revision (published)