adamant's blog

By adamant, history, 21 month(s) ago, In English

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} $$$

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 $$$

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

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

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

$$$ \large [x^k] g(x) = [x^{k-1}] (\phi - x \phi')\phi^{k-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).

  • Vote: I like it
  • +101
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Ok this has always bothered me. Why is the formal Laurent series defined as having only a finite number of negative terms while a Laurent series in complex analysis can have infinite negative terms?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    The idea behind formal power/Laurent series, compared to regular series, is to not care at all about convergence issues.

    We generally define the multiplication in formal Laurent series as

    $$$ \left(\sum\limits_{i=-n}^\infty a_i x^i\right) \left(\sum\limits_{j=-m}^\infty b_j x^{j}\right) = \sum\limits_{i=-n}^\infty \sum\limits_{j=-m}^\infty a_i b_j x^{i+j} = \sum\limits_{k=-(n+m)}^\infty x^k \sum\limits_{i+j=k} a_i b_j. $$$

    If we don't make the number of negative terms finite, we potentially have infinite sums near $$$x^k$$$ and bad things happen.

    To work with such sums, we'd need to introduce a notion of convergence and it kind of defeats the whole purpose.

»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

Actually there is a variant form:

$$$ [x^n](F^{\langle -1 \rangle})^k = [x^{-k-1}] F'F^{-n-1}. $$$

Remarks:

  • When $$$n=0$$$ and $$$k<0$$$, we still can use this formula but the usual one does not work.
  • It avoids division.
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Looks nice! Is there a simple proof to it? Is it also proven with residues?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    So, for $$$y = x \phi(y)$$$, we have $$$F' F^{-n-1}=\frac{\phi - x \phi'}{\phi^2} \frac{\phi^{n+1}}{x^{n+1}}$$$ and the formula for $$$y=g(x)$$$ would look like

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

    Neat! Let's test it for Catalan numbers with $$$\phi(x) = 1+x^2$$$:

    $$$ [x^{n-1}] (1-x^2) \sum\limits_{i=0}^{n-1} \binom{n-1}{i} x^{2i} $$$

    For $$$n = 2k+1$$$, we get

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

    This is, indeed, another known formula for Catalan numbers, and this time without division.

    And for the fuss Catalan numbers with $$$\phi(x) = 1 + x^k$$$, it would be

    $$$ [x^{n-1}](1+(1-k)x^k) \sum\limits_{i=0}^{n-1} \binom{n-1}{i} x^{ki} = \binom{kt}{t} + (1-k)\binom{kt}{t-1}. $$$
»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

I've seen this sequence (table) of numbers named as "Fuss Catalan numbers" in the book Concrete Mathematics where a combinatorial proof of the formula is given. And actually they are in OEIS at A062993.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    There are several sequences mentioned in the article... As I understand, you mean the table

    $$$ f(t, k) = \frac{1}{kt+1}\binom{kt+1}{t}, $$$

    which is related to $$$k$$$-ary trees with $$$t$$$ vertices.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah sorry, for k-ary trees. And btw, in the book it is mentioned that the generating function is really hard to solve, which always bugged me a bit. So thanks for this blog :)