info prev up next book cdrom email home

p-Good Path

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

\begin{displaymath}
y=(p-1)x.
\end{displaymath}

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

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

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

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

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.




© 1996-9 Eric W. Weisstein
1999-05-26