Delannoyovo číslo - Delannoy number - Wikipedia

v matematika, a Delannoyovo číslo ${ displaystyle D}$ popisuje počet cest od jihozápadního rohu (0, 0) obdélníkové mřížky k severovýchodnímu rohu (m, n), používající pouze jednotlivé kroky na sever, severovýchod nebo východ. Čísla Delannoy jsou pojmenována podle důstojníka francouzské armády a amatérského matematika Henri Delannoy.^[1]

Číslo Delannoy ${ displaystyle D (m, n)}$ také počítá počet globální zarovnání dvou sekvencí délek ${ displaystyle m}$ a ${ displaystyle n}$,^[2] počet bodů v an m-dimenzionální celočíselná mřížka to jsou nanejvýš n kroky od počátku,^[3] a v mobilní automaty, počet buněk v m-dimenzionální sousedství von Neumann poloměru n^[4] zatímco počet buněk na povrchu an m-dimenzionální sousedství von Neumann poloměru n je uveden s (sekvence A266213 v OEIS ).

Příklad

Číslo Delannoy D(3,3) se rovná 63. Následující obrázek ilustruje 63 cest Delannoy od (0, 0) do (3, 3):

Podmnožina cest, které nevyčnívají nad SW – NE úhlopříčku, se počítá podle příbuzné řady čísel, Schröderova čísla.

Delannoyovo pole

The Delannoyovo pole je nekonečná matice z čísel Delannoy:^[5]

m n	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

V tomto poli jsou čísla v prvním řádku všechna jedna, čísla v druhém řádku jsou lichá čísla, čísla ve třetím řádku jsou na střed čtvercová čísla a čísla ve čtvrtém řádku jsou na střed oktaedrická čísla. Alternativně mohou být stejná čísla uspořádána v a trojúhelníkové pole připomínající Pascalův trojúhelník, také nazývaný tribonacciho trojúhelník,^[6] ve kterém každé číslo je součtem tří čísel nad ním:

            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

Centrální čísla Delannoy

The centrální čísla Delannoy D(n) = D(n,n) jsou čísla čtverce n × n mřížka. Prvních několik centrálních čísel Delannoy (počínaje n= 0) jsou:

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ... (sekvence A001850 v OEIS ).

Výpočet

Delannoyova čísla

Pro ${ displaystyle k}$ diagonální (tj. severovýchodní) schody, tam musí být ${ displaystyle m-k}$ kroky v ${ displaystyle x}$ směr a ${ displaystyle n-k}$ kroky v ${ displaystyle y}$ směrem k dosažení bodu ${ displaystyle (m, n)}$; protože tyto kroky lze provádět v jakémkoli pořadí, počet těchto cest je dán parametrem multinomický koeficient${ displaystyle { binom {m + n-k} {k, m-k, n-k}} = { binom {m + n-k} {m}} { binom {m} {k}}}$. Jeden tedy získá výraz uzavřené formy

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

Alternativní výraz je dán vztahem

${ displaystyle D (m, n) = součet _ {k = 0} ^ { min (m, n)} { binom {m} {k}} { binom {n} {k}} 2 ^ {k}}$

nebo nekonečnou řadou

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

A také

${ displaystyle D (m, n) = součet _ {k = 0} ^ {n} A (m, k),}$

kde ${ displaystyle A (m, k)}$ je uveden s (sekvence A266213 v OEIS ).

Základní relace opakování protože čísla Delannoy jsou snadno viditelná

${ displaystyle D (m, n) = { začátek {případů} 1 & { text {if}} m = 0 { text {nebo}} n = 0 D (m-1, n) + D ( m-1, n-1) + D (m, n-1) & { text {jinak}} end {případy}}}$

Tato relace opakování také vede přímo k generující funkce

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

Centrální čísla Delannoy

Střídání ${ displaystyle m = n}$ v prvním uzavřeném výrazu výše, nahrazení ${ displaystyle k leftrightarrow n-k}$, a trochu algebra, dává

${ displaystyle D (n) = součet _ {k = 0} ^ {n} { binom {n} {k}} { binom {n + k} {k}},}$

zatímco druhý výraz výše dává

${ displaystyle D (n) = součet _ {k = 0} ^ {n} { binom {n} {k}} ^ {2} 2 ^ {k}.}$

Centrální čísla Delannoy uspokojují i ​​třídobý vztah opakování mezi sebou,^[7]

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

a mají generující funkci

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

Přední asymptotické chování centrálních čísel Delannoy je dáno vztahem

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

kde ${ displaystyle alpha = 3 + 2 { sqrt {2}} přibližně 5,828}$a ${ displaystyle c = (4 pi (3 { sqrt {2}} - 4)) ^ {- 1/2} přibližně 0,5727}$.

Viz také

• Motzkinovo číslo
• Narayana číslo

Reference

externí odkazy

• Weisstein, Eric W. „Delannoyovo číslo“. MathWorld.