Числа Деланнуа

Введение

Числа Деланнуа представляют собой особый набор чисел, встречающихся в комбинаторике. Они описывают количество различных путей, которые можно проложить от одного угла прямоугольной сетки до противоположного, двигаясь только вправо, вверх или по диагонали вверх-вправо. Эти числа находят приложения в теории решеток и имеют интересные связи с биномиальными коэффициентами.

Операция

Числа Деланнуа $D(m, n)$ для сетки размером $m \times n$ можно вычислить с помощью рекуррентной формулы:

D(m, n) = D(m-1, n) + D(m, n-1) + D(m-1, n-1)

где начальные условия заданы как:

D(0, 0) = 1

При этом числа Деланнуа можно выразить через сумму биномиальных коэффициентов:

D(m, n) = \sum_{k=0}^{\min(m, n)} \binom{m}{k} \binom{n}{k} 2^k

Свойства

Симметричность: Числа Деланнуа обладают симметрией: $D(m, n) = D(n, m)$ .
Частные случаи: Для $m = 1$ или $n = 1$ , числа Деланнуа совпадают с числами Фибоначчи.
Связь с биномиальными коэффициентами: Эти числа можно выразить через биномиальные коэффициенты, что дает возможность применять их в различных комбинаторных задачах.

Примеры использования

Пример 1

Рассмотрим решетку размером $2 \times 2$ . Найдем число путей от нижнего левого угла до верхнего правого угла:

\begin{equation*} \begin{aligned} D(2, 2) &= \sum_{k=0}^{2} \binom{2}{k} \binom{2}{k} 2^k \\&= \binom{2}{0} \binom{2}{0} 2^0 + \binom{2}{1} \binom{2}{1} 2^1 + \binom{2}{2} \binom{2}{2} 2^2 \\&= 1 + 4 + 4 = 9 \end{aligned} \end{equation*}

Таким образом, существует 9 различных путей.

Пример 2

Найдем число Деланнуа для прямоугольной решетки размером $3 \times 2$ :

\begin{equation*} \begin{aligned} D(3, 2) &= \sum_{k=0}^{2} \binom{3}{k} \binom{2}{k} 2^k \\ &= \binom{3}{0} \binom{2}{0} 2^0 + \binom{3}{1} \binom{2}{1} 2^1 + \binom{3}{2} \binom{2}{2} 2^2 \\ &= 1 + 6 + 6 = 13 \end{aligned} \end{equation*}

Таким образом, существует 13 различных путей по данной решетке.

Часто задаваемые вопросы (FAQ)

Что такое число Деланнуа?
- Это комбинаторное число, показывающее количество путей от одного угла сетки до противоположного, при движении вправо, вверх или по диагонали.
Как числа Деланнуа связаны с биномиальными коэффициентами?
- Они могут быть выражены через сумму произведений биномиальных коэффициентов и степеней двойки.

Примеры из жизни

Комбинаторика: Числа Деланнуа используются для решения задач о подсчете путей на сетке, имея важное значение в теории вероятностей.
Квантовая механика: Эти числа появляются в вычислениях, связанных с переходами частиц в решетках физических систем.
Компьютерные науки: Используются для определения возможных путей обхода сеток и решеток в алгоритмах машинного обучения и компьютерного зрения.

Ссылки на литературу и ресурсы

Учебники и литература:
Онлайн курсы: