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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Некоторые значения[править | править вики-текст]

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

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

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

Delannoy3x3.svg

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

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

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(0,k)=D(k,0)=1.

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

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

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

Кроме того

где задано последовательность A266213 в OEIS.

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

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

, где  — полином Лежандра.

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

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