info prev up next book cdrom email home

Delannoy Number

The Delannoy numbers are defined by


where $D(0,0)=1$. They are the number of lattice paths from $(0,0)$ to $(b,a)$ in which only east (1, 0), north (0, 1), and northeast (1, 1) steps are allowed (i.e, $\rightarrow$, $\uparrow$, and $\nearrow$).


For $n\equiv a=b$, the Delannoy numbers are the number of ``king walks''


where $P_n(x)$ is a Legendre Polynomial (Moser 1955, Vardi 1991). Another expression is

D(n,n)=\sum_{k=0}^n{n\choose k}{n+k\choose k}={}_2F_1(-n,n+1;1,-1),

where ${a\choose b}$ is a Binomial Coefficient and ${}_2F_1(a,b;c;z)$ is a Hypergeometric Function. The values of $D(n,n)$ for $n=1$, 2, ... are 3, 13, 63, 321, 1683, 8989, 48639, ... (Sloane's A001850).

The Schröder Numbers bear the same relation to the Delannoy numbers as the Catalan Numbers do to the Binomial Coefficients.

See also Binomial Coefficient, Catalan Number, Motzkin Number, Schröder Number


Moser, L. ``King Paths on a Chessboard.'' Math. Gaz. 39, 54, 1955.

Sloane, N. J. A. Sequence A001850/M2942 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, 1991.

© 1996-9 Eric W. Weisstein