조합 항등식의 조합론적 증명

이번 글에서는 몇 가지 조합 항등식(combination identity)들을 대수적인 방법이나 기타 다른 방법을 이용하지 않고 오직 조합론적 증명(combinatorial proof) 방법만을 이용하여 증명하려고 한다. 모든 증명은 기본적인 Double counting (한가지 대상을 두가지 다른 방법으로 셈하여 그 두개의 셈이 서로 같음을 보이는 방법)을 바탕으로 하고 있다.

$\displaystyle{{n \choose r}= {n \choose n-r}}$

증명. $n$명의 지원자 중에서 $r$명의 합격자를 선택하는 경우의 수 ${n \choose r}$은 $n$명의 지원자 중에서 $n-r$명의 불합격자를 선택하는 경우의 수 ${n \choose n-r}$와 같다.

$\displaystyle{{n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}}$

증명. $n$명의 지원자 중에서 $r$명의 합격자를 선택하는 경우의 수 ${n \choose r}$은 $n$명의 지원자중에서 $a$라는 지원자를 먼저 합격 시키고 나머지 $n-1$명의 지원자 중에서 $r-1$명의 합격자를 선택하는 경우의 수 ${n-1 \choose r-1}$과 $n$명의 지원자 중 $a$는 불합격 시키고 나머지 $n-1$명 중에서 $r$명의 합격자를 선택하는 경우의 수 ${n-1 \choose r}$의 합과 같다.

$\displaystyle{{n \choose r} = \frac{n}{r}{n-1 \choose r-1}}$

증명. $n$명의 지원자 중에서 $r$명의 합격자를 선택하고, 이 합격자들 $r$명 중에서 합격자 대표를 한명 선출하는 경우의 수 $r{n \choose r}$은, $n$명의 지원자 중에서 합격자 대표를 먼저 선택하고, 나머지 $n-1$명의 지원자 중에서 $r-1$명의 합격자를 선택하는 경우의 수 $n {n-1 \choose r-1}$과 같다.

$\displaystyle{{n \choose r} = \frac{n-r+1}{r}{n \choose r-1}}$

증명. $n$명의 지원자 중에서 $r$명의 합격자를 선택하고, 이 합격자들 $r$명 중에서 합격자 대표를 한명 선출하는 경우의 수 $r{n \choose r}$은, $n$명의 지원자 중에서 합격자 대표가 될 사람을 제외한 $r-1$명의 합격자만을 먼저 선택하고, 나머지 $n-(r-1)$명 중에서 합격자 대표를 선출하는  경우의 수 $(n-r+1){n \choose r-1}$과 같다.

$\displaystyle{{n \choose r}{n-r \choose k} = {n \choose k}{n-k \choose r}}$

증명. $n$명의 지원자 중에서 $A$ 부서로 보낼 $r$명의 합격자를 선택하고, 이들을 제외한 $n-r$명 중에서 $B$ 부서로 보낼 $k$명을 추가로 선택하는 경우의 수 ${n \choose r}{n-r \choose k}$은, $n$명의 지원자 중에서 $B$ 부서로 보낼 $k$명의 합격자를 선택하고, 이들을 제외한 $n-k$명 중에서 $A$ 부서로 보낼 $r$명을 추가로 선택하는 경우의 수 ${n \choose k}{n-k \choose r}$과 같다.

$\displaystyle{\sum_{k=0}^{n} {n \choose k} = 2^n}$

증명. 위 식의 좌변은 $n$명의 지원자 중에서 임의의 $0 \leq k \leq n$에 대하여, $k$명의 합격자를 선택하는 경우의 수와 같다. 이 때, 모든 $k$를 고려하므로 각각의 지원자는 합격했을 수도 또는 불합격했을 수도 있다. 따라서 이는 각각의 지원자 $n$명에게 개별적으로 합격, 또는 불합격을 통보하는 경우의 수 $2^n$과 같다.

$\displaystyle{\sum_{k=0}^{n} k{n \choose k} = n2^{n-1}}$

