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

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

Число Деланного также подсчитывает количество глобальных выравниваний двух последовательностей длин и , ^[2] количество точек в m -мерной целочисленной решетке, которые находятся не более чем на n шагов от начала координат, ^[3] и, в клеточных автоматах , количество ячеек в m -мерной окрестности фон Неймана радиуса n ^{[4], в} то время как количество ячеек на поверхности m -мерной окрестности фон Неймана радиуса n задается с помощью (последовательность A266213${\ Displaystyle D (м, п)}$${\ displaystyle m}$${\ displaystyle n}$в OEIS ).

Пример [ править ]

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

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

Массив Деланного [ править ]

Массив Деланный является бесконечной матрицей из чисел Delannoy: ^[5]

м п	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

В этом массиве числа в первой строке равны единице, числа во второй строке - нечетные числа , числа в третьей строке - это центрированные квадратные числа , а числа в четвертой строке - центрированные октаэдрические числа . В качестве альтернативы, одни и те же номера могут быть расположены в виде треугольной решетки , напоминающей треугольник Паскаля , называемый также tribonacci треугольник , ^[6] , в которой каждое число является суммой трех чисел над ним:

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

Центральные номера Delannoy [ править ]

Эти цифры центрального Delannoy D ( п ) = D ( п , п ) являются числами для квадратного п × п сетки. Первые несколько центральных чисел Деланного (начиная с n = 0):

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

Вычисление [ править ]

Числа Деланного [ править ]

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

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

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

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

или бесконечной серией

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

А также

${\ Displaystyle D (т, п) = \ сумма _ {к = 0} ^ {п} А (м, к),}$

где задается с помощью (последовательность A266213 в OEIS ).${\ Displaystyle А (м, к)}$

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

${\ displaystyle 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 {иначе}} \ end {case}}}$

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

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

Центральные номера Delannoy [ править ]

Подстановка в первое выражение замкнутой формы выше, замена и небольшая алгебра дает${\displaystyle m=n}$${\displaystyle k\leftrightarrow n-k}$

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

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

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

Центральные числа Деланного также удовлетворяют трехчленным рекуррентным отношениям между собой ^[7].

${\displaystyle nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),}$

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

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

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

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

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

См. Также [ править ]

• Число Моцкина
• Число Нараяны

Ссылки [ править ]

Внешние ссылки [ править ]

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