Числа Деланнуа
Числа Деланнуа[1] (или числа Деланоя[2]; фр. Delannoy) D(a, b) в комбинаторике описывают количества путей из левого нижнего угла прямоугольной решётки (a, b) в противоположный по диагонали угол, используя только ходы вверх, вправо или вверх-вправо («ходом короля»). В a-мерном клеточном автомате D(a,b) задают количество клеток в окрестности фон Неймана радиуса b, последовательность A008288 в OEIS; количество клеток на поверхности окрестности задет последовательность A266213 в OEIS. Названы в честь французского математика Анри Огюста Деланнуа[фр.][3].
Некоторые значения
Для квадратной сетки 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(0,k)=D(k,0)=1.
Это уравнение аналогично треугольнику Паскаля для биномиальных коэффициентов C(m,n):
которое относится к количеству путей между теми же вершинами, но при условии, что допустимы только ходы по сторонам клеток.
Если учесть места, в которых пути пересекают диагональ, то можно вывести связь между числами Деланнуа и биномиальными коэффициентами[4]:
Кроме того
где задано последовательность A266213 в OEIS.
Производящая функция для чисел:
Когда рассматриваются пути в квадрате, числа Деланнуа равны:
- , где — полином Лежандра.
Другие свойства для них:
См. также
- Числа Моцкина
- Числа Нараяны
- Числа Шрёдера
Примечания
- ↑ Смирнов Е. Ю. Три взгляда на ацтекский бриллиант Архивная копия от 31 июля 2018 на Wayback Machine
- ↑ Кохась К. Разбиение ацтекских диамантов и квадратов на домино
- ↑ Banderier, Cyril; Schwer, Sylviane (2005), "Why Delannoy numbers?", Journal of Statistical Planning and Inference, 135 (1): 40—54, arXiv:math/0411128, doi:10.1016/j.jspi.2005.02.004
- ↑ Martin Aigner. A course in enumeration. — Springer, 2007. — С. 19. — ISBN 978-3-540-39032-4.
Ссылки
- Weisstein, Eric W. Delannoy Number (англ.) на сайте Wolfram MathWorld.
- Richard P. Stanley. Enumerative Combinatorics. — Cambridge University Press, 1999. — Т. 2. — С. 185. — ISBN 0-521-56069-1.
- Упоминание чисел Деланнуа в русскоязычной статье.