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

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

Назван в честь	Анри-Огюст Делануа
Количество известных терминов	бесконечность
Формула	$D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}2^{k}$
ОЭИС Индекс	А008288 Квадратный массив Деланной

В математике число Деланнуа $D$ подсчитывает пути от юго-западного угла (0, 0) прямоугольной сетки до северо-восточного угла ( m , n ), используя только отдельные шаги на север, северо-восток или восток. Числа Деланнуа названы в честь офицера французской армии и математика-любителя Анри Делануа .

Число Деланной $D(m,n)$ также подсчитывает глобальные выравнивания двух последовательностей длин $m$ и $n$, точки в m -мерной целочисленной решетке или перекрестном многограннике , которые находятся не более чем на n шагах от начала координат, а в клеточных автоматах — клетки в m -мерной окрестности фон Неймана радиуса n .

Пример

Число Деланной D (3,3) равно 63. На следующем рисунке показаны 63 пути Деланной от (0, 0) до (3, 3):

Подмножество путей, которые не поднимаются выше диагонали ЮЗ-СВ, учитываются соответствующим семейством чисел, числами Шредера .

Delannoy array

Массив Деланной представляет собой бесконечную матрицу чисел Деланного:

м н	0	1	2	3	4	5	6	7	8
0	1	1	1	1	1	1	1	1	1
1	1	3	5	7	9	11	13	15	17
2	1	5	13	25	41	61	85	113	145
3	1	7	25	63	129	231	377	575	833
4	1	9	41	129	321	681	1289	2241	3649
5	1	11	61	231	681	1683	3653	7183	13073
6	1	13	85	377	1289	3653	8989	19825	40081
7	1	15	113	575	2241	7183	19825	48639	108545
8	1	17	145	833	3649	13073	40081	108545	265729
9	1	19	181	1159	5641	22363	75517	224143	598417

В этом массиве все числа в первой строке равны единице, числа во второй строке — это нечетные числа , числа в третьей строке — это центрированные квадратные числа , а числа в четвертой строке — это центрированные октаэдрические числа . Альтернативно, те же числа можно расположить в треугольном массиве, напоминающем треугольник Паскаля , также называемый треугольником Трибоначчи , в котором каждое число представляет собой сумму трех чисел, стоящих над ним:

            1
          1   1
        1   3   1
      1   5   5   1
    1   7  13   7   1
  1   9  25  25   9   1
1  11  41  63  41  11   1

Центрального

Центральные числа Деланной D ( n ) = D ( n , n ) — это числа для квадратной сетки n × n . Первые несколько центральных чисел Деланной (начиная с n = 0):

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ... (последовательность A001850 в OEIS ).

Вычисление

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

Для $k$ диагональные (т.е. северо-восточные) ступеньки, должны быть $m-k$ шаги в $x$ направление и $n-k$ шаги в $y$ направление, чтобы добраться до точки $(m,n)$; поскольку эти шаги могут выполняться в любом порядке, количество таких путей определяется полиномиальным коэффициентом ${\binom {m+n-k}{k,m-k,n-k}}={\binom {m+n-k}{m}}{\binom {m}{k}}$. Следовательно, получаем выражение в замкнутой форме

$D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m+n-k}{m}}{\binom {m}{k}}.$

Альтернативное выражение дается выражением

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

или бесконечным рядом

$D(m,n)=\sum _{k=0}^{\infty }{\frac {1}{2^{k+1}}}{\binom {k}{n}}{\binom {k}{m}}.$

А также

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

где $A(m,k)$ задается (последовательность A266213 в OEIS ).

Легко видеть, что основное рекуррентное соотношение для чисел Деланнуа имеет вид

$D(m,n)={\begin{cases}1&{\text{if }}m=0{\text{ or }}n=0\\D(m-1,n)+D(m-1,n-1)+D(m,n-1)&{\text{otherwise}}\end{cases}}$

Это рекуррентное соотношение также приводит непосредственно к производящей функции

$\sum _{m,n=0}^{\infty }D(m,n)x^{m}y^{n}=(1-x-y-xy)^{-1}.$

Центрального

Замена $m=n$ в первом выражении закрытой формы выше, заменив $k\leftrightarrow n-k$и немного алгебры дает

$D(n)=\sum _{k=0}^{n}{\binom {n}{k}}{\binom {n+k}{k}},$

в то время как второе выражение выше дает

$D(n)=\sum _{k=0}^{n}{\binom {n}{k}}^{2}2^{k}.$

Центральные числа Деланнуа также удовлетворяют трехчленному рекуррентному соотношению между собой:

$nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),$

и имеют производящую функцию

$\sum _{n=0}^{\infty }D(n)x^{n}=(1-6x+x^{2})^{-1/2}.$

Ведущая асимптотика центральных чисел Деланнуа определяется выражением

$D(n)={\frac {c\,\alpha ^{n}}{\sqrt {n}}}\,(1+O(n^{-1}))$

где $\alpha =3+2{\sqrt {2}}\approx 5.828$ и $c=(4\pi (3{\sqrt {2}}-4))^{-1/2}\approx 0.5727$.

См. также

• Число Моцкина
• Число Нараяны
• Число Шредера-Гиппарха
• Число Шредера

Внешние ссылки

• Вайсштейн, Эрик В. «Число Деланной» . Математический мир .