증명.  위 식의 좌변은 $n$명의 지원자 중에서 임의의 $0 \leq k \leq n$에 대하여, $k$명의 합격자를 선택하고, 이 합격자들 $k$명 중에서 합격자 대표를 한명 선출하는 경우의 수와 같다. 이는 우선 $n$명의 지원자들 중에서 합격자 대표를 먼저 선출하고, 나머지 $n-1$명에서 개별적으로 합격, 또는 불합격을 통보하는 경우의 수 $n2^{n-1}$과 같다.

$\displaystyle{{2n \choose 2} = 2{n \choose 2} + n^2}$

증명. $2n$명의 지원자를 각각 $n$명으로 이루어진 그룹 $A$와 $B$로 나눈다. 이제 $2n$명의 지원자 중에서 $2$명의 합격자를 선택하는 경우의 수 ${2n \choose 2}$을 아래의 세 가지 경우로 나뉘어 진다.

그룹 $A$에서만 $2$명을 합격시키는 경우의 수: ${n \choose 2}$,

그룹 $B$에서만 $2$명을 합격시키는 경우의 수: ${n \choose 2}$,

그룹 $A$와 $B$에서 각가 $1$명씩 합격시키는 경우의 수: ${n \choose 1}{n \choose 1} = n^2$.

따라서 총 경우의 수는 위에 주어진 각각의 경우의 수의 합과 같다.

$\displaystyle{{m+n \choose r}  = \sum_{k=0}^{r} {m \choose k}{n \choose r-k}}$

증명. $m+n$명의 지원자를 각각 $m$명과 $n$명으로 이루어진 그룹 $A$와 $B$로 나눈다. 이제 $m+n$명의 지원자 중에서 $r$명의 합격자를 선택하는 경우의 수 ${m+n \choose r}$을 아래과 같이 나누어 생각할 수 있다.

그룹 $A$에서 $0$명, 그룹 $B$에서 $r$명을 합격시키는 경우의 수: ${m \choose 0}{n \choose r}$,

그룹 $A$에서 $1$명, 그룹 $B$에서 $r-1$명을 합격시키는 경우의 수: ${m \choose 1}{n \choose r-1}$,

그룹 $A$에서 $2$명, 그룹 $B$에서 $r-2$명을 합격시키는 경우의 수: ${m \choose 2}{n \choose r-2}$,

...

그룹 $A$에서 $r$명, 그룹 $B$에서 $0$명을 합격시키는 경우의 수: ${m \choose r}{n \choose 0}$,

따라서 총 경우의 수는 위에 주어진 각각의 경우의 수의 합과 같다.

$\displaystyle{{n+1 \choose r+1} = \sum_{k=r}^{n} {k \choose r}}$

증명. $n+1$명의 지원자를 일렬로 줄을 세운다. 이제 $n+1$명의 지원자 중에서 $r+1$명의 합격자를 선택하는 경우의 수 ${m+1 \choose r+1}$을 아래과 같이 나누어 생각할 수 있다.

앞에서 $r+1$번째 지원자를 우선 합격시키고, $r+1$번째 지원자 앞에 선 $r$명의 지원자 중에서 나머지 $r$명을 합격시키는 경우의 수: ${r \choose r}$

앞에서 $r+2$번째 지원자를 우선 합격시키고, $r+2$번째 지원자 앞에 선 $r+1$명의 지원자 중에서 나머지 $r$명을 합격시키는 경우의 수: ${r+1 \choose r}$

...

앞에서 $n$번째 지원자를 우선 합격시키고, $n$번째 지원자 앞에 선 $n-1$명의 지원자 중에서 나머지 $r$명을 합격시키는 경우의 수: ${n-1 \choose r}$

앞에서 $n+1$번째 지원자를 우선 합격시키고, $r+1$번째 지원자 앞에 선 $n$명의 지원자 중에서 나머지 $r$명을 합격시키는 경우의 수: ${n \choose r}$

따라서 총 경우의 수는 위에 주어진 각각의 경우의 수의 합과 같다.