## September 18, 2017

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

### Re: Lattice Paths and Continued Fractions I

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.

Personally I’d like nothing better than a porism.

But since Flajolet got a lemma and I’m feeling faintly envious, who is this Flajolet? Phillipe Flajolet the French computer scientist?

Posted by: John Baez on September 21, 2017 1:17 AM | Permalink | Reply to this

### Re: Lattice Paths and Continued Fractions I

I confuse the notions of scholium and porism. I think I saw someone use scholium instead of porism when I was at an impressionable age. There is a mathoverflow question on this for those who need enlightening.

It was indeed that Philippe Flajolet. And to be clear, to say he was a computer scientist is not to say that he wasn’t a mathematician! He spoke at the ICM in Beijing in 2002. It seems, from how others have written about him, that he was very respected, with much warmth.

Posted by: Simon Willerton on September 21, 2017 9:15 AM | Permalink | Reply to this

### Re: Lattice Paths and Continued Fractions I

My book with Irving Segal and Zhengfang Zhou has a lot of scholia, because Segal (probably influenced by Newton) liked scholia. He disdained ‘propositions’, which he regarded as new-fangled decadence.

Posted by: John Baez on September 22, 2017 1:56 AM | Permalink | Reply to this

### Re: Lattice Paths and Continued Fractions I

New-fangled, really? Now you’ve got me curious. I thought they had been around for quite some time.

Posted by: Todd Trimble on September 22, 2017 11:51 AM | Permalink | Reply to this

### Re: Lattice Paths and Continued Fractions I

Surely someone’s leg is being pulled here (maybe mine!). Euclid’s Elements (in English translation) uses the term “Proposition” starting on page 1, so it’s hard to see how Segal could be serious.

I looked at Newton’s Principia and found the word “Proposition” many times, starting on page 103. Again this is in English translation; I haven’t looked at the Latin in which he wrote.

Posted by: Todd Trimble on September 22, 2017 6:11 PM | Permalink | Reply to this

### Re: Lattice Paths and Continued Fractions I

I don’t use the word “Proposition” to mean “Theorem with an inferiority complex” any more myself, for a quite different reason: the word “proposition” is also used by logicians and philosophers to mean essentially a statement, something that could be proven but could also be assumed or disproven, and in HoTT we’ve picked up this usage to refer to (-1)-groupoids.

Posted by: Mike Shulman on September 22, 2017 9:39 PM | Permalink | Reply to this

### Re: Lattice Paths and Continued Fractions I

Certainly that’s a venerable meaning of the word, but that would never stop me from using it with the other meaning. But maybe similar scruples were what was really underlying Segal’s objection.

Posted by: Todd Trimble on September 23, 2017 1:59 AM | Permalink | Reply to this

### Re: Lattice Paths and Continued Fractions I

Cool! I proved a result which I think is more or less equivalent to this one in this blog post, which also has some stuff about computing Hankel determinants relevant to the previous post, but I didn’t know it had a name.

Posted by: Qiaochu Yuan on January 4, 2018 12:14 AM | Permalink | Reply to this

### Re: Lattice Paths and Continued Fractions I

I guess that demonstrates how fundamental it is!

Posted by: Simon Willerton on January 4, 2018 12:38 PM | Permalink | Reply to this

Post a New Comment