Recall that a Dyck path of length $2n$ is a lattice path in $\mathbb{Z}^2$ from $(0,0)$ to $(2n,0)$ consisting of $n$ up steps $U=(1,1)$ and $n$ down steps $D=(1,-1)$ which never goes below the $x$-axis. Let $\mathrm{Dyck}(2n)$ denote the set of such Dyck paths. Of course we have $$ \#\mathrm{Dyck}(2n)=\mathrm{Cat}(n) = \frac{1}{n+1}\binom{2n}{n}$$ the ubiquitous Catalan number.
A Motzkin path of length $\ell$ is a lattice path in $\mathbb{Z}^2$ from $(0,0)$ to $(\ell,0)$ consisting of some number of up steps $U=(1,1)$, down steps $D=(1,-1)$, and horizontal steps $H=(1,0)$ which never goes below the $x$-axis. Let $\mathrm{RBMotz}(\ell)$ denote the set of such Motzkin paths whose horizontal steps have each been colored either red or blue. For $\Gamma \in \mathrm{RBMotz}(\ell)$, set
- $r(\Gamma) := \#$ of red horizontal steps of $\Gamma$;
- $r^{*}(\Gamma) := \#$ of red horizontal steps of $\Gamma$ which occur at height one or higher (i.e., do not occur on the $x$-axis);
- $b(\Gamma) := \#$ of blue horizontal steps of $\Gamma$;
- $b^{*}(\Gamma) := \#$ of blue horizontal steps of $\Gamma$ which occur after the 1st down step.
Question: Do you know a reference for the fact that $$ \#\{\Gamma \in \mathrm{RBMotz}(\ell)\colon r(\Gamma)=r^{*}(\Gamma), b(\Gamma)=b^{*}(\Gamma)\} = \mathrm{Cat}(\ell-1)?$$
Note that I'm not asking for a proof of this formula; I know how to prove it. Actually I know a bijection to Dyck paths (see below). But I'm wondering if it's appeared in somewhere in the literature previously.
There are several known colored Motzkin path interpretations of the Catalan numbers. For instance:
- $\#\mathrm{RBMotz}(\ell) = \mathrm{Cat}(\ell+1)$;
- $\#\{\Gamma \in \mathrm{RBMotz}(\ell)\colon r(\Gamma)=r^{*}(\Gamma)\} = \mathrm{Cat}(\ell)$,
which you can find as exercises 40 and 41 in Chapter 2 of Richard Stanley's book "Catalan Numbers." This is why I'm thinking that the interpretation I'm interested in may be known.
How to prove it: The basic idea to define a bijection between these colored Motzkin paths and Dyck paths is to replace each step of the Motzkin path by two steps. For example, the bijection $\varepsilon\colon \{\Gamma \in \mathrm{RBMotz}(\ell)\colon r(\Gamma)=r^{*}(\Gamma)\}\to \mathrm{Dyck}(2\ell)$ works in exactly this way:
- $U\to UU$;
- $D\to DD$;
- $H_+ \to DU$;
- $H_- \to UD$.
Here $H_+$ means a red horizontal step and $H_-$ a blue horizontal step.
The one extra thing you need for the interpretation I'm interested is a "color-swapping" involution $\Psi\colon\mathrm{RBMotz}(\ell)\to\mathrm{RBMotz}(\ell)$ with the property that:
- $r(\Gamma)=b(\Psi(\Gamma))$;
- $r^{*}(\Gamma)=b^{*}(\Psi(\Gamma))$.
Such a $\Psi$ can be defined recursively: $$ \Psi(\Gamma) := \begin{cases} H_{\mp}\cdot \Psi(\Gamma') &\textrm{if $\Gamma=H_{\pm}\cdot \Gamma'$}; \\ U\cdot \Psi(\Gamma'') \cdot D \cdot \Psi(\Gamma') &\textrm{if $\Gamma=\overbrace{U\cdot \Gamma' \cdot D} \cdot \Gamma''$}. \end{cases}$$ Here $\Gamma=\overbrace{U\cdot \Gamma' \cdot D} \cdot \Gamma''$ means this first $U$ and the $D$ are "matched," i.e., this $D$ is the first return to the $x$-axis.
With $\varepsilon$ and $\Psi$ it's easy to (recursively) define the bijection $\alpha \colon \{\Gamma \in \mathrm{RBMotz}(\ell)\colon r(\Gamma)=r^{*}(\Gamma), b(\Gamma)=b^{*}(\Gamma)\}\to \mathrm{Dyck}(2(\ell-1))$: $$ \alpha(\Gamma=\overbrace{U\cdot \Gamma' \cdot D} \cdot \Gamma'') := U \cdot \varepsilon(\Psi(\Gamma')) \cdot D \cdot \varepsilon(\Gamma'')$$
I should say that this came up in joint work in progress with Alexander Lazar and Svante Linusson.
