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

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

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


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

  1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, \ldots
  Например, D(3,3)=63, так как существует 63 различных пути Деланноя в квадрате 3 × 3:
 Пути, которые не поднимаются выше диагонали, описывают числа Шрёдера.
 Дополнительные значения приведены в таблице:
k\{n012345678910
01111111111
113579111315171921
2151325416185113145181221

Свойства


 Числа Деланноя удовлетворяют рекуррентному соотношению:  D(m,n)=D(m1,n)+D(m1,n1)+D(m,n1), в качестве начальных условий можно принять D(0,k)=D(k,0)=1.
 Это уравнение аналогично треугольнику Паскаля для биномиальных коэффициентов C(m,n):

 C(m,n)=C(m1,n)+C(n1,m)
  которое относится к количеству путей между теми же вершинами, но при условии, что допустимы только ходы по сторонам клеток.
 Если учесть места, в которых пути пересекают диагональ, то можно вывести связь между числами Деланноя и биномиальными коэффициентами:

 D(m,n)=k=0mC(m,k)C(n+mk,m)=k=0m2kC(m,k)C(n,m)
  Кроме того
D(m,n)=k=0nA(m,k),

 где A(m,k) задано .
 Производящая функция для чисел:

p,q=0D(p,q)xpyq=11xyxy
  Когда рассматриваются пути в квадрате, числа Деланноя равны:

D(n)=D(n,n)=Pn(3), где Pn(x) — полином Лежандра.
  Другие свойства для них:

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