# Number of certain Dyck paths

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.

• Probably, you should replace some $n$ to another variable $k$. – Fedor Petrov Nov 30 '16 at 14:52
• So I expect catalan-generalised motzkin or something similar. But I found no source. – Mare Nov 30 '16 at 15:27
• 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. – T. Amdeberhan Nov 30 '16 at 23:05
• Have also a look here – Duchamp Gérard H. E. Dec 1 '16 at 2:14
• 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. – Ira Gessel Dec 1 '16 at 16:01

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.

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.