Число Деланного - Delannoy number

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

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

Пример

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

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

Массив Деланного

В Массив Деланного является бесконечная матрица чисел Деланного:^[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

В этом массиве все числа в первой строке равны единице, числа во второй строке - это нечетные числа, числа в третьей строке - это центрированные квадратные числа, а числа в четвертой строке - это центрированные октаэдрические числа. В качестве альтернативы те же числа могут быть расположены в треугольная решетка напоминающий Треугольник Паскаля, также называемый треугольник трибоначчи,^[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

Центральные номера Деланного

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

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

Вычисление

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

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

${\displaystyle D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m+n-k}{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(m,n)=\sum _{k=0}^{n}A(m,k),}$

куда ${\displaystyle A(m,k)}$ дается с (последовательность A266213 в OEIS ).

Базовый отношение повторения ведь числа Деланного легко увидеть

${\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{otherwise}}\end{cases}}}$

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

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

Центральные номера Деланного

Подстановка ${\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}$.

Смотрите также

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

Рекомендации

1. Бандерье, Кирилл; Швер, Сильвиан (2005), «Почему числа Деланного?», Журнал статистического планирования и вывода, 135 (1): 40–54, arXiv:математика / 0411128, Дои:10.1016 / j.jspi.2005.02.004
2. Ковингтон, Майкл А. (2004), «Количество различных выравниваний двух струн», Журнал количественной лингвистики, 11 (3): 173–182, Дои:10.1080/0929617042000314921
3. Лютер, Себастьян; Мертенс, Стефан (2011), «Подсчет решетчатых животных в больших измерениях», Журнал статистической механики: теория и эксперимент, 2011 (9): P09026, arXiv:1106.1078, Bibcode:2011JSMTE..09..026L, Дои:10.1088 / 1742-5468 / 2011/09 / P09026
4. Breukelaar, R .; Bäck, Th. (2005), «Использование генетического алгоритма для развития поведения в многомерных клеточных автоматах: появление поведения», Материалы 7-й ежегодной конференции по генетическим и эволюционным вычислениям (GECCO '05), Нью-Йорк, Нью-Йорк, США: ACM, стр. 107–114, Дои:10.1145/1068009.1068024, ISBN  1-59593-010-8
5. Суланке, Роберт А. (2003), «Объекты, считанные центральными числами Деланного» (PDF), Журнал целочисленных последовательностей, 6 (1): Статья 03.1.5, МИСТЕР  1971435
6. Слоан, Н. Дж. А. (ред.). «Последовательность A008288 (квадратный массив чисел Деланного D (i, j) (i> = 0, j> = 0), считанный антидиагоналями)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
7. Пирт, Пол; Воан, Вэнь-Цзинь (2002). «Биективное доказательство рецидива Деланного». Congressus Numerantium. 158: 29–33. ISSN  0384-9864. Zbl  1030.05003.

внешняя ссылка

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