Dyck Paths with varying upstep size A problem I have been thinking about for a few years boils down to something very similar to the generalized ballot problem. Consider (something that seems very close to) a Dyck path starting at $(0,I)$ and ending at $(N,0)$ with downsteps $(1,-1)$. The upsteps are allowed to be one of the 4: $(1,R_1), (1,R_2), (1,R_3), (1,R_4)$. I am trying to calculate the number of paths/sequences of the $4$ upsteps, and $1$ downstep that ultimately get you from start to finish, while never going below or touching the $x$-axis. I have been stuck along while just trying to figure this out for a single upstep, so I can't say I have tried much. Any direction appreciated!
 A: Let's start with an easier case where $I=0$ and paths are allowed to touch the $x$-axis, and use the kernel method.
Let $F(x,y)$ be the ordinary generating function over all paths of length $n$ that end at height $h\ge 0$, i.e. $F(x,y)=\sum_{P} x^{\operatorname{length}(P)} y^{\operatorname{height}(P)}$, where $P$ runs over all paths that start at $(0,0)$, stay on or above the $x$-axis, and have unit steps $d=(1,-1)$ and $u_j=(1,r)$ for $r\in\{r_j\mid 1\le j\le k\}$ (in your example, $k=4$), $\operatorname{length}(P)$ is the number of steps in $P$, and $\operatorname{height}(P)$ is the terminal height of $P$. Then, partitioning the paths based on their last step, we get the following for their generating function:
$$
F(x,y)=1+\sum_{j=1}^{k}{xy^{r_j}F(x,y)}+\frac{x}{y}(F(x,y)-F(x,0)).
$$
Multiplying through by $y$ and putting all terms with $F(x,y)$ on the left, we get
$$
\left(y-x\left(1+\sum_{j=1}^{k}{y^{r_j+1}}\right)\right)F(x,y)=1-\frac{x}{y}F(x,0).
$$
Let $y$ be a solution of
$$
y-x\left(1+\sum_{j=1}^{k}{y^{r_j+1}}\right)=0,
$$
in other words, $y$ is the compositional inverse
$$
y=\left(\frac{x}{1+\sum_{j=1}^{k}{x^{r_j+1}}}\right)^{\langle-1\rangle}
$$
then $F(x,0)=\dfrac{y}{x}$. Equivalently, $u=u(x)=F(x,0)$ is a solution of the functional equation
$$
u=1+\sum_{j=1}^{k}{(xu)^{r_j+1}}.
$$
In the specific case you mention, the set of multiplicities is $\{2,5,6,8\}$, so your generating function satisfies the equation
$$
u=1+x^3u^3+x^6u^6+x^7u^7+x^9u^9.
$$
If you want to see how this sequence starts, run the following Mathematica code:
CoefficientList[u/.AsymptoticSolve[u-1-x^3*u^3-x^6*u^6-x^7*u^7-x^9*u^9==0,u->1,{x,0,24}][[1]],x]

It yields this sequence:
{1,0,0,1,0,0,4,1,0,22,10,0,139,91,7,953,816,136,6894,7296,1900,51866,65296,23276,402293}

=====
Now let us consider paths as above that start at $(0,I)$, $I\ge 0$, and end at $(N,0)$, $N\ge 0$. Shine an imaginary flashlight horizontally to the right under the path. (Alternatively, dig imaginary horizontal tunnels to the left of every down-step until you hit an up-step or the $y$-axis.) You will light precisely $I$ down-steps. Moving along the path from left to right, the $k$-th such down-step $d_k$ is the first step ending at height $I-k$ for $k=1,2,\dots,I$. This will decompose such a path as
$$
U_0d_1U_1d_2U_2\dots d_IU_I,
$$
where each $U_k$ is a path starting and ending on the $x$-axis that was lifted up by $I-k$ units, i.e. a path of the type considered in the previous part. Therefore, the generating function for such paths is
$$
v=x^Iu^{I+1}=\frac{1}{x}y^{I+1},
$$
where $y$ satisfies
$$
y=x\left(1+\sum_{j=1}^{k}{y^{r_j+1}}\right).
$$
Using Lagrange inversion now yields
$$
\begin{split}
[x^n]v&=[x^{n+1}]y^I=\frac{1}{n+1}[y^n]Iy^{I-1}\left(1+\sum_{j=1}^{k}{y^{r_j+1}}\right)^{n+1}\\
&=\frac{I}{n+1}\left[y^{n+1-I}\right]\left(1+\sum_{j=1}^{k}{y^{r_j+1}}\right)^{n+1}.
\end{split}
$$
