격자 경로

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

 정의 
길이 , 보폭 의 격자 경로는  ()를 만족시키는 점렬 이다.

 예 
 단위 벡터 보폭 
섬네일|300픽셀|격자를 따라 동쪽 또는 남쪽으로만 걸어 (0, 0)부터 (2, 3)까지 가는 경로의 수는 조합의 수(이항 계수) 과 같다. 다른 점도 이와 같은 수를 계산하여 그 점의 위치에 적으면 파스칼의 삼각형을 얻는다.
원점과 점  사이, 단위 벡터들 를 보폭으로 하는 격자 경로의 수는 다항 계수

이다. 특히, 원점과 점  사이, 을 보폭으로 하는 격자 경로의 수는 이항 계수

이다.

 다이크 경로 

다이크 경로()는 원점과 점  사이, 을 보폭으로 하는 격자 경로로 간주하거나, 원점과 점  사이의 단위 벡터 보폭의 격자 경로 가운데, 대각선  위를 지나지 않는 경우로 간주할 수 있다. 다이크 경로의 수는 카탈랑 수

이다.

 같이 보기 
 한붓그리기
 모츠킨 수

 각주 

 외부 링크 



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