격자 경로

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

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

정의

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

예

단위 벡터 보폭

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

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

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

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

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

이다.

다이크 경로

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

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

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

이다.

같이 보기

• 한붓그리기
• 모츠킨 수