길이 5, 보폭 (1, 1), (2, 0), (0, -1)의 격자 경로
조합론에서, 격자 경로(영어: lattice path)는 주어진 범위의 보폭을 유지하며 걸어 얻는 경로이다.
길이
, 보폭
의 격자 경로는
(
)를 만족시키는 점렬
이다.[1]:28
격자를 따라 동쪽 또는 남쪽으로만 걸어 (0, 0)부터 (2, 3)까지 가는 경로의 수는 조합의 수(이항 계수)
과 같다. 다른 점도 이와 같은 수를 계산하여 그 점의 위치에 적으면 파스칼의 삼각형을 얻는다.
원점과 점
사이, 단위 벡터들
를 보폭으로 하는 격자 경로의 수는 다항 계수
![{\displaystyle {\binom {v_{1}+\cdots +v_{d}}{v_{1},\dots ,v_{n}}}={\frac {(v_{1}+\cdots v_{d})!}{v_{1}!\cdots v_{d}!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06a9f07ed21509a2c37ad9e866bd94706da8a43b)
이다.[1]:28 특히, 원점과 점
사이,
을 보폭으로 하는 격자 경로의 수는 이항 계수
![{\displaystyle {\binom {a+b}{a}}={\frac {(a+b)!}{a!b!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e2e0c8881b84a5acfe34f3d675d0dcb8c9fd106)
이다.
다이크 경로(영어: Dyck path)는 원점과 점
사이,
을 보폭으로 하는 격자 경로로 간주하거나, 원점과 점
사이의 단위 벡터 보폭의 격자 경로 가운데, 대각선
위를 지나지 않는 경우로 간주할 수 있다. 다이크 경로의 수는 카탈랑 수
![{\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}={\frac {(2n)!}{(n+1)!n!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d3cc1809ef4fe1853927780beb6a012e857b595)
이다.