Skip to main content
Post Made Community Wiki
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253

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.