파스칼의 삼각형 의미적(조합론적)해석

다음 등식이 성립하는 것을 흥미로운 두가지 방법으로 소개한다.

$$  _{r}\mathrm{C} _{r}+ _{r+1} \mathit{C} _{r} +  _{r+2} \textrm{C} _{r} +\cdots+ _{n+r} \textrm{C} _{r} = _{n+r+1} \textrm{C} _{r} $$

 

(1) 집합의 부분집합의 개수를 이용한 증명

집합 A=\(\left \{1,2,3,4, \cdots , n+1  \right \} \)에서 r개의 원소를 뽑는  방법의 수는 \(   _{n+1} \mathrm{C}_{r}  \)이다.

집합 A의 부분집합 중에서

원소의 최솟값이 1인 부분집합의 개수는  \( _{n} \mathrm{C}_{r} \)

원소의 최솟값이 2인 부분집합의 개수는  \( _{n-1} \mathrm{C}_{r} \)

원소의 최솟값이 3인 부분집합의 개수는  \( _{n-2} \mathrm{C}_{r} \)

$$ \cdots $$

원소의 최솟값이 n-r+1 인 부분집합의 개수는  \(   _{r} \mathrm{C}_{r}  \) 이므로

$$  _{r}\mathrm{C} _{r}+ _{r+1} \mathit{C} _{r} +  _{r+2} \textrm{C} _{r} +\cdots + _{n+r} \textrm{C} _{r} = _{n+r+1} \textrm{C} _{r} $$

이 성립한다.

 

(2) 최단경로의 방법을 이용한 증명

 A에서 B로 가는 최단경로의 수는 \(   _{n+1} \mathrm{C}_{r+1}  \)이다.

한편, A에서 B까지 가는 최단경로는 반드시 \(p_{1}\), \(p_{2}\),\(p_{3}\), \(\cdots\), \(p_{n-r+1}\)중 반드시 한 번은 지나가야 한다.

 \(p_{1}\)을 지난 가는 최단경로의 수는 \( _{n} \mathrm{C}_{r} \)

\(p_{2}\)을 지난 가는 최단경로의 수는  \( _{n-1} \mathrm{C}_{r} \)

 \(p_{3}\)을 지난 가는 최단경로의 수는 \( _{n-2} \mathrm{C}_{r} \)

$$ \cdots $$

\(p_{n-r+1}\)을 지난 가는 최단경로의 수는   \(   _{r} \mathrm{C}_{r}  \)

 

따라서,  다음이 성립합을 알 수 있다.

$$  _{r}\mathrm{C} _{r}+ _{r+1} \mathit{C} _{r} +  _{r+2} \textrm{C} _{r} +\cdots+ _{n} \textrm{C} _{r} = _{n+1} \textrm{C} _{r+1} $$

파스칼의 삼각형