2.3 격자 직사각형에서의 최단경로

격자 직사각형에서의 최단 경로 $xy$-평면의 점 $(a,b)$에 대해 $a$와 $b$가 둘 다 정수일 때 이를 '격자점'이라 한다. 격자점 $(0,0)$ 으로부터 격자점 $(m,n)$으로 가는 최단 경로를 생각하자. 여기서 $m, n$은 자연수이다. 이때, 전체 최단경로의 수는
   $C(m+n,m)$ 또는 $C(m+n, n)$
이다. 그 이유는 다음과 같다. 

최단경로라 함은 ➡ 방향이나 ⬆ 방향으로의 이동이다. 어느 최단경로든지 $m$개의 ➡와 $n$개의 ⬆로 구성된다. 따라서 전체 최단경로의 수는 $m$개의 ➡와 $n$개의 ⬆를 배열하는 순열이다. 즉, '같은것을 포함하는 순열의 수(1.6 같은 것을 포함하는 순열)'다. 따라서 전체 최단경로의 수는 
   $P(m+n; m, n) = C(m+n,m)$

임을 알수 있다. 

또한, $\rm O(0,0)$으로부터  ${\rm A}(a,b)$를 지나 ${\rm Q}(m,n)$까지 가는 최단경로의 수는 '곱의 법칙' 에 의해
   $C(a+b, a)\cdot C((m-a)+(n-b), m-a)$
이다.

 

최단경로를 세는 방법을 이용하여 다음의 '반더몬트 항등식'을 유도해 보자. 
     $\begin{align} C(m,0)\times C(n,r) + C(m,1)\times C(n,r-1)+\cdots+C(m,r)\times C(n,0) \\ = C(m+n,r) \end{align}$
단, 자연수 $m, n, r$은 $m, n \geq r$을 만족한다. 

'반더몬트 항등식'의 다른 증명 : 

우변 $C(m+n, r)$은 서로 다른 $m+n$개이 대상에서 $r$개를 선택하는 조합의 수임에 주목하자. 이 수를 다른 방식으로 셈할 것이다.  특정한 $m$개의 대상에서 $i$개를 선택한 후, 특정하지 않은 $n$개의 대상에서 $r-i$개를 선택하는 방법의 수는 

   $C(m, i)\times C(n, r-i)$

이다. 이제, 각각의 $i=0,1,2,\cdots,r$에 대하여 합의 법칙을 적용하면, 이것은 서로 다른 $m+n$개이 대상에서 $r$개를 선택하는 조합의 수를 의미한다. 

 

$\rm O(0,0)$에서 ${\rm Q}(m+n-r, r)$까지의 최단경로의 수는 $C(m+n,r)$이다. 이제 이 수를 다른 방식으로 센다. 

격자점
   ${\rm A}_0 (m,0), {\rm A}_1 (m-1,1), \cdots, {\rm A}_r (m-r,r)$
을 생각하자. $\rm O$에서 $\rm Q$로 가는 최단경로들은 ${\rm A}_i$ 중 하나를 반드시 지나고 또 그 하나만을 지나간다. ${\rm A}_i (m-i,i)$를 지나는 최단경로들의 수는
   $C(m- {i}+{i}, i)\times C(({m}+n-{r} - {m}+{ i})+({r} - {i}), (r-i))$

              $= C(m,i) \times C(n,r-i) (i=0,1,\cdots,r)$
이므로 반더몬트 항등식은 '합의 법칙'에 의해 성립한다. 

꽤 복잡하게 보였던 수식도 의외로 싶게 해결되는 순간이 있다. 나의 주변 상황이 바뀌거나 정리되지 않을 때, 그 불쾌한 감정들에 몰입하는 것보다 나의 생각을 바꾸는 것은 의외로 좋은 선택이다. 나를 둘러싼 상황나 타인의 마음은 내 의지의 영역이 아니다. 그러나 내 생각은 내가 선택할 수 있다. 나의 오늘과 내일이 행복해 질 수 있는 생각을 선택하자.