Delannoy number

Delannoy number

In mathematics, a Delannoy number D describes the number of 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.

D(m,n)=\begin{cases}1 &\text{if }m=0\text{ or }n=0\\D(m-1,n) + D(m-1,n-1) + D(m,n-1)&\text{else}\end{cases}

For an n × n grid, the first few Delannoy numbers (starting with n=0) are (sequence A001850 in OEIS):

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ...

The following figure illustrates the 63 Delannoy paths through a 3 × 3 grid:

Delannoy3x3.svg

The paths that do not rise above the SW–NE diagonal represent the Schröder numbers.

See also

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Delannoy, Jean — (1908 )    Actor, director, film editor, and screen writer. Jean Delannoy at first pursued a fairly traditional path and studied the classics at university. However, he took up acting while he was a student in Paris in the 1920s. He was one of… …   Guide to cinema

  • Delannoy, Jean — (1908 )    Actor, director, film editor, and screen writer. Jean Delannoy at first pursued a fairly traditional path and studied the classics at university. However, he took up acting while he was a student in Paris in the 1920s. He was one of… …   Historical Dictionary of French Cinema

  • Motzkin number — In mathematics, a Motzkin number for a given number n (named after Theodore Motzkin) is the number of different ways of drawing non intersecting chords on a circle between n points. The Motzkin numbers have very diverse applications in geometry,… …   Wikipedia

  • Narayana number — In combinatorics, the Narayana numbers N(n, k), n = 1, 2, 3 ..., 1 ≤ k ≤ n, form a triangular array of natural numbers, called Narayana triangle, that occur in various counting problems. They are named for T.V. Narayana… …   Wikipedia

  • Schröder number — In mathematics, a Schröder number describes the number of paths from the southwest corner (0, 0) of an n times; n grid to the northeast corner ( n , n ), using only single steps north, northeast, or east, that do not rise above the SW ndash;NE… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Domino tiling — of a square A domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge to edge. Equivalently, it is a matching in the grid graph formed by placing a… …   Wikipedia

  • Integer sequence prime — In mathematics, an integer sequence prime is a prime number found as a member of an integer sequence. For example, the 8th Delannoy number, 265729, is prime. A challenge in empirical mathematics is to identify large prime values in rapidly… …   Wikipedia

  • Числа Деланноя — (Delannoy) D(a, b) в комбинаторике описывают количества путей из левого нижнего угла прямоугольной решётки (a, b) в противоположный по диагонали угол, используя только ходы вверх, вправо или вверх вправо («ходом короля»). Содержание 1 Некоторые… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”