2
$\begingroup$

A Dyck word is a sequence of open and closed brackets such that the brackets come in correctly matched pairs. For example $(()(()))()$ is a Dyck word, while $())(()$ is not. A Dyck path is a visual representation of a Dyck word, where for every open bracket the path goes up one step and for every closed bracket the path goes down one step. For example the Dyck path to $(()(()))()$ is enter image description here It is easily seen that the Dyck path uniquely determines the Dyck word and that any such path, which stays above or at the starting height and ends at the starting height, is a Dyck path. A peak in a Dyck word is an occurrence of $()$.

Let $D(n,k)$ denote the set of Dyck paths/words of length $2n$ with $k$ many peaks, then the cardinality $\#D(n,k)$ is given by the Narayana numbers $N(n,k) = \frac{1}{n} {n \choose k} {n \choose k-1}$.

Question: In the asymptotic regime where $N(n,k)$ is largest (that is $\frac{k}{n} \rightarrow \frac{1}{2}$) I am interested in the limiting distribution of the peaks on the horizontal axis. For any Dyck word $w \in D(n,k)$ let $q_1(w),...,q_k(w) \in [2n-1]$ denote the positions of the peaks of $w$, i.e. such that the positions $q_i,q_{i}+1$ in $w$ are filled with $()$ for all $i \leq k$. If we rescale the interval $[0,2n]$ to $[0,1]$, we can describe a probability distribution \begin{align*} & \mu_{n,k} := \frac{1}{N(n,k)} \frac{1}{k} \sum\limits_{w \in D(n,k)} \sum\limits_{i \leq k} \delta_{\frac{1}{2n}q_i(w)} \ . \end{align*} I would be very interested in the weak limit of $\mu_{n,k}$ in the regime $\frac{k}{n} \rightarrow \frac{1}{2}$.

Any help is much appreciated!

Improve this question
$\endgroup$
6
  • $\begingroup$ Here's another comment: there is a straightforward bijection between Dyck paths of length $2n$ with $k$ peaks, and pairs $\alpha=(\alpha_1,\ldots,\alpha_k)$, $\beta=(\beta_1,\ldots,\beta_k)$ of compositions of $n$ into $k$ parts for which $\alpha_1 + \alpha_2 + \cdots + \alpha_i \geq \beta_1 + \beta_2 + \cdots + \beta_i$ for all $i$. We simply record the lengths of the up (respectively, down) run in $\alpha$ (resp., $\beta$). For example, in your pictured Dyck path we have $\alpha = (2,2,1)$ and $\beta=(1,3,1)$. This could be a useful alternative perspective for your problem. $\endgroup$
    – Sam Hopkins
    Commented Nov 7, 2023 at 14:52
  • 2
    $\begingroup$ I suspect that equidistribution is almost certain. Here is a sketch of a proof: In @SamHopkins's notation, put $\lambda_i = \alpha_1+\cdots+ \alpha_i$ and $\mu_i = \beta_1 + \cdots + \beta_i$. Then Narayana numbers correspond to pairs of partitions $\lambda \subset \mu \subset [k-1] \times [n-k]$. So, sending $n \to \infty$ with $k/n \to r$, one can rescale $\lambda$ and $\mu$ and imagine them as noncrossing paths from $(0,0)$ to $(r,1-r)$, and one wants to know what the most likely such path is. (continued) $\endgroup$
    – David E Speyer
    Commented Nov 7, 2023 at 16:02
  • 2
    $\begingroup$ If you look at a single partition in the $k \times (n-k)$ box, as $n \to \infty$ with $k/n \to r$, it is almost certain that the path will limit to the straight line. This is because the entropy function $\lim_{n \to \infty} \tfrac{1}{n} \log \binom{n}{pn} = - p \log p - (1-p) \log (1-p)$ is convex in $p$, so it is optimal to have the curve take the same slope everywhere. I wrote this up in a blogpost a long time ago sbseminar.wordpress.com/2011/10/02/random-partitions-i . (continued) $\endgroup$
    – David E Speyer
    Commented Nov 7, 2023 at 16:06
  • 2
    $\begingroup$ This time we have two paths which are constrained to be noncrossing. But, if the rescaled paths ever get a constant distance apart, the previous analysis will take over and make them both become line segments. So I think the optimum will just be that both paths limit to the diagonal of the rectangle, and the peaks are equidistributed. $\endgroup$
    – David E Speyer
    Commented Nov 7, 2023 at 16:08
  • 2
    $\begingroup$ Cohn, Larsen and Propp computed the limiting shape of a plane partition in the box of size $(\alpha n) \times (\beta n) \times (\gamma n)$; it is is frozen outside an inscribed ellipse. nyjm.albany.edu/j/1998/4-10.pdf . You want plane partitions inside $2 \times (k-1) \times (n-k)$, which we can think of as $(\alpha, \beta, \gamma) = (0, r, 1-r)$. I'm not sure that their paper directly applies when one of the rescaled side lengths limits to zero, but it tells me which way to bet. $\endgroup$
    – David E Speyer
    Commented Nov 7, 2023 at 16:11

0

Reset to default

You must log in to answer this question.