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

Для квадратної сітки n×n перші числа Делануа (починаючи з n=0) (послідовність A001850 з Онлайн енциклопедії послідовностей цілих чисел, OEIS):

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, …

Наприклад, D (3,3) = 63, оскільки в квадраті 3 × 3 існує 63 різних шляхи Делануа:

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

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

Числа Делануа задовольняють рекурентному співвідношенню: ${\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 }$

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

• Weisstein, Eric W. Delannoy Number(англ.) на сайті Wolfram MathWorld.
• Richard P. Stanley. Enumerative Combinatorics. — Cambridge University Press, 1999. — Т. 2. — С. 185. — ISBN 0-521-56069-1.