Continued Fractions and Flows on Flat Tori

Lattice Paths and Continued Fractions I

Posted by Simon Willerton

In my last post I talked about certain types of lattice paths with weightings on them and formulas for the weighted count of the paths, in particular I was interested in expressing the reverse Bessel polynomials as a certain weighted count of Schröder paths. I alluded to some connection with continued fractions and it is this connection that I want to explain here and in my next post.

In this post I want to prove Flajolet's Fundamental Lemma. Alan Sokal calls this Flajolet's Master Theorem, but Viennot takes the stance that it deserves the high accolade of being described as a 'Fundamental Lemma', citing Aigner and Ziegler in Proofs from THE BOOK:

"The essence of mathematics is proving theorems – and so, that is what mathematicians do: They prove theorems. But to tell the truth, what they really want to prove, once in their lifetime, is a Lemma, like the one by Fatou in analysis, the Lemma of Gauss in number theory, or the Burnside-Frobenius Lemma in combinatorics.

"Now what makes a mathematical statement a true Lemma? First, it should be applicable to a wide variety of instances, even seemingly unrelated problems. Secondly, the statement should, once you have seen it, be completely obvious. The reaction of the reader might well be one of faint envy: Why haven't I noticed this before? And thirdly, on an esthetic level, the Lemma – including its proof – should be beautiful!"

Interestingly, Aigner and Ziegler were building up to describing a result of Viennot's – the Gessel-Lindström-Viennot Lemma – as a fundamental lemma! (I hope to talk about that lemma in a later post.)

Anyway, Flajolet's Fundamental Lemma that I will describe and prove below is about expressing the weighted count of paths that look like

as a continued fraction

$$\frac{1} {1- c_{0} - \frac{a_{1} b_{1}} {1-c_{1} - \frac{a_{2} b_{2}} {1- c_2 - \frac{a_3 b_3} {1-\dots }}}}$$

Next time I'll give a few examples, including the connection with reverse Bessel polynomials.

Motzkhin paths

We consider Motzkhin paths, which are like Dyck paths and Schröder paths we considered last time, but here the flat paths have length $1$.

A Motzkhin path, then, is a lattice path in $\mathbb{N}^2$ starting at $(0, 0)$, having steps in the direction $(1,1)$, $(1,-1)$ or $(1,0)$. The path finishes at some $(\ell, 0)$. Here is a Motzkhin path.

