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


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


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

© 1996-9 Eric W. Weisstein