격자 경로

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

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

정의

길이 $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}$이다.^:28

예

단위 벡터 보폭

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

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

${\binom {v_{1}+\cdots +v_{d}}{v_{1},\dots ,v_{n}}}={\frac {(v_{1}+\cdots v_{d})!}{v_{1}!\cdots v_{d}!}}$

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

${\binom {a+b}{a}}={\frac {(a+b)!}{a!b!}}$

이다.

다이크 경로

 이 부분의 본문은 다이크 경로입니다.

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

$C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}={\frac {(2n)!}{(n+1)!n!}}$

이다.

같이 보기

• 한붓그리기
• 모츠킨 수

외부 링크

• Weisstein, Eric Wolfgang. “Lattice path”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Point lattice”. 《Wolfram MathWorld》 (영어). Wolfram Research.