5
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You are right. My description was vague and not fully correct, however, you understood it well. My proof of the formula proceeds in a similar way as yours. The request for the reference came from a reviewer of my paper. $\endgroup$ – Twi Feb 22 '15 at 11:22

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.