Delannoy
Delannoy numbers are a mathematical concept concerning paths on a rectangular grid. Named after French army officer and amateur mathematician Henri Delannoy, the Delannoy number D(m,n) counts the number of paths from the point (0,0) to the point (m,n) in a grid, using only steps that move either one unit north, one unit east, or one unit northeast (i.e., steps (0,1), (1,0), and (1,1)).
Properties and Calculation:
-
The Delannoy number D(m,n) can be calculated using a recurrence relation:
- D(m,n) = D(m-1, n) + D(m, n-1) + D(m-1, n-1)
-
The base cases for the recurrence are:
- D(0,n) = 1 for all non-negative integers n.
- D(m,0) = 1 for all non-negative integers m.
-
An explicit formula for D(m,n) is given by:
- D(m,n) = Σk=0min(m,n) (mCk) (nCk) 2k
where (mCk) and (nCk) represent binomial coefficients.
Centered Delannoy Numbers:
A related sequence is the centered Delannoy numbers. The nth centered Delannoy number is defined as D(n,n). These numbers represent the total number of paths from (0,0) to (n,n) using the same allowed steps (north, east, and northeast). The first few centered Delannoy numbers are 1, 3, 13, 63, 321, 1683, 8989, 48639, ...
Applications:
Delannoy numbers appear in various combinatorial problems, including:
- Counting paths in lattices.
- Analyzing certain types of grid graphs.
- Enumerating certain types of lattice animals.
- Problems related to voting theory and game theory.