2.1 이항계수

1장에서 언급한 $C(n,r)$은 조합론에서 가장 중요하고 의미 있는 수 중의 하나이다. 이 수를 '이항계수'라 하는데 그 이유는 다음 이항식 
   $B(a,b) = (a+b)\times(a+b)\times \cdots \times (a+b) = (a+b)^n$ 
를 전개했을 때 계수로 나타나기 때문이다. 

이항식을 전개하였을때 나타나는 각 항은 $a$와 $b$의 곱으로 이루어진 $n$차 단항식이다. 위의 이항식을 분배법칙에 의해 전개할 때 각 인수
   $(a+b)$
에서 $a$나 $b$ 중의 하나를 선택해야 한다. 만일 $b$가 $r$개의 인수에서 선택된다면 $a$는 자동적으로 나머지  $(n-r)$개의 인수에서 선택된다. 이때, 이항식의 계수는 $n$개의 $(a+b)$의 곱에서 $b$를 선택할 인수 $(a+b)$를 $ r$개를 선택하여야 하므로 조합의 수 
   $C(n,r)$ (1.3 순열과 조합)

임이 분명하다. 여기서 우리는 조합적으로 
   $C(n,r) = C(n,n-r)$
과 같음을 아주 쉽게 이해할 수 있다(왜일까?). 

이항식의 전개식에서 서로 다른 항의 개는 $n+1$이며 총 항의 개수는 
   $B(1,1) = 2\times2\times\cdots\times2=2^n$
이다. 이것은 이항식의 계수들의 합과 같다. 
  $B(1,1) = C(n,0)+C(n,1)+C(n,2)+\cdots+C(n,n)$
또한, 
  $\begin{align}0 &= B(1,-1) \\ &= C(n,0)-C(n,1)+C(n,2)-\cdots+(-1)^r C(n,r)+\cdots+(-1)^n C(n,n)\end{align}$
이다. 

 

---

기본적인 조합적 항등식
   $C(n,r) = C(n-1,r-1)+C(n-1,r)$
은 대수적 증명이 가능하지만 조합적으로 증명한다.

사실 나는 조합론에서 수식의 계산보다 이러한 이해를 더 선호하는 편이다.

 

좌변은 서로 다른 $n$개에서 $r$개를 선택하는 조합의 수이다. 그러므로 우변의 식 또한 좌변과 동일한 셈하기의 다른 표현  방식에 불과하다. 한 사건을 작은 두 사건으로 분할하고 '합의 법칙'을 활용한 것으로 예상할 수 있다. 그럼, 두 사건으로 어떻게 분할 했을까 유추해보자.

 

우리는 이미 결과를 알고 있으므로 어떤 상황에 의해 그런 결과가 나왔는지를 추정하면 된다. 

서로 다른 $n$개의 대상을 $1, 2, 3, \cdots, n$이라 할 때 $r$개를 수를 선택하는 경우, 특정한 하나를 포함하는 경우와 아닌 경우로 분할할 수 있다. 특정한 하나를 $n$이라하면  $n$을 포함하는 것들의 개수는 $n$을 제외한 서로 다른 수 $(n-1)$개에서  $(r-1)$개의 수를 선택하는 조합의 수 
   $C(n-1,r-1)$
이고, $n$을 포함하지 않는 것의 개수는 $n$을 제외한 서로 다른 수 $(n-1)$개에서 $r$개의 수를 선택하는 조합의 수
   $C(n-1,r)$
이다. 이 두 사건은 동시에 일어나지 않으므로 '합의 법칙'에 의해 위의 항등식이 성립한다. 

$P(n,r)$에 대해서도 위와 같은 방법으로 조합적 항등식을 만들어 보자. 여기에 그것에 대한 결과만 기술하고 독자들에게 연습문제로 남겨둔다. 
    $P(n,r) = rP(n-1,r-1)+P(n-1,r)$