2차원 MXN 격자에 있는경로의 개수 계산하기

가령 M개의 행과 N개의 열을 가진 격자(grid)를 생각해 보자.

이것은 조합을 계산하면 된다.

(M+N)C(M) 또는 (M+N)C(N)이 동일한 값을 결과로 도출하게 된다.

이것은 먼저 A가 시작점(왼쪽 상단), B(가 오른쪽 하단)이라고 가정했을 때, A에서 B로 가는 경로는 오른쪽 방향으로 가는 경로는 N만큼 있고, 아래쪽으로 가는 방향으로 가는 경로는 M만큼 있기 때문에 총 경로 개수는 M+N이 있고, 이중에서 중복을 허용하지 않고, 순서는 중요하지 않은 조합을 계산하면 되는 것이다. 조합은 다음과 같이 계산한다.
여기에서 n은 조합을 계산할 대상이 되는 개체의 수를 나타내고, r은 몇 개의 객체를 선택할지를 나타낸다.

가령 16X12의 조합을 계산할 때는, 28C12가 되고 이것을 계산하면, 30421755을 얻게 된다.