격자 경로

길이 5, 보폭 (1, 1), (2, 0), (0, -1)의 격자 경로

조합론에서, 격자 경로(틀:Llang)는 주어진 범위의 보폭을 유지하며 걸어 얻는 경로이다.

정의

길이 $n$, 보폭 $S\subseteq {\mathbb{Z}}^d$의 격자 경로는 $v_i-v_{i-1}\in S$ ($i=1,\dots ,n$)를 만족시키는 점렬 $\{v^{(0)},v^{(1)},\dots ,v^{(n)}\}\subset {\mathbb{Z}}^d$이다.틀:Rp

예

단위 벡터 보폭

격자를 따라 동쪽 또는 남쪽으로만 걸어 (0, 0)부터 (2, 3)까지 가는 경로의 수는 조합의 수(이항 계수) $(\genfrac{}{}{0ex}{}{5}{2})=10$과 같다. 다른 점도 이와 같은 수를 계산하여 그 점의 위치에 적으면 파스칼의 삼각형을 얻는다.

원점과 점 $v\in {\mathbb{Z}}^d$ 사이, 단위 벡터들 $\{e^{(1)},\dots ,e^{(d)}\}$를 보폭으로 하는 격자 경로의 수는 다항 계수

$(\genfrac{}{}{0ex}{}{v_1+\cdots +v_d}{v_1,\dots ,v_n})=\frac{(v_1+\cdots v_d)!}{v_1!\cdots v_d!}$

이다.틀:Rp 특히, 원점과 점 $(a,b)\in {\mathbb{Z}}^2$ 사이, $\{(1,0),(0,1)\}$을 보폭으로 하는 격자 경로의 수는 이항 계수

$(\genfrac{}{}{0ex}{}{a+b}{a})=\frac{(a+b)!}{a!b!}$

이다.

다이크 경로

틀:본문 다이크 경로(틀:Llang)는 원점과 점 $(0,2n)$ 사이, $\{(1,1),(1,-1)\}$을 보폭으로 하는 격자 경로로 간주하거나, 원점과 점 $(n,n)$ 사이의 단위 벡터 보폭의 격자 경로 가운데, 대각선 $y=x$ 위를 지나지 않는 경우로 간주할 수 있다. 다이크 경로의 수는 카탈랑 수

$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!}$

이다.

같이 보기

• 한붓그리기
• 모츠킨 수

외부 링크

• 틀:매스월드
• 틀:매스월드