p-Good Path

A Lattice Path from one point to another is $p$-good if it lies completely below the line

$$y=(p-1)x.$$

Hilton and Pederson (1991) show that the number of $p$-good paths from (1, $q-1$) to ($k$, $n-k$) under the condition $2\leq k\leq n-p+1\leq p(k-1)$ is

$${n-q\choose k-1}-\sum_{j=1}^\ell {}_pd_{qj}{n-pj\choose k-j},$$

where ${a\choose b}$ is a Binomial Coefficient, and

$$\ell\equiv\left\lfloor{n-k\over p-1}\right\rfloor ,$$

where $\left\lfloor{x}\right\rfloor$ is the Floor Function.

See also Catalan Number, Lattice Path, Schröder Number

References

Hilton, P. and Pederson, J. ``Catalan Numbers, Their Generalization, and Their Uses.'' Math. Intel. 13, 64-75, 1991.