2
$\begingroup$

Recall that a Motzkin path is a piece-wise linear planar path connecting points in the integer lattice quadrant $\Bbb{Z}_{\geq 0} \times \Bbb{Z}_{\geq 0}$ beginning at the origin $(0,0)$ and ending at $(n,0)$ for some $n \in \Bbb{Z}_{>0}$ whose steps are either

\begin{equation} \begin{array}{ll} \nearrow & = (1,1) \\ \searrow & = (1,-1) \\ \rightarrow & = (1,0) \end{array} \end{equation}

Alternatively we may view a Motzkin path as an $n$-tuple $\underline{\pi} = \big(\pi_1, \dots, \pi_n \big)$ where $\pi_i \in \{ \nearrow \, , \searrow \, , \rightarrow \}$ for each $1 \leq i \leq n$ and where $\pi_1 + \cdots + \pi_n = (n,0)$. The set of Motzkin paths $\underline{\pi}$ terminating at $(n,0)$ will be denoted $\mathcal{M}_n$. Among the Motzkin paths $\mathcal{M}_n$ is the subset of what I'll call Fibonacci-Motzkin paths: These are paths that weakly increase until a threshold is reached, after which they strictly decrease. More specifically $\underline{\pi} = (\pi_1, \dots, \pi_n) \in \mathcal{M}_n$ is a Fibonacci-Motzkin path if there exists a threshold $ 0 \leq k \leq \lfloor {1 \over 2} n \rfloor $ such that $\pi_i \in \{ \nearrow, \, \rightarrow \}$ for all $1 \leq i \leq n - k$ and $\pi_i = \searrow$ for all $n-k < i \leq n$. The threshold $k$ equals the number of $\nearrow$ steps taken in the initial ascent of the path. A moment's reflection should convince the reader that the cardinality of the set $\mathcal{F}_n$ of all Fibonacci-Motzkin paths is indeed the $n$-th Fibonacci number, thus justifying the choice of terminology.

Received wisdom tells us to introduce two infinite families of generic parameters $\beta_1, \beta_2, \beta_3, \dots$ and $\gamma_0, \gamma_1, \gamma_2, \dots$ and then assign a weight

\begin{equation} \mathrm{w}(\underline{\pi}) \, := \ \beta_1 \cdots \beta_k \cdot \gamma_0^{m_0} \cdots \gamma_k^{m_k} \end{equation}

to a Motzkin path $\underline{\pi} \in \mathcal{M}_n$ where

\begin{equation} \begin{array}{ll} k &\text{$=$ number of $\nearrow$ steps taken by $\underline{\pi}$} \\ m_\ell &\text{$=$ number of $\rightarrow$ steps taken by $\underline{\pi}$ at height $\ell$} \end{array} \end{equation}

The corresponding generating function of all Motzkin paths, given by

\begin{equation} M(z) := \ 1 \ + \ \sum_{n \, \geq \, 1} z^n \sum_{\underline{\pi} \, \in \, \mathcal{M}_n} \, \mathrm{w}(\underline{\pi}) \end{equation}

is then seen to coincide with the formal expansion of the $J$-type continued fraction

\begin{equation} \ {1 \over {1 - z \gamma_0 \ - \ {\displaystyle z^2 \beta_1 \over {\displaystyle 1 - z \gamma_1 \ - \ {z^2 \beta_2 \over {\displaystyle 1 - z \gamma_2 \ - \ {z^2 \beta_3 \over {\ddots}}}}}}}} \end{equation}

Let us introduce a Fibonacci analogue of the generating function $M(z)$ namely

\begin{equation} F(z) := \ 1 \ + \ \sum_{n \, \geq \, 1} z^n \sum_{\underline{\pi} \, \in \, \mathcal{F}_n} \, \mathrm{w}(\underline{\pi}) \end{equation}

Question: Is there some kind of continued fraction whose expansion is $F(z)$?

thanks, ines.

$\endgroup$
3
$\begingroup$

Grouping the terms of $F(z)$ by the height reached, we get $$F(z) = \frac{1}{(1 - z\gamma_0)} + \frac{z^2 \beta_1}{(1 - z\gamma_0) (1 - z\gamma_1)} + \frac{z^4 \beta_1 \beta_2}{(1 - z\gamma_0) (1 - z\gamma_1) (1 - z\gamma_2)} + \cdots \\ $$ This has the form of Euler's continued fraction $$a_0 + a_0a_1 + a_0a_1a_2 + \cdots = \cfrac{a_0}{1 - \cfrac{a_1}{1 + a_1 - \cfrac{a_2}{1 + a_2 - \ddots}}}$$ with $$a_0 = \frac{1}{1 - z\gamma_0} \\ a_1 = \frac{z^2 \beta_1}{1 - z \gamma_1} \\ a_2 = \frac{z^2 \beta_2}{1 - z \gamma_2} \\ \vdots $$ It is perhaps more natural to drop the denominators to the next level: i.e. instead of $$\cfrac{\frac{1}{1 - z\gamma_0}}{1 - \cfrac{\frac{z^2 \beta_1}{(1 - z \gamma_1)}}{1 + \frac{z^2 \beta_1}{(1 - z \gamma_1)} - \cfrac{\frac{z^2 \beta_2}{(1 - z \gamma_2)}}{1 + \frac{z^2 \beta_2}{(1 - z \gamma_2)} - \ddots}}}$$ we could write $$\cfrac{1}{(1 - z\gamma_0) - \cfrac{(1 - z\gamma_0) z^2 \beta_1}{(1 - z \gamma_1) + z^2 \beta_1 - \cfrac{(1 - z \gamma_1) z^2 \beta_2}{(1 - z \gamma_2) + z^2 \beta_2 - \ddots}}}$$

$\endgroup$
8
  • $\begingroup$ Why do you have a square $(1 -z\gamma_0)^2$ in the denominator for the $\beta_1$-terms? It seems to me that the height one terms contribute $z^2 \beta_1 \sum_{n \geq 0} {\gamma_0^{n+1} -\gamma_1^{n+1} \over {\gamma_0 - \gamma_1}} z^n = {z^2\beta_1 \over {(1-z\gamma_0)(1-z\gamma_1) } }$. $\endgroup$ May 4 at 23:23
  • $\begingroup$ In fact, shouldn't all the denominators be multiplicity free --- i.e. the height $k$-terms contributing $z^{2k}\beta_1 \cdots \beta_k (1 - z\gamma_0)^{-1} \cdots (1 - z\gamma_k)^{-1}$ ? $\endgroup$ May 4 at 23:29
  • $\begingroup$ Otherwise we don't recover the Fibonacci generating function $(1 - z -z^2)^{-1}$ upon specializing all the $\gamma$'s and $\beta$'s to 1. $\endgroup$ May 5 at 0:42
  • $\begingroup$ To put it differently, shouldn't $a_k = z^2\beta_k (1 -z\gamma_k )^{-1}$ for $k \geq 1$ ? $\endgroup$ May 5 at 2:12
  • 1
    $\begingroup$ @InesInstitoris, I don't know. The closest I've been able to find in about twenty minutes' research is the Hankel continued fractions of this paper, but they should have numerators which are cubic monomials rather than cubic polynomials. $\endgroup$ May 5 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.