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)$ 임을 알..
2022. 9. 10.
2.2 파스칼 삼각형
파스칼 삼각형 $(a+b)$ $(a+b)\times(a+b)$ $(a+b)\times(a+b)\times(a+b)$ ...... 의 전개식에서 각항의 계수만을 차례로 나열하면 삼각형 모양을 얻게 된다. 이와같이 이항계수를 나열한 것을 '파스칼 삼각형'이라고 한다. 파스칼 삼각형에서는 여러 가지 성질을 발견할 수 있다. 그 중 '하키 스틱 패턴'이라 불리는 다음 항등식에 대해 생각해 보자. $C(r,r)+C(r+1,r)+\cdots+C(n,r) = C(n+1,r+1)$ 이것 또한, 조합적으로 증명한다. 서로 다른 $(n+1)$개의 대상 $1, 2, \cdots, (n+1)$에서 $(r+1)$개를 선택하여 담은 임의의 한 상자를 X라 하자. 첫번째, $1$이 X에 속하는 경우, X를 만들기 위해서는 $1$을..
2022. 9. 10.
