The n-Category Café

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.