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

Числа Делануа або числа Деланоя (Шаблон:Lang-fr) D (a, b) в комбінаториці описують кількості шляхів з лівого нижнього кута прямокутної решітки (a, b) в протилежний по діагоналі кут, використовуючи тільки ходи вгору, вправо або вгору-вправо («ходом короля»). В a-вимірному клітинному автоматі D (a, b) задають кількість клітинок в околиці фон Неймана радіусом b (Шаблон:OEIS); кількість клітинок на поверхні околиці задає Шаблон:OEIS. Названі на честь французького математика Шаблон:Нп.

Деякі значення

Для квадратної сітки n×n перші числа Делануа (починаючи з n=0) (Шаблон: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(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):

$C(m,n)=C(m-1,n)+C(n-1,m)$

яке стосується кількості шляхів між тими ж вершинами, але за умови, що допустимі тільки ходи по сторонам клітин.Шаблон:Прояснити

Якщо врахувати місця, в яких шляхи перетинають діагональ, то можна вивести зв'язок між числами Делануа і біноміальними коефіцієнтами :

$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)$

$D(m,n)=\sum _{k=0}^{n}A(m,k),$

де $A(m,k)$ позначено Шаблон:OEIS.

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

$\sum _{p,q=0}^{\mathrm{\infty }}D(p,q)x^p{y}^q=\frac{1}{1-x-y-xy}$

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

$D(n)=D(n,n)=P_n(3)$, де $P_n(x)$ — поліном Лежандра.

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

$D(n)=\frac{3(2n-1)D(n-1)-(n-1)D(n-2)}{n}$

$\sum _{n=0}^{\mathrm{\infty }}D(n)x^n=\frac{1}{\sqrt{1-6x+x^2}}=1+3x+13x^2+63x^3+321x^4+\dots$

Див. також

• Число Моцкіна
• Число Нараяни
• Числа Шредера

Посилання

• Шаблон:MathWorld
• Шаблон:Книга-ру