Number of Dyck paths with prescribed number of edges

Question

I am trying to find a formula for the trace of certain matrix. To do that I was forced to determine the number of Dyck paths with prescribed number of edges.

By a Dyck path I mean a lattice path from $(0,0)$ to $(2n,0)$ consisting of $n$ steps of type $(1,1)$ and $n$ steps of type $(1,-1)$ never going below the $x$-axis (y=0). It is well known the number of Dyck paths equals the $n$th Catalan number.

If a multiindex $m=(m_{1},\dots,m_{\ell})\in\mathbb{N}^{\ell}$ is given I consider the set of Dyck paths which encounter edges $(j,j+1)$ and $(j+1,j)$ exactly $2m_{j}$ times. Let me denote the set of such paths by $\Omega(m)$. I can prove (and it is not very difficult) that $$ |\Omega(m)|=\prod_{j=1}^{\ell-1}\binom{m_j+m_{j+1}-1}{m_{j+1}}. $$

For sure, this has to be known. I would like to know some references on works dealing with these paths (depending on a multiindex). Since the problem I am working on is not in its nature combinatorial, I would like to only use the existing terminology and results and cite other papers. Perhaps someone knows the original work with the above formula. Thanks a lot.

Answer 1

This formula is Proposition 3B in P. Flajolet, Combinatorial Aspects of Continued Fractions, Discrete Math 32 (1980), 125–161.

Answer 2

I don't have a reference, but this is too long for a comment.

I find the definition of "encounter" and your notation for edges confusing, so let me rewrite your definition as I understand it: If $m = \left(m_1, m_2, \ldots, m_k\right)$ is a $k$-tuple of nonnegative integers, then $\Omega\left(m\right)$ shall denote the set of all Dyck paths from $\left(0, 0\right)$ to $\left(2n, 0\right)$ (not $\left(0, 2n\right)$) such that, for every positive integer $i$, the number of steps of the form $\left(p, i-1\right) \to \left(p+1, i\right)$ in the path equals $m_i$. Here, $m_i$ is defined to be $0$ when $i>k$.

Your formula then follows by induction over $k$, once we notice that, if $m = \left(m_1, m_2, \ldots, m_k\right)$ and $\overline{m} = \left(m_1, m_2, \ldots, m_{k-1}\right)$, then the paths in $\Omega\left(m\right)$ are obtained as follows: Choose a path $p$ in $\Omega\left(\overline{m}\right)$, and modify $p$ by "inserting" two-step "excursions" (of the form $/\backslash$) to height $k$ at $m_k$ of the $m_{k-1}$ points at which $p$ reaches height $k-1$. Note that these $m_{k-1}$ points are peaks of $p$, and we are allowed to install several excursions at one and the same peak.

I would suggest writing up a proof as a service to your readers even if this does prove to be a well-known result.