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](http://oeis.org/search?q=1%2C5%2C21%2C81%2C302&sort=&language=english&go=Search) 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.
> 
> 
> 



Number of certain Dyck paths
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.


