The Delannoy numbers 
are the number of lattice paths from 
to 
in which only east (1, 0), north (0, 1), and northeast
(1, 1) steps are allowed (i.e., 
, 
, and 
), for nonnegative
integers 
and 
. For 
, they satisfy the recurrence relation
 |
(1)
|
with 
. For nonnegative
integers 
and 
, they are also given by the sums
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
where the third expression requires 
and 
is a hypergeometric
function.
A table for values for the Delannoy numbers is given by
 |
(5)
|
(OEIS A008288) for 
, 1, ... increasing from left to right and 
, 1, ... increasing from top to bottom.
They have the generating function
 |
(6)
|
(Comtet 1974, p. 81).
Taking 
gives the central Delannoy numbers 
, which are the number of
"king walks" from the 
corner of an 
square to the upper right
corner 
. These are given by
 |
(7)
|
where 
is a Legendre polynomial (Moser 1955; Comtet
1974, p. 81; Vardi 1991). Another expression is
 |  |  |
(8)
|
 |  |  |
(9)
|
 |  |  |
(10)
|
where 
is a binomial coefficient and 
is a hypergeometric
function. These numbers have a surprising connection with the Cantor
set (E. W. Weisstein, Apr. 9, 2006).
For 
, they also satisfy the recurrence
equation
 |
(11)
|
with 
and 
.
They have generating function
 |  |  |
(12)
|
 |  |  |
(13)
|
The values of 
for 
, 2, ... are 3, 13, 63, 321, 1683, 8989, 48639, ...
(OEIS A001850). The numbers of decimal
digits in 
for 
, 1, ... are 1, 7, 76, 764, 7654, 76553, 765549, 7655510,
... (OEIS A114470). The ratios of these digit
counts to 
converge to 
(OEIS A104178).
The first few prime Delannoy numbers are 3, 13, 265729, ... (OEIS A092830), corresponding to indices 1, 2, 8, .... E. W. Weisstein (Feb. 28, 2006) reported no others in a search to index 7,834,059.
The Schröder numbers bear the same relation to the Delannoy numbers as the Catalan numbers do to the binomial coefficients.
Taking the upper triangular factor in the Cholesky decomposition of a finite principal square array of 
, transposing it,
and multiplying on the right by the diagonal
matrix 
of the same size gives the lower triangular
version of Pascal's triangle (G. Helms,
pers. comm., Aug. 29, 2005).
Beautiful fractal patterns can be obtained by plotting 
(mod 
) (E. Pegg, Jr., pers. comm., Aug. 29, 2005).
In particular, the 
case corresponds to a pattern resembling the Sierpiński
carpet.
with Diagonal Steps." Canad. Math. Bull. 10, 653-658, 1967.Vardi,
I.