Interested Article - Числа Деланнуа

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

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

Для квадратной сетки n × n первые числа Деланнуа (начиная с n =0) последовательность в 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)

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

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

\ 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)=\sum _{k=0}^{n}A(m,k),

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

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

\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)

, где

P_{n}(x)

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

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

D(n)={\frac {3(2n-1)D(n-1)-(n-1)D(n-2)}{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

См. также

Примечания

Смирнов Е. Ю. от 31 июля 2018 на Wayback Machine
Кохась К.
Banderier, Cyril; Schwer, Sylviane (2005), "Why Delannoy numbers?", Journal of Statistical Planning and Inference , 135 (1): 40—54, arXiv : , doi :
Martin Aigner. . — Springer, 2007. — С. . — ISBN 978-3-540-39032-4 .

Ссылки

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