격자 경로 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Lattice Path in Z2.svg|섬네일|300픽셀|길이 5, 보폭 (1, 1), (2, 0), (0, -1)의 격자 경로]]

[[조합론]]에서, '''격자 경로'''({{llang|en|lattice path}})는 주어진 범위의 보폭을 유지하며 걸어 얻는 경로이다.

== 정의 ==
길이 <math>n</math>, 보폭 <math>S\subseteq\mathbb Z^d</math>의 '''격자 경로'''는 <math>v_i-v_{i-1}\in S</math> (<math>i=1,\dots,n</math>)를 만족시키는 점렬 <math>\{v^{(0)},v^{(1)},\dots,v^{(n)}\}\subset\mathbb Z^d</math>이다.<ref name="Stanley">{{서적 인용
|url=http://math.mit.edu/~rstan/ec/ec1/
|성=Stanley
|이름=Richard P.
|제목=Enumerative Combinatorics. Volume 1
|언어=en
|판=2
|출판사=Cambridge University Press
|날짜=2012
}}</ref>{{rp|28}}

== 예 ==
=== 단위 벡터 보폭 ===
[[파일:Walking on Pascal's Triangle SVG.svg|섬네일|300픽셀|격자를 따라 동쪽 또는 남쪽으로만 걸어 (0, 0)부터 (2, 3)까지 가는 경로의 수는 [[조합]]의 수([[이항 계수]]) <math>\textstyle\binom 52=10</math>과 같다. 다른 점도 이와 같은 수를 계산하여 그 점의 위치에 적으면 [[파스칼의 삼각형]]을 얻는다.]]
원점과 점 <math>v\in\mathbb Z^d</math> 사이, 단위 벡터들 <math>\{e^{(1)},\dots,e^{(d)}\}</math>를 보폭으로 하는 격자 경로의 수는 [[다항 계수]]
:<math>\binom{v_1+\cdots+v_d}{v_1,\dots,v_n}=\frac{(v_1+\cdots v_d)!}{v_1!\cdots v_d!}</math>
이다.<ref name="Stanley" />{{rp|28}} 특히, 원점과 점 <math>(a,b)\in\mathbb Z^2</math> 사이, <math>\{(1,0),(0,1)\}</math>을 보폭으로 하는 격자 경로의 수는 [[이항 계수]]
:<math>\binom{a+b}a=\frac{(a+b)!}{a!b!}</math>
이다.

=== 다이크 경로 ===
{{본문|다이크 경로}}
[[다이크 경로]]({{llang|en|Dyck path}})는 원점과 점 <math>(0,2n)</math> 사이, <math>\{(1,1),(1,-1)\}</math>을 보폭으로 하는 격자 경로로 간주하거나, 원점과 점 <math>(n,n)</math> 사이의 단위 벡터 보폭의 격자 경로 가운데, 대각선 <math>y=x</math> 위를 지나지 않는 경우로 간주할 수 있다. 다이크 경로의 수는 [[카탈랑 수]]
:<math>C_n=\frac1{n+1}\binom{2n}n=\frac{(2n)!}{(n+1)!n!}</math>
이다.

== 같이 보기 ==
* [[한붓그리기]]
* [[모츠킨 수]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=LatticePath|title=Lattice path}}
* {{매스월드|id=PointLattice|title=Point lattice}}

[[분류:순서론]]
[[분류:열거조합론]]
[[분류:알고리즘]]
[[분류:수열]]