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.
