격자 경로

길이 ${\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

원점과 점 ${\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!}}}$ 

이다.

• 한붓그리기
• 모츠킨 수

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