Русская Википедия:Числа Деланнуа
Числа Деланнуа[1] (или числа Деланоя[2]; Шаблон:Lang-fr) D(a, b) в комбинаторике описывают количества путей из левого нижнего угла прямоугольной решётки (a, b) в противоположный по диагонали угол, используя только ходы вверх, вправо или вверх-вправо («ходом короля»). В a-мерном клеточном автомате D(a,b) задают количество клеток в окрестности фон Неймана радиуса b, Шаблон:OEIS; количество клеток на поверхности окрестности задет Шаблон:OEIS. Названы в честь французского математика Шаблон:Нп3[3].
Некоторые значения
Для квадратной сетки 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 |
Свойства
Числа Деланнуа удовлетворяют рекуррентному соотношению: <math>\ D(m,n)=D(m-1,n) + D(m-1,n-1) + D(m,n-1)</math>, в качестве начальных условий можно принять D(0,k)=D(k,0)=1.
Это уравнение аналогично треугольнику Паскаля для биномиальных коэффициентов C(m,n):
- <math>\ C(m,n) = C(m-1,n)+C(n-1,m)</math>
которое относится к количеству путей между теми же вершинами, но при условии, что допустимы только ходы по сторонам клеток.
Если учесть места, в которых пути пересекают диагональ, то можно вывести связь между числами Деланнуа и биномиальными коэффициентами[4]:
- <math>\ 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)</math>
Кроме того
- <math> D(m,n) = \sum_{k=0}^{n} A(m,k), </math>
где <math> A(m,k) </math> задано Шаблон:OEIS.
Производящая функция для чисел:
- <math>\sum_{p,q=0}^\infty D(p,q)x^p y^q = \frac{1}{1-x-y-x y}</math>
Когда рассматриваются пути в квадрате, числа Деланнуа равны:
- <math>D(n)=D(n,n)=P_n(3)</math>, где <math>P_n(x)</math> — полином Лежандра.
Другие свойства для них:
- <math>D(n)=\frac{3(2n-1)D(n-1)-(n-1)D(n-2)}{n}</math>
- <math>\sum_{n=0}^\infty D(n)x^n = \frac{1}\sqrt{1-6x+x^2}=1+3x+13x^2+63x^3+321x^4+\ldots</math>
См. также
Примечания
Ссылки
- Шаблон:MathWorld
- Шаблон:Книга
- Упоминание чисел Деланнуа в русскоязычной статье.
- ↑ Смирнов Е. Ю. Три взгляда на ацтекский бриллиант
- ↑ Кохась К. Разбиение ацтекских диамантов и квадратов на домино
- ↑ Шаблон:Citation
- ↑ Шаблон:Книга