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

다음과 같은 등식이 성립합을 식이 아닌 조합론적(스토리해석적)으로 해석해보기 하자. 

\( _{n} \mathrm{C} _{0} \)  +  \( _{n+1} \mathrm{C} _{1} \) + \( _{n+2} \mathrm{C} _{2} \) + \( \cdots \) + \( _{n+r} \mathrm{C} _{r} \) =  \( _{n+r+1} \mathrm{C} _{r} \)

 

우선, 우변의  \( _{n+r+1} \mathrm{C} _{r} \)은 집합 A=\( \left \{ 1, 2, 3, 4, \cdots , n+r+1 \right \}\)의 부분집합 중에서  원소의 개수가 \( \mathit {r}\)인 부분집합의 개수이다. 

한편, 원소의 개수가  \( \mathit {r}\)인 집합 A의 부분집합 중에서

\(  n+r+1 \)을 포함하지 않는 부분집합의 개수는                                           \( _{n+r} \mathrm{C} _{r} \)

\(  n+r+1 \)은 포함하지만 \(  n+r \)을 포함하지 않는 부분집합의 개수는              \( _{n+r-1} \mathrm{C} _{r-1} \)

\(  n+r+1 \), \(  n+r \)을 포함하지만  \(  n\)을 포함하지 않는 부분집합의 개수는       \( _{n+r-2} \mathrm{C} _{r-2} \)

$$ \cdots $$

\(  n+r+1 \), \(  n+r \) \( \cdots \), 을 포함하지만 n+1를 포함하지 않는 원소의 개수가 r인 부분집합은 나머지 원소 1,2,3,  \( \cdots \), k-1 중에서 k-n-1개의 원소를 뽑아야 되므로 \( _{k-1} \mathrm{C} _{k-n-1} \)이다.

따라서, 

\( _{n} \mathrm{C} _{0} \)  +  \( _{n+1} \mathrm{C} _{1} \) + \( _{n+2} \mathrm{C} _{2} \) + \( \cdots \) + \( _{n+r} \mathrm{C} _{r} \) =  \( _{n+r+1} \mathrm{C} _{r} \)이 성립한다.