Меню Главная Случайная статья Настройки Числа Деланнуа Материал из https://ru.wikipedia.org Числа Деланнуа[1] (или числа Деланоя[2]; фр. Delannoy) D(a, b) в комбинаторике описывают количества путей из левого нижнего угла прямоугольной решётки (a, b) в противоположный по диагонали угол, используя только ходы вверх, вправо или вверх-вправо («ходом короля»). В a-мерном клеточном автомате D(a,b) задают количество клеток в окрестности фон Неймана радиуса b, последовательность A008288 в OEIS; количество клеток на поверхности окрестности задет последовательность A266213 в OEIS. Названы в честь французского математика Анри Огюста Деланнуа[фр.][3]. Содержание 1 Некоторые значения 2 Свойства 3 См. также 4 Примечания 5 Ссылки Некоторые значения Для квадратной сетки 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 Свойства Числа Деланнуа удовлетворяют рекуррентному соотношению: ${\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): ${\displaystyle \ C(m,n)=C(m-1,n)+C(n-1,m)}$ которое относится к количеству путей между теми же вершинами, но при условии, что допустимы только ходы по сторонам клеток. Если учесть места, в которых пути пересекают диагональ, то можно вывести связь между числами Деланнуа и биномиальными коэффициентами[4]: ${\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)}$ Кроме того ${\displaystyle D(m,n)=\sum _{k=0}^{n}A(m,k),}$ где ${\displaystyle A(m,k)}$ задано последовательность A266213 в OEIS. Производящая функция для чисел: ${\displaystyle \sum _{p,q=0}^{\infty }D(p,q)x^{p}y^{q}={\frac {1}{1-x-y-xy}}}$ Когда рассматриваются пути в квадрате, числа Деланнуа равны: ${\displaystyle D(n)=D(n,n)=P_{n}(3)}$, где ${\displaystyle P_{n}(x)}$ — полином Лежандра. Другие свойства для них: ${\displaystyle D(n)={\frac {3(2n-1)D(n-1)-(n-1)D(n-2)}{n}}}$ ${\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 }$ См. также Числа Моцкина Числа Нараяны Числа Шрёдера Примечания Смирнов Е. Ю. Три взгляда на ацтекский бриллиант Архивная копия от 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 Ссылки Weisstein, Eric W. Delannoy Number (англ.) на сайте Wolfram MathWorld. Упоминание чисел Деланнуа в русскоязычной статье.