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

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

 

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

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

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(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)$$\ C(m,n)=C(m-1,n)+C(n-1,m)$ 

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

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

$D(m,n)=\underset{k=0}{\overset{m}{\sum <!--\; \sum \; -->}}C(m,k)C(n+m-<!--\; -\; -->k,m)=\underset{k=0}{\overset{m}{\sum <!--\; \sum \; -->}}{2}^{k}C(m,k)C(n,k)$$\ 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)=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}A(m,k),$$D(m,n)=\sum _{k=0}^{n}A(m,k),$ 

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

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

$\underset{p,q=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}D(p,q)x^p{y}^q=\frac{1}{1-<!--\; -\; -->x-<!--\; -\; -->y-<!--\; -\; -->xy}$$\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)$$D(n)=D(n,n)=P_{n}(3)$ , где $P_n(x)$$P_n(x)$  — полином Лежандра.

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

$D(n)=\frac{3(2n-<!--\; -\; -->1)D(n-<!--\; -\; -->1)-<!--\; -\; -->(n-<!--\; -\; -->1)D(n-<!--\; -\; -->2)}{n}$$D(n)={\frac {3(2n-1)D(n-1)-(n-1)D(n-2)}{n}}$ 

$\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}D(n)x^n=\frac{1}{\sqrt{1-<!--\; -\; -->6x+x^2}}=1+3x+13x^2+63x^3+321x^4+\dots <!--\; \dots \; -->$$\sum _{n=0}^{\infty }D(n)x^{n}={\frac {1}{\sqrt {1-6x+x^{2}}}}=1+3x+13x^{2}+63x^{3}+321x^{4}+\ldots$ 

См. такжеПравить

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

СсылкиПравить

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