4
$\begingroup$

Recall that a dyck $n$-path is a lattice path of length $2n$ with steps $U$ (ups corresponding to $(1,1)$) and $D$ (downs corresponding to $(1,-1)$) such that it starts at $(0,0)$ and never goes below the $x$-axis.

This sequence on OEIS gives the Number of Dyck $n$-paths with at least one $UUU$.

QUESTIONS. Is there a formula for the Number of Dyck n-paths with at least one $$UUUU...U \qquad \text{$k$ U's?}$$ Maybe we can start with small $k=4,5,\dots$? The result for $k=3$ seems to be very nice.

$\endgroup$
  • $\begingroup$ Probably, you should replace some $n$ to another variable $k$. $\endgroup$ – Fedor Petrov Nov 30 '16 at 14:52
  • $\begingroup$ So I expect catalan-generalised motzkin or something similar. But I found no source. $\endgroup$ – Mare Nov 30 '16 at 15:27
  • $\begingroup$ I suspect this would be very complicated soon with $k$. Already at $k=3$ the sequence carries a 3rd-order polynomial coefficients recurrence, so for higher values of $k$ the answers can only given by multiple sums. $\endgroup$ – T. Amdeberhan Nov 30 '16 at 23:05
  • 1
    $\begingroup$ Have also a look here $\endgroup$ – Duchamp Gérard H. E. Dec 1 '16 at 2:14
  • 1
    $\begingroup$ This problem can also be solved using the method of my student C. J. Wang's Ph.D. thesis, people.brandeis.edu/~gessel/homepage/students/wangthesis.pdf, though he doesn't apply the method to this particular problem. $\endgroup$ – Ira Gessel Dec 1 '16 at 16:01
6
$\begingroup$

First I will show one way to derive the generating function for Dyck paths, and then I will adapt it to count Dyck paths that avoid $U^k$ for any $k$.


Define $F(x,u)$ to be the generating function that counts partial Dyck paths using $x$ to mark the number of steps and $u$ to mark the ending height. Here, "partial" means we don't require them to end at height $0$. Note that $F(x,0)$ is then the generating function for Dyck paths.

Every partial Dyck path is either:

  • The Dyck path of length $0$
  • A Dyck path that ends in an up-step
  • A Dyck path that ends in a down-step

This translates to the following functional equation: $$ F(x,u) = 1 + xuF(x,u) + \frac{x}{u}\left(F(x,u) - F(x,0)\right). $$ The left-hand side $F(x,u)$ corresponds to "every partial Dyck path". On the right-hand side, the $1$ represents the Dyck path of length $0$, the $xuF(x,u)$ represents taking an existing partial Dyck path and adding an up-step (increasing the length and height by $1$), and the $\frac{x}{u}\left(F(x,u) - F(x,0)\right)$ represents taking an existing partial Dyck path not already at height zero and adding a down-step (increasing the length by $1$ and decreasing the height by $1$).

This functional equation can be solved with the kernel method. Let $F = F(x,u)$ and $F_0 = F(x,0)$, and rearrange the functional equation $$ \left(u - xu^2 - x\right)F = u - xF_0 $$ Let $K$ be the coefficient of $F$ and let $P$ be the right-hand side. Then, $F_0$ is a root of a factor of the resultant of $K$ and $P$ with respect to $u$: $$ \operatorname{Res}(K, P, u) = x\left(x^2F_0^2 - F_0 + 1\right). $$ So $F(x,0)$ is a root of the polynomial $x^2F(x,0)^2 - F(x,0) +1$. You can generate terms from this minimal polynomial in Maple, for example, with the command

series(RootOf(F0^2*x^2-F0+1, F0), x, 20);

We now adapt this to avoid $UUU$. Instead of appending $U$ or $D$ to an existing partial Dyck path, we append either $D$, $UD$, $UUD$. This prevents an occurrence of $UUU$. From this description, we derive a functional equation $$ F(x,u) = 1 + x^2F(x,u) + x^3uF(x,u) + \frac{x}{u}\left(F(x,u)-F(x,0)\right). $$ The kernel method find a minimal polynomial for $F(x,0)$: $$ x^4F_0^2 + (x^2-1)F_0 - 1. $$ Subtracting this generating function from the Catalan numbers gives the terms in the linked OEIS sequence.


To generalize to avoiding $U^k$, we allow steps of the form $U^iD$ for $0 \leq i \leq k-1$, giving the functional equation $$ F(x,u) = 1 + \frac{x}{u}\left(F(x,u)-F(x,0)\right) + \sum_{i=1}^{k-1} x^{i+1}u^{i-1}F(x,u), $$ which can again be solved with the kernel method for any fixed $k$.

It follows that all of these generating functions are algebraic, and their asymptotics can be extracted using analytic methods.

$\endgroup$
2
$\begingroup$

The number of Dyck paths avoiding $U^k$ has been studied in some detail in https://arxiv.org/pdf/1508.01688v5.pdf under the name "generalized Motzkin numbers", $M_{k-1,n}$.

Proposition 3.2 gives several equivalent characterizations in terms of other objects. Theorem 4.8 gives an alternating sum for the number.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.