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 22, 2017

Lattice Paths and Continued Fractions II

Posted by Simon Willerton

Last time we proved Flajolet’s Fundamental Lemma about enumerating Dyck paths. This time I want to give some examples, in particular to relate this to what I wrote previously about Dyck paths, Schröder paths and what they have to do with reverse Bessel polynomials.

We’ll see that the generating function of the sequence of reverse Bessel polynomials (θ i(R)) i=0 \left(\theta_i(R)\right)_{i=0}^\infty has the following continued fraction expansion.

i=0 θ i(R)t i=11Rtt1Rt2t1Rt3t1 \sum_{i=0}^\infty \theta_i(R) \,t^i = \frac{1}{1-Rt- \frac{t}{1-Rt - \frac{2t}{1-Rt- \frac{3t}{1-\dots}}}}

I’ll even give you a snippet of SageMath code so you can have a play around with this if you like.

Flajolet’s Fundamental Lemma

Let’s just recall from last time that if we take Motzkhin paths weighted by a ia_is, b ib_is and c ic_is as in this example,

weighted Motzkhin path

then when we sum the weightings of all Motzkhin paths together we have the following continued fraction expression. σ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]]

Jacobi continued fractions and Motzkhin paths

Flajolet’s Fundamental Lemma is very beautiful, but we want a power series going up in terms of path length. So let’s use another variable tt to keep track of path length. All three types of step in a Motzkhin path have length one. We can set a i=α ita_i=\alpha_i t, b i=β itb_i=\beta_i t and c i=γ itc_i=\gamma_i t. Then σw a,b,c(σ)[α i,β i,γ i][[t]]\sum_{\sigma} w_{a, b, c}(\sigma)\in \mathbb{Z}[\alpha_i, \beta_i, \gamma_i][[t]], and the coefficient of t t^\ell will be the sum of the weights of Motzkhin paths of length \ell. This coefficient will be a polynomial (rather than a power series) as there are only finitely paths of a given length.

=0 ( σMotzkhin lengthw α,β,γ(σ))t =11γ 0tα 1β 1t 21γ 1tα 2β 2t 21γ 2tα 3β 3t 21 \sum_{\ell=0}^\infty\left(\sum_{\sigma\,\,\text{Motzkhin length}\,\,\ell} w_{\alpha,\beta,\gamma}(\sigma)\right)t^\ell = \frac{1} {1- \gamma_{0}t - \frac{\alpha_{1}\beta_1 t^2} {1-\gamma_{1}t - \frac{\alpha_{2}\beta_2 t^2} {1- \gamma_2t - \frac{\alpha_3 \beta_3 t^2} {1-\dots }}}}

Such a continued fraction is called a Jacobi (or J-type) continued fraction. They crop up in the study of moments of orthogonal polynomials and also in birth-death processes.

For example, I believe that Euler proved the following Jacobi continued fraction expansion of the generating function of the factorials. =0 !t =11tt 213t4t 215t9t 21 \sum_{\ell=0}^\infty \ell!\, t^\ell = \frac{1} {1- t - \frac{t^2} {1-3 t - \frac{4 t^2} {1- 5t - \frac{9 t^2} {1-\dots }}}} We can get the right hand side by taking α i=β i=i\alpha_i=\beta_i=i and γ i=2i+1\gamma_i=2i+1. Here is a Motzkhin path weighted in that way.

weighted Motzkhin path

The equation above is telling us that if we weight Motzkhin paths in that way, then the weighted count of Motzkhin paths of length \ell is !\ell!, and that deserves an exclamation mark! (You’re invited to verify this for Motzkhin paths of length 4.)

I’ve put some SageMath code at the bottom of this post if you want to check the continued fraction equality numerically.

Stieltjes continued fractions and Dyck paths

A Dyck path is a Motzkhin path with no flat steps. So if we weight the flat steps in Motzkhin paths with 00 then when we do a weighted count then we just count the weighted Dyck paths. This means setting γ i=0\gamma_i=0.

Also the weigh α i\alpha_i on an up step always appears with the weight β i\beta_i on a corresponding down step (what goes up must come down!) so we can simplify things by just putting a weighting α iβ i\alpha_i\beta_i — which we’ll rename as α i\alpha_i — on the down step from level ii and put a weighting of 11 on each up step. We can call this weighting w αw_\alpha.

Putting this together we get the following, where we’ve noted that there are no Dyck paths of odd length.

n=0 ( σDyck length2nw α(σ))t 2n=11α 1t 21α 2t 21α 3t 21 \sum_{n=0}^\infty\left(\sum_{\sigma\,\,\text{Dyck length}\,\,2n} w_\alpha(\sigma)\right)t^{2n} = \frac{1} {1- \frac{\alpha_{1} t^2} {1- \frac{\alpha_{2} t^2} {1- \frac{\alpha_3 t^2} {1-\dots }}}}

This kind of continued fraction is called a Stieltjes (or S-type) continued fraction. Of course, we could replace t 2t^2 by tt in the above, without any ill effect.

Previously we proved combinatorially that with the weighting where α i=i\alpha_i=i the weighted count of Dyck paths of length 2n2n was precisely (2n1)!!(2n-1)!!. This means that we have proved the following continued fraction expansion of the generating function of the odd double factorials.

n=0 (2n1)!!t 2n=11t 212t 213t 21 \sum_{n=0}^\infty (2n -1)!!\, t^{2n} = \frac{1} {1- \frac{ t^2} {1- \frac{2 t^2} {1- \frac{3 t^2} {1-\dots }}}}

