Числа Деланнуа

Числа Деланнуа (или числа Деланоя; фр. 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:

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

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

Свойства

Числа Деланнуа удовлетворяют рекуррентному соотношению:   D ( m , n ) = D ( m − 1 , n ) + D ( m − 1 , n − 1 ) + D ( m , n − 1 ) {displaystyle 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 ) {displaystyle C(m,n)=C(m-1,n)+C(n-1,m)}

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

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

  D ( m , n ) = ∑ k = 0 m C ( m , k ) C ( n + m − k , m ) = ∑ k = 0 m 2 k C ( m , k ) C ( n , k ) {displaystyle 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,k)}

Кроме того

D ( m , n ) = ∑ k = 0 n A ( m , k ) , {displaystyle D(m,n)=sum _{k=0}^{n}A(m,k),}

где A ( m , k ) {displaystyle A(m,k)} задано последовательность A266213 в OEIS.

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

∑ p , q = 0 ∞ D ( p , q ) x p y q = 1 1 − x − y − x y {displaystyle sum _{p,q=0}^{infty }D(p,q)x^{p}y^{q}={frac {1}{1-x-y-xy}}}

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

D ( n ) = D ( n , n ) = P n ( 3 ) {displaystyle D(n)=D(n,n)=P_{n}(3)} , где P n ( x ) {displaystyle P_{n}(x)} — полином Лежандра.

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

D ( n ) = 3 ( 2 n − 1 ) D ( n − 1 ) − ( n − 1 ) D ( n − 2 ) n {displaystyle D(n)={frac {3(2n-1)D(n-1)-(n-1)D(n-2)}{n}}} ∑ n = 0 ∞ D ( n ) x n = 1 1 − 6 x + x 2 = 1 + 3 x + 13 x 2 + 63 x 3 + 321 x 4 + … {displaystyle sum _{n=0}^{infty }D(n)x^{n}={frac {1}{sqrt {1-6x+x^{2}}}}=1+3x+13x^{2}+63x^{3}+321x^{4}+ldots }