Delannoy Number

The Delannoy numbers are defined by

$$D(a,b)=D(a-1,b)+D(a,b-1)+D(a-1,b-1),$$

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''

$$D(n,n)=P_n(3),$$

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

References

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.'' http://www.research.att.com/~njas/sequences/eisonline.html 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.