Числа ДелануаСмирнов Е. Ю. Три взгляда на ацтекский бриллиант або числа ДеланояКохась К. Разбиение ацтекских диамантов и квадратов на домино () 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, оскільки в квадраті 3 × 3 існує 63 різних шляхи Делануа:
Шляхи, які не піднімаються вище від діагоналі, описують .
Числа Делануа утворюють нескінченну матрицю Делануа, частину якої наведено в таблиці: k\n0123456789100111111111111135791113151719212151325416185113145181221
Властивості Числа Делануа задовольняють рекурентному співвідношенню: , за початкові умови можна взяти D (0, k) = D (k, 0) = 1.
Це рівняння аналогічне трикутнику Паскаля для біноміальних коефіцієнтів C(m, n):
яке стосується кількості шляхів між тими ж вершинами, але за умови, що допустимі тільки ходи по сторонам клітин.
Якщо врахувати місця, в яких шляхи перетинають діагональ, то можна вивести зв'язок між числами Делануа і біноміальними коефіцієнтами :
де позначено .
Твірна функція для чисел:
Коли розглядаються шляхи в квадраті, числа Делануа рівні:
, де — поліном Лежандра.
Інші їх властивості:
Примітки
Див. також Число Моцкіна Число Нараяни Числа Шредера
Посилання