이 글에선 하키스틱 법칙이라는 꽤 유명한 조합적 항등식을 조합적으로 증명하겠습니다.
Theorem 1. \sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}
파스칼의 삼각형을 생각하면 왜 이 등식에 이런 이름이 붙었는지 알 수 있습니다.
Proof of Theorem 1. S=\{ a_1, a_2, \cdots , a_{n+1} \}의 부분집합중 원소가 r+1개인 것의 집합을
A라 하면,
|A|=\binom{n+1}{r+1}이다. 이제
A_1 :=( a_1를 포함하고
a_2, a_3, \cdots, a_{n+1})중 r개를 원소로 갖는 집합들의 집합,
A_2 :=( a_2를 포함하고
a_3, a_4 \cdots, a_{n+1})중 r개를 원소로 갖는 집합들의 집합,
A_3 :=( a_3를 포함하고
a_4, a_5 \cdots, a_{n+1})중 r개를 원소로 갖는 집합들의 집합,
\cdots
A_{n-r+1} :=( a_{n-r+1}를 포함하고
a_{n-r+2}, a_{n-r+3} \cdots, a_{n+1})중 r개를 원소로 갖는 집합들의 집합이라고 하자. 그러면
|A_1|=\binom{n}{r} , |A_2|=\binom{n-1}{r} ,|A_3|=\binom{n-2}{r} , \cdots ,|A_{n-r+1} |=\binom{n-(n-r)}{r}
이다. 한편
A_1, A_2, \cdots , A_{n-r+1}들은 쌍마다 서로소이고
A_1 \cup A_2 \cup \cdots \cup A_{n-r+1}= A므로 합의 법칙에 의해
\binom{n}{r} + \binom{n-1}{r} + \cdots + \binom{r}{r} = \binom{n+1}{r+1}이다.
\Box
이 식을 조금 변형하면 다음을 얻을 수 있습니다 :
Theorem 2. \sum_{k=0}^{r} _n H_k = _{n+1} H_r
이 식은 Theorem 1과 동치이므로 이미 증명되었지만 이것도 따로 증명해보겠습니다.
Proof of Theorem 2. c_1, c_2, \cdots , c_n개의 색깔의 공들을 생각하자. 이들 중에서 공을 중복을 포함하여 r개 뽑는 경우의 수는
_{n+1} H_r이다. 그런데 이 경우의 수는 다음과 같이도 구할 수 있다 :
c_1색의 공을 k개
(1 \le k \le r) 뽑아놓고 나머지 공은 나머지
c_2, c_3, \cdots , c_n 색 중에서 뽑는다. 이 때 공을 뽑는 경우의 수는
_{n} H_k이다. 이들을 합해주면 원래 구하려는 경우의 수가 나온다. 즉,
\sum_{k=0}^{r} _n H_k = _{n+1} H_r이다.
\Box
이제 이것을 이용하여 역시 잘 알려진 급수를 구해봅시다.
Theorem 3. \sum_{k=1}^{n} k(k+1)(k+2)\cdots (k+r) = \frac{n(n+1)(n+2)\cdots (n+r+1)}{r+1}
Proof of Theorem 3. 양변을 r!으로 나누면 Theorem 2와 똑같은 형태가 나온다.
\Box
