Числа Деланноя

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

Некоторые значения

Для квадратной сетки n × n первые числа Деланноя (начиная с n=0) последовательность A001850 в OEIS:

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

Например, D(3,3)=63, так как существует 63 различных пути Деланноя в квадрате 3 × 3:

Пути, которые не поднимаются выше диагонали, описывают числа Шрёдера.

Дополнительные значения приведены в таблице:

k\n	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1
1	1	3	5	7	9	11	13	15	17	19	21
2	1	5	13	25	41	61	85	113	145	181	221

Свойства

Числа Деланноя удовлетворяют рекуррентному соотношению: $\ D(m,n)=D(m-1,n) + D(m-1,n-1) + D(m,n-1)$, в качестве начальных условий можно принять D(0,k)=D(k,0)=1.

Это уравнение аналогично треугольнику Паскаля для биномиальных коэффициентов C(m,n):

$\ C(m,n) = C(m-1,n)+C(n-1,m)$

которое относится к количеству путей между теми же вершинами, но при условии, что допустимы только ходы по сторонам клеток.

Если учесть места, в которых пути пересекают диагональ, то можно вывести связь между числами Деланноя и биномиальными коэффициентами^[1]:

$\ D(m,n)=\sum_{k=0}^m C(m,k)C(n+m-k,m)=\sum_{k=0}^m 2^k C(m,k)C(n,m)$

Производящая функция для чисел:

$\sum_{p,q=1}^\infty D(p,q)x^p y^q = \frac{1}{1-x-y-x y}$

Когда рассматриваются пути в квадрате, числа Деланноя равны:

$D(n)=D(n,n)=P_n(3)$, где $P_n(x)$ — полином Лежандра.

Другие свойства для них:

$D(n)=\frac{3(2n-1)D(n-1)-(n-1)D(n-2)}{n}$

$\sum_{n=1}^\infty D(n)x^n = \frac{1}\sqrt{1-6x+x^2}=1+3x+13x^2+63x^3+321x^4+\ldots$

См. также

• Числа Моцкина
• Числа Нараяны
• Числа Шрёдера

Ссылки

1. ↑ Martin Aigner A course in enumeration. — Springer, 2007. — С. 19. — ISBN 978-3-540-39032-4

• Weisstein, Eric W. Delannoy Number (англ.) на сайте Wolfram MathWorld.
• Richard P. Stanley Enumerative Combinatorics. — Cambridge University Press, 1999. — Т. 2. — С. 185. — ISBN 0-521-56069-1
• Упоминание чисел Деланноя в русскоязычной статье.