Named after | Henri–Auguste Delannoy |
---|---|
No. of known terms | infinity |
Formula | |
OEIS index |
|
In mathematics, a Delannoy number counts the paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m, n), using only single steps north, northeast, or east. The Delannoy numbers are named after French army officer and amateur mathematician Henri Delannoy. [1]
The Delannoy number also counts the global alignments of two sequences of lengths and , [2] the points in an m-dimensional integer lattice or cross polytope which are at most n steps from the origin, [3] and, in cellular automata, the cells in an m-dimensional von Neumann neighborhood of radius n. [4]
The Delannoy number D(3,3) equals 63. The following figure illustrates the 63 Delannoy paths from (0, 0) to (3, 3):
The subset of paths that do not rise above the SW–NE diagonal are counted by a related family of numbers, the Schröder numbers.
The Delannoy array is an infinite matrix of the Delannoy numbers: [5]
m n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 |
2 | 1 | 5 | 13 | 25 | 41 | 61 | 85 | 113 | 145 |
3 | 1 | 7 | 25 | 63 | 129 | 231 | 377 | 575 | 833 |
4 | 1 | 9 | 41 | 129 | 321 | 681 | 1289 | 2241 | 3649 |
5 | 1 | 11 | 61 | 231 | 681 | 1683 | 3653 | 7183 | 13073 |
6 | 1 | 13 | 85 | 377 | 1289 | 3653 | 8989 | 19825 | 40081 |
7 | 1 | 15 | 113 | 575 | 2241 | 7183 | 19825 | 48639 | 108545 |
8 | 1 | 17 | 145 | 833 | 3649 | 13073 | 40081 | 108545 | 265729 |
9 | 1 | 19 | 181 | 1159 | 5641 | 22363 | 75517 | 224143 | 598417 |
In this array, the numbers in the first row are all one, the numbers in the second row are the odd numbers, the numbers in the third row are the centered square numbers, and the numbers in the fourth row are the centered octahedral numbers. Alternatively, the same numbers can be arranged in a triangular array resembling Pascal's triangle, also called the tribonacci triangle, [6] in which each number is the sum of the three numbers above it:
1 1 1 1 3 1 1 5 5 1 1 7 13 7 1 1 9 25 25 9 1 1 11 41 63 41 11 1
The central Delannoy numbersD(n) = D(n,n) are the numbers for a square n×n grid. The first few central Delannoy numbers (starting with n=0) are:
For diagonal (i.e. northeast) steps, there must be steps in the direction and steps in the direction in order to reach the point ; as these steps can be performed in any order, the number of such paths is given by the multinomial coefficient . Hence, one gets the closed-form expression
An alternative expression is given by
or by the infinite series
And also
where is given with (sequence A266213 in the OEIS ).
The basic recurrence relation for the Delannoy numbers is easily seen to be
This recurrence relation also leads directly to the generating function
Substituting in the first closed form expression above, replacing , and a little algebra, gives
while the second expression above yields
The central Delannoy numbers satisfy also a three-term recurrence relationship among themselves, [7]
and have a generating function
The leading asymptotic behavior of the central Delannoy numbers is given by
where and .
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n; this coefficient can be computed by the multiplicative formula
In mathematics, the Bernoulli numbersBn are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.
In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the sequence begins
In mathematics, the Euler numbers are a sequence En of integers defined by the Taylor series expansion
In mathematics, a recurrence relation is an equation according to which the th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of ; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.
In mathematics, the Hermite polynomials are a classical orthogonal polynomial sequence.
In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.
In mathematics, the n-th harmonic number is the sum of the reciprocals of the first n natural numbers:
In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Catalan.
In mathematics, the nth Motzkin number is the number of different ways of drawing non-intersecting chords between n points on a circle. The Motzkin numbers are named after Theodore Motzkin and have diverse applications in geometry, combinatorics and number theory.
In mathematics the nth central binomial coefficient is the particular binomial coefficient
In mathematics, the plastic ratio is a geometrical proportion close to 53/40. Its true value is the real solution of the equation x3 = x + 1.
In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling.
In combinatorics, the Eulerian number is the number of permutations of the numbers 1 to in which exactly elements are greater than the previous element.
In mathematics, the Schröder number also called a large Schröder number or big Schröder number, describes the number of lattice paths from the southwest corner of an grid to the northeast corner using only single steps north, northeast, or east, that do not rise above the SW–NE diagonal.
In mathematics, the Perrin numbers are a doubly infinite constant-recursive integer sequence with characteristic equation x3 = x + 1. The Perrin numbers bear the same relationship to the Padovan sequence as the Lucas numbers do to the Fibonacci sequence.
A centered octahedral number or Haüy octahedral number is a figurate number that counts the points of a three-dimensional integer lattice that lie inside an octahedron centered at the origin. The same numbers are special cases of the Delannoy numbers, which count certain two-dimensional lattice paths. The Haüy octahedral numbers are named after René Just Haüy.
In mathematics, a Ramanujan–Sato series generalizes Ramanujan’s pi formulas such as,
Gregory coefficientsGn, also known as reciprocal logarithmic numbers, Bernoulli numbers of the second kind, or Cauchy numbers of the first kind, are the rational numbers that occur in the Maclaurin series expansion of the reciprocal logarithm