(Actually at this point the length of each step is a bit of a red herring, but let's not worry about that.)

We want to count weighted paths, so we're going to have to weight them. We'll do it in a universal way to start with. Let $\{a_i\}_{i=1}^\infty$, $\{b_i\}_{i=1}^\infty$ and $\{c_i\}_{i=0}^\infty$, be three sets of commuting indeterminates. Now weight each step in a path in the following way. Each step going up to level $i$ will be given the weight $a_i$; each step going down from level $i$ will be given the weight $b_i$; and each flat step at level $i$ will be given weight $c_i$. Here's the path from above with the weights marked on it.

The weight $w_{a,b,c}(\sigma)$ of a path $\sigma$ is just the product of the weights of each of its steps, so the weight of the above path is $c_0a_1^2b_1^2c_1a_2b_2$.

If you try to start writing down the sum of the weightings of all Motzkhin paths you'll get a power series that begins

$$1 + c_0 + a_1b_1 + c_0^2 + 2a_1b_1c_0 + a_1b_1c_1 + c_0^3 + \dots \in\mathbb{Z}[[a_i, b_i, c_i]]$$

Flajolet's Fundamental Lemma will give us a formula for this power series.

Flajolet's Fundamental Lemma

In order to prove the result about the enumeration of weightings of all paths we will need to consider slightly more general paths that don't just start on the $x$-axis. So define a $(h,k)$–path to be like a Motzkhin path except that it starts at some point $(0, h)$, for $h\ge 0$, does not go below the line $y=h$ nor above the line $y=k$ and finishes at some point $(\ell, h)$. Let $P_h^k$ denote the set of all $(h,k)$–paths.

Here is a $(2,4)$–path with the weights marked on. Of course this is also, for instance, a $(2,13)$–path.

We want the weighted sum of all Motzkhin paths, so in order to calculate that we will take $p_h^k$ to be the sum of all weights of $(h,k)$-paths: $$p_h^k\coloneqq \sum_{\sigma\in P_h^k} w_{a,b,c}(\sigma)\in \mathbb{Z}[[a_i, b_i, c_i]].$$ There is a beautifully simple expression for $p^k_h$.

Observe first that any path in $P_k^k$ is constrained to lie at level $k$ so must simply be a product of flat steps which all have weight $c_k$, thus

$$p^k_k = 1 + c_k +c_k^2 + c_k^3+\dots = \frac{1}{1-c_k}.$$

Given two paths $\sigma_1, \sigma_2\in P^k_h$ we can multiply them together simply by placing $\sigma_2$ after $\sigma_1$. The above pictured example is the product of three paths in $P_2^4$, the middle one being a flat path. Weighting is clearly preserved by this multiplication: $w_{a,b,c}(\sigma_1\sigma_2)=w_{a,b,c}(\sigma_1)w_{a,b,c}(\sigma_2)$.

An indecomposable $(h,k)$-path is a path which only returns to level $h$ at its finishing point, i.e. as the name suggests, it can not be decomposed into a non-trivial product. It is clear that any path uniquely decomposes as a product of indecomposable paths. There are two types of non-trivial indecomposable $(h,k)$-paths: there is the single flat step; and there are the paths which are an up step followed by a path in $P_{h+1}^k$ followed by a down step back to level $h$. We let $I_{h}^k$ be the set of non-trivial indecomposable $(h,k)$-paths.

This all leads to the following argument to deduce an expression for the weighted count of all $(h,k)$-paths.

$$\begin{aligned} p^k_h&=\sum_{\sigma\in P^k_h} w_{a,b,c}(\sigma)\\ &= \sum_{n=0}^\infty \sum_{\pi_i,\dots,\pi_n \in I^k_h} w_{a,b,c}(\pi_1\dots \pi_n)\\ &= \sum_{n=0}^\infty \sum_{\pi_i,\dots,\pi_n \in I^k_h} w_{a,b,c}(\pi_1)\dots w_{a,b,c}(\pi_n)\\ &= \frac{1}{1- \sum_{\pi\in I^k_h} w_{a,b,c}(\pi)} \\ &= \frac{1}{1- c_k - \sum_{\sigma\in P^k_{h+1}}a_{h+1} w_{a,b,c}(\sigma)b_{h+1}} \\ &= \frac{1}{1- c_k- a_{h+1}b_{h+1}\sum_{\sigma\in P^k_{h+1}} w_{a,b,c}(\sigma)} \\ &= \frac{1}{1- c_k - a_{h+1} b_{h+1}p_{h+1}^k} \end{aligned}$$

This is a lovely recursive expression for the weighted count $p_h^k$. Using the fact $p^k_k=\frac{1}{1-c_k}$ that we gave above, we obtain the following.

Lemma $$p_h^k= \frac{1} {1- c_{h} - \frac{a_{h+1} b_{h+1}} {1-c_{h+1} - \frac{a_{h+2} b_{h+2}} {\qquad \frac{\vdots}{1- c_{k-1}-\frac{a_k b_k}{1-c_k}} }}}$$

Now taking $h=0$ and letting $k\to \infty$ we get the following continued fraction expansion for the weighted count of all Motzkhin paths starting at level $0$.

Flajolet's Fundamental Lemma $$\sum_{\sigma\,\,\mathrm{Motzkhin}} w_{a,b,c}(\sigma) = \frac{1} {1- c_{0} - \frac{a_{1} b_{1}} {1-c_{1} - \frac{a_{2} b_{2}} {1- c_2 - \frac{a_3 b_3} {1-\dots }}}} \in\mathbb{Z}[[a_i, b_i, c_i]]$$

How lovely and simple is that?

Next time I'll give some examples and applications which include the Dyck paths and Scröder paths we looked at previously.

Posted at September 18, 2017 12:18 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2983

washingtonchases.blogspot.com

Source: https://golem.ph.utexas.edu/category/2017/09/lattice_paths_and_continued_fr.html

Share this post