2
$\begingroup$

I have a pretty simple question for which I was not able to find a so simple answer.

Introduction

I was playing around with some of the mathematical objects that can be enumerated by Catalan numbers. One of them are the famous strings of correctly matched parentheses.

Let $P^{(n)}$ be the set containing all correctly matched parentheses strings of length $2n$, and imagine there exists a bijective funcion $f$ mapping each of the strings $s^{(n)}$ in $P^{(n)}$ to the set of integers ${1, 2, ..., n}$ such that each string of length $n$ can be denoted as $s_i^{(n)}$ where $i=f(s)$.

Define now our function of interest $G_i^n(k)$ as a function acting on the $k$-th parenthesis of $s_i^{(n)}$ the following way:

· If the $k$-th parentheses is "(", it takes the value $0$.

· If the $k$-th parentheses is ")", it takes the number of already matched "(" characters in the string to the closest unmatched "(" to its left plus one.

This can also be described by the following algorithm:

  1. Look at the parentheses in the $k$-th position. If it is a "(", you output $0$ and the algorithm is finished. Otherwise, you continue to $2$.

  2. Move one position to the left and check the parentheses there. If it is a ")", you do nothing and return to step $2$. If it is an already matched "(", you increase the output of the function by $1$ and return to step $2$. If it is an unmatched "(", you increase the output of the function by $1$, mark that parentheses as already matched and exit the algorithm by outputing the accumulated value of the funcion

While this may seem a bit of a mess, it is easy to see with a few examples. Focusing on two of the $n=3$ cases, the string:

$$ (()())$$

would produce the following resulting values:

$$(0,0,1,0,1,3)$$

And, for the string:

$$()(())$$

the function would take values:

$$(0,1,0,0,1,2)$$

I apologize if the notation is not precise or non-standard in any way.

My main question is just what it is known about this function and whether it has a closed form.

My work

After spending some time on it, I was able to identify my original problem both with Dyck paths and with full rooted binary trees. Regarding the former, $G$ can be seen as the "width" of the Dyck's path peak as seen from right to left from the $k$-th point divided by $2$. The previous examples can be expressed (using the conventional bijection of taking "(" to a step $(1,1)$ and ")" to a step $(1,-1)$) as:

path 1

And:

path 2

Then, the function I am studying can also be expressed in terms of the heights and $x$ coordinate of the peaks and valleys of the path to the left side of the $k$-th point.

The question

I just want to know whether this function has already been studied or if there's any closed form for it. I would also appreciate if anyone could point me to useful references regarding this topic, since most of the bibliography I could find tends to focus on counting the number of Dyck paths following certain specific patterns rather than what I am looking for here.

Thank you very much in advance!

Edit:

Thank you very much for the comments. It turns out that what I am looking for is called either "chords" or "multitunnel" in Dyck paths depending on the author. It would be great to find a generating function involving their length. I will continue searching for references.

Update:

After some research, there seem to be some papers regarding the number of certain types of tunnels, but none studying their lengths, which is the parameter I would be interested in. Any other reference would be highly appreciated!

$\endgroup$
3
  • 1
    $\begingroup$ It's not clear what you mean by "closed form": do you mean, for the corresponding generating function over all Dyck paths? At any rate, you might poke around findstat.org to see if your statistic has been explored before (I'm sure it has...) $\endgroup$ Commented Mar 2, 2022 at 1:26
  • 2
    $\begingroup$ Is this the chord length statistic on Dyck paths in work of Wilson and Kenyon? (cf Figure 4 in J.S. Kim's article: arxiv.org/pdf/1108.5558.pdf) $\endgroup$
    – user61318
    Commented Mar 2, 2022 at 1:32
  • 3
    $\begingroup$ Looks like the tunnels of Elizalde and Deutsch: arxiv.org/pdf/math/0306125.pdf $\endgroup$ Commented Mar 2, 2022 at 1:40

0

You must log in to answer this question.

Browse other questions tagged .