Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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

weighted Motzkhin path

as a continued fraction

11c 0a 1b 11c 1a 2b 21c 2a 3b 31 \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 11.

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

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 \{a_i\}_{i=1}^\infty, {b i} i=1 \{b_i\}_{i=1}^\infty and {c i} i=0 \{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 ii will be given the weight a ia_i; each step going down from level ii will be given the weight b ib_i; and each flat step at level ii will be given weight c ic_i. Here’s the path from above with the weights marked on it.

weighted Motzkhin path

The weight w a,b,c(σ)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 2c_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+[[a i,b i,c i]] 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 xx-axis. So define a (h,k)(h,k)–path to be like a Motzkhin path except that it starts at some point (0,h)(0, h), for h0h\ge 0, does not go below the line y=hy=h nor above the line y=ky=k and finishes at some point (,h)(\ell, h). Let P h kP_h^k denote the set of all (h,k)(h,k)–paths.

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

high Motzkhin path

We want the weighted sum of all Motzkhin paths, so in order to calculate that we will take p h kp_h^k to be the sum of all weights of (h,k)(h,k)-paths: p h k σP h kw a,b,c(σ)[[a i,b i,c i]].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 h kp^k_h.

Observe first that any path in P k kP_k^k is constrained to lie at level kk so must simply be a product of flat steps which all have weight c kc_k, thus

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

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

An indecomposable (h,k)(h,k)-path is a path which only returns to level hh 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)(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 kP_{h+1}^k followed by a down step back to level hh. We let I h kI_{h}^k be the set of non-trivial indecomposable (h,k)(h,k)-paths.

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

p h k = σP h kw a,b,c(σ) = n=0 π i,,π nI h kw a,b,c(π 1π n) = n=0 π i,,π nI h kw a,b,c(π 1)w a,b,c(π n) =11 πI h kw a,b,c(π) =11c k σP h+1 ka h+1w a,b,c(σ)b h+1 =11c ka h+1b h+1 σP h+1 kw a,b,c(σ) =11c ka h+1b h+1p h+1 k \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 kp_h^k. Using the fact p k k=11c kp^k_k=\frac{1}{1-c_k} that we gave above, we obtain the following.

Lemma p h k=11c ha h+1b h+11c h+1a h+2b h+21c k1a kb k1c k 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=0h=0 and letting kk\to \infty we get the following continued fraction expansion for the weighted count of all Motzkhin paths starting at level 00.

Flajolet’s Fundamental Lemma σMotzkhinw a,b,c(σ)=11c 0a 1b 11c 1a 2b 21c 2a 3b 31[[a i,b i,c i]] \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

7 Comments & 0 Trackbacks

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

Post a New Comment