I believe this was originally proved by Gauss, but I have no idea how.

Again there’s some SageMath code at the end for you to see this in action.

Thron continued fractions and Schröder paths

What I’m really interested in, you’ll remember, is reverse Bessel polynomials, and these are giving weighted counts of Schroder paths. Using continued fractions in this context is less standard than for Dyck paths and Motzkhin paths as above, but it only requires a minor modification. I learnt about this from Alan Sokal.

The difference between Motzkhin paths and Schröoder paths is that the flat steps have length 22 in Schroder paths. Remember that the power of tt was encoding the length, so we just have to assign t 2t^2 to each flat step rather than tt. So if we put a i=ta_i= t, b i=α itb_i=\alpha_i t and c i=γ it 2c_i = \gamma_i t^2 in Flajolet’s Fundamental Lemma then we get the following.

n=0 ( σSchroder length2nw α,γ(σ))t 2n=11γ 0t 2α 1t 21γ 1t 2α 2t 21γ 2t 2α 3t 21 \sum_{n=0}^\infty\left(\sum_{\sigma\,\,\text{Schroder length}\,\,2n} w_{\alpha,\gamma}(\sigma)\right)t^{2n} = \frac{1} {1- \gamma_{0}t^2 - \frac{\alpha_{1} t^2} {1-\gamma_{1}t^2 - \frac{\alpha_{2} t^2} {1- \gamma_2t^2 - \frac{\alpha_3 t^2} {1-\dots }}}}

Here w α,γw_{\alpha, \gamma} is the weighting where we put α i\alpha_is on the down steps and γ i\gamma_is on the flat steps.

This kind of continued fraction is called a Thron (or T-type) continued fraction. Again, we could replace t 2t^2 by tt in the above, without any ill effect.

We saw before that if we take the weighting, w rBpw_{rBp}, with α i:=i\alpha_i:=i and γ i:=R\gamma_i:=R, such as in the following picture,

weighted schroder path

then the weighted sum of Schroder paths of length 2n2n is precisely the nnth reverse Bessel polynomial: θ i(R)= σSchroder length2nw rBp(σ). \theta_i(R)= \sum_{\sigma\,\,\text{Schroder length}\,\,2n} w_{rBp}(\sigma).

Putting that together with the Thron continued fraction above we get the following Thron continued fraction expansion for the generating function of the reverse Bessel polynomials.

n=0 θ n(R)t n=11Rtt1Rt2t1Rt3t1 \sum_{n=0}^\infty \theta_n(R) t^n = \frac{1}{1-Rt- \frac{t}{1-Rt - \frac{2t}{1-Rt- \frac{3t}{1-\dots}}}}

This expression is given by Paul Barry, without any reference, in the formulas section of the entry in the Online Encyclopedia of Integer Sequences.

See the end of the post for some SageMath code to check this numerically.

In my recent magnitude paper I actually work backwards. I start with the continued fraction expansion as a given, and use Flajolet’s Fundamental Lemma to give the Schr&\ouml;der path interpretation of the reverse Bessel polynomials. Of course, I now know that I can bypass the use of continued fractions completely, and have a purely combinatorial proof of this interpretation. Regardless of that, however, the theory of lattice paths and continued fractions remains beautiful.

Appendix: Some SageMath code

It’s quite easy to play around with these continued fractions in SageMath, at least to some finite order. I thought I’d let you have some code to get you started…

Here’s some SageMath code for you to check the Jacodi continued fraction expansion of the generating function of the factorials.

# T = Z[t]
T.<t> = PolynomialRing(ZZ)
# We'll take the truncated continued fraction to be in the 
# ring of rational functions, P = Z(t)
P = Frac(T)

def j_ctd_frac(alphas, gammas):
    if alphas == [] or gammas == []:
        return 1
        return P(1/(1 - gammas[0]*t - alphas[0]*t^2* 
                        j_ctd_frac(alphas[1:], gammas[1:])))

cf(t) = j_ctd_frac([1, 4, 9, 16, 25, 36], [1, 3, 5, 7, 9, 11]) 
print cf(t).series(t, 10)

The above code can be used to define a Stieltjes continued fraction and check out the expansion of Gauss on the odd double factorials.

def s_ctd_frac(alphas):
    gammas = [0]*len(alphas)
    return j_ctd_frac(alphas, gammas)

cf(t) = s_ctd_frac([1, 2, 3, 4, 5, 6])
print cf(t).series(t, 13)

Here’s the code for getting the reverse Bessel polynomials from a Thron continued fraction.

S.<R> = PolynomialRing(ZZ)
T.<t> = PowerSeriesRing(S)

def t_ctd_frac(alphas, gammas):
    if alphas == [] or gammas == []:
        return 1
        return (1/(1- gammas[0]*t^2 - alphas[0]*t^2* 
                      t_ctd_frac(alphas[1:], gammas[1:])))

print T(t_ctd_frac([1, 2, 3, 4, 5, 6], [R, R, R, R, R, R]),
Posted at September 22, 2017 10:14 AM UTC

TrackBack URL for this Entry:

1 Comment & 0 Trackbacks

Re: Lattice Paths and Continued Fractions II

Cool! All this has a lot of overlap with this old blog post of mine, although I didn’t know the names of most of the objects and results I was writing down.

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

Post a New Comment