들라노이 수

들라노이 수

이름을 따서 명명됨	앙리-오귀스트 들라노이
No. 알려진.	무한의
공식	${\displaystyle D(m,n)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}{n}}{k}2}}^{k}}}}}}}}}}$
OEIS 지수	A008288 들라노이 정사각형 배열

수학에서 델라노이 번호 $D{\displaystyle }$ ${\displaystyle D}$은 직사각형 그리드의 남서쪽 코너(0, 0)에서 북동쪽 코너(m, n)로 가는 경로의 수를 설명하며$$, 북쪽, 북동쪽 또는 동쪽의 단발만 사용한다.들라노이 번호는 프랑스 육군 장교와 아마추어 수학자 앙리 들라노이(Henry Delannoy)의 이름을 따서 붙여졌다.^[1]

그 들라 누아 번호 D{D(m,n)\displaystyle}또한 길이 m{m\displaystyle}과 n{n\displaystyle}점의 origin,[3]에서 대부분의 n단계에서 세포, 세포의 수에 있는m-dimensional 정수 격자에서도 수 ,[2]의 두 시퀀스의 세계적인 맞춤의 수를 센다(m, n).한 m-반경 n의^[4] m-차원 폰 노이만 근방의 표면의 셀 수는 (OEIS의 순서 A266213)과 함께 주어진다.

예

델라노이 번호 D(3,3)는 63과 같다.다음 그림은 (0, 0)에서 (3, 3)까지의 63개의 델라노이 경로를 보여준다.

SW-NE 대각선 위로 올라가지 않는 경로의 하위 집합은 관련 숫자 계열인 슈뢰더 번호에 의해 계수된다.

들라노이 배열

Delannoy 배열은 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

이 배열에서 첫 번째 행의 숫자는 모두 1이고, 두 번째 행의 숫자는 홀수이며, 세 번째 행의 숫자는 중심 정사각형 숫자이고, 네 번째 행의 숫자는 중심 정사각형 숫자다.또는 파스칼의 삼각형을 닮은 삼각형 배열로 같은 숫자를 배열할 수 있는데, 트리보나치 삼각형이라고도 하며,^[6] 각 숫자는 그 위의 세 숫자의 합이다.

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

중앙 들라노이 수

중심 Delanoy 번호 D(n) = D(n,n)는 제곱 n × n 그리드에 대한 숫자다.처음 몇 개의 중앙 델라노이 번호(n=0으로 시작)는 다음과 같다.

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ...(OEIS에서 연속 A001850).

연산

들라노이 수

$k{\displaystyle }$ ${\displaystyle k}$ 대각선$$(즉, 북동쪽) 스텝의 경우$$, $m$ ,${\displaystyle n}$)에 $도달$하려면 ${\displaystyle x}$$${\$displaystyle x}$ ${\displaystyle \mathrm{방향}}$으로${\displaystyle }$m${\displaystyle }$-$$k {\$displaystyle$ $n-k$} 스텝이 있어야 $하며{\displaystyle }$, 이 스텝은 구멍일 수 있으므로 y ${\$$displaystystyle$$y}$ 방향으로$$ $n-k}$ 스텝이$$ 있어야 한다$.$med in any order, the number of such paths is given by the multinomial coefficient ${\displaystyle {\binom {m+n-k}{k,m-k,n-k}}={\binom {m+n-k}{m}}{\binom {m}{k}}}$. Hence, one gets the closed-form expression

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

다른 표현은 다음에 의해 주어진다.

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

또는 무한 시리즈로

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

그리고 또한

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

여기서 $A{\displaystyle }$( ${\displaystyle m}$, ${\displaystyle k}$) ${\displaystyle A(m,k)}$은(OEIS에서 순서 A266213)와 함께 주어진다$$.

델라노이 숫자의 기본적인 재발관계는 쉽게 알 수 있다.

${\displaystyle D(m,n)={\begin{case}1&{\text}{{}m=0{\text{}또는 }n=0\\\D(m-1,n-1)+D(m-1,n-1)+D(m,n-1)+D(m,{\text{otherwise}}}:{case}}}}}}}}}}}}}}}}}}}}:{case}}}}}}}}}}}$

이러한 재발 관계는 발생 함수로 직접 연결되기도 한다.

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

중앙 들라노이 수

$위$의 첫 번째 닫힌 형태 표현에서$$ m${\displaystyle }$= ${\displaystyle n}$ ${\displaystyle$m=$n}$을(를) $대체$하고, ${\displaystyle \mathrm{k파운드}}$n${\displaystyle }$- ${\displaystyle k}${\$displaystyle k\좌우타로우 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}^{k}.}$

중앙 델라노이 수치는 그들 사이의 3개월의 재발 관계도 만족시킨다.^[7]

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

그리고 생성기능이 있다.

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

중앙 들라노이 숫자의 대표적인 무증상 행동은 다음과 같다.

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

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

참고 항목

• 모츠킨 수
• 나라야나 수

참조

외부 링크

• Weisstein, Eric W. "Delannoy Number". MathWorld.