Числа Деланоя

Числа Делануа[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, оскільки в квадраті 3 × 3 існує 63 різних шляхи Делануа:

Шляхи, які не піднімаються вище від діагоналі, описують числа Шредера.

Числа Делануа утворюють нескінченну матрицю Делануа, частину якої наведено в таблиці:

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 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.

Твірна функція для чисел:

Коли розглядаються шляхи в квадраті, числа Делануа рівні:

, де  поліном Лежандра.

Інші їх властивості:

Примітки

  1. Смирнов Е. Ю. Три взгляда на ацтекский бриллиант
  2. Кохась К. Разбиение ацтекских диамантов и квадратов на домино
  3. 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.
  4. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.