Числа ДеланнуаСмирнов Е. Ю. Три взгляда на ацтекский бриллиант (или числа ДеланояКохась К. Разбиение ацтекских диамантов и квадратов на домино ; ) D(a, b) в комбинаторике описывают количества путей из левого нижнего угла прямоугольной решётки (a, b) в противоположный по диагонали угол, используя только ходы вверх, вправо или вверх-вправо («ходом короля»). В a-мерном клеточном автомате D(a,b) задают количество клеток в окрестности фон Неймана радиуса b, ; количество клеток на поверхности окрестности задет . Названы в честь французского математика .
Некоторые значения Для квадратной сетки n × n первые числа Деланнуа (начиная с n=0) :
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):
которое относится к количеству путей между теми же вершинами, но при условии, что допустимы только ходы по сторонам клеток.
Если учесть места, в которых пути пересекают диагональ, то можно вывести связь между числами Деланнуа и биномиальными коэффициентами:
Кроме того
где задано .
Производящая функция для чисел:
Когда рассматриваются пути в квадрате, числа Деланнуа равны: , где — полином Лежандра. Другие свойства для них:
См. также Числа Моцкина Числа Нараяны Числа Шрёдера
Примечания
Ссылки
Упоминание чисел Деланнуа в русскоязычной статье.
Категория:Целочисленные последовательности