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.

 A: 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.
A: 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.
