이항정리는 (x+y)^n을 전개시키면 어떻게 되는지 설명하는 정리이다. 여기엔 조합론에서 매우 중요한 C(n,r)이 사용된다.(C(n,r)이 n개의 물체중에서 r개를 선택하는 조합의 수임을 기억하라.) 이항정리로 말미암아 이 C(n,r)은 로 쓰고 이항계수라고도 부르기도한다. 본 글에서는 필자가 이항계수의 기호입력이 좀 익숙치 않은 관계로 모두 C(n,r)로 통일하여 쓰도록 하겠다.
이항정리의 증명은 여러가지가 있을 수 있다. 수학적 귀납법을 이용할 수도 있고 조합적 증명을 이용할 수도 있다. 하지만 이번 글에서는 이항정리 자체에 주목하지 않고 정리로 부터 나오는 따름정리(corollary)들의 조합적 증명에 더 주목하기로 한다.
이진코드(binary code)를 이용하면 풀 수 있다. 이진코드란 0과 1로만 표현되는 코드로 1010, 000111, 10100100010000, ...등이 모두 이진코드이다.
길이가 n인 이진코드의 개수를 생각하자.
(우변)처음 0을 쓸지 1을 쓸지 정해야하므로 경우의 수는 2, 그렇게 처음 숫자를 정하고 다음 숫자를 또 0을 쓸지 1일 쓸지 정해야하므로 경우의 수는 2×2, 그렇게 n자리를 모두 채울 때까지 계속 2를 곱하게 되므로 총 경우의 수는 2의 n제곱이 된다.
(좌변) 이 이진코드들은 코드 속에 쓰인 1의 개수로 구분할 수 있다. 1이 하나도 안 쓰이면 0개라고 하고 그다음부터 1개쓰임, 2개쓰임, ... n개쓰임까지 총 n+1개의 항목으로 나누자. 각 항목은 몇 개의 이진코드를 갖는가?
어던 길이 n 이진코드 안에서 1을 k개 쓰려면 어느 자리에 쓸지 정해야한다. 이는 순서와 관계없으므로 조합의 수가 된다. 즉 C(n,k)가 k개쓰임 항목의 이진코드 개수이다.
이를 다 합하면 C(n,0)+C(n,1)+...+C(n,n)이 된다.
아래는 n=4일 때를 그림으로 표현한 것이다.
이 이외에도 집합 {1, 2, ... , n}의 부분집합의 개수로 해석하는 방법도 있다. (당연히 {1, 2, ... , n}의 부분집합들은 정확하게 길이n의 이진코드들과 일대일 완전대응시킬 수 있다.)
문제2. 풀이
약간 현실적인 예를 들어본다. n명의 학생 중 최소 1명의 동아리 부원과 부장을 뽑는데, 그 인원수는 제한이 없다고 하자.(모두가 동아리부원이 될 수도 있고, 한 명만 부원(이면서 동시에 부장)일 수도 있다.) 이 때 발생하는 모든 경우의 수를 생각하자.
(우변) 동아리 부원의 수가 k명이라고 하자. k는 1부터 n까지 가능하고, 각 경우는 배타적이다. 고로 각 경우를 더하면 총 경우의 수가 될 것이다. 일단 n명 중 k명의 부원을 뽑아야하므로 C(n,k)이다. 이제 이 k명의 부원 중 1명의 부장을 뽑아야하므로 C(k,1), 즉 k를 추가로 곱해야한다. 결국 동아리 부원의 수가 k명일 때 발생하는 경우의 수는 kC(n,k)이고, k=1~n일 때를 모두 더하면 1C(n,1)+...+nC(n,n)가 된다.
(좌변) 일단 부장이 될 학생을 먼저 정하고 부장이 아닌 부원을 뽑을 수도 있다. 이는 뽑는 순서의 차이만 있을 뿐 총 경우의 수에 영향을 주지 않는다. 부장이 될 학생을 정하는 경우의 수는 C(n,1), 즉 n이다. 이후 총 n-1명의 남은 학생들 중 부원이 될 사람을 골라야하는데 이미 부장이 봅혔으니 0명부터 n-1명까지 제한이 없다. 제한이 없다는 이야기는 각 학생이 자유롭게 부원이 될지, 안 될지 둘 중 하나를 결정하면 된다는 것이므로 2를 총 n-1번 곱하면 된다. 즉 2^(n-1)이 된다. 아까 부장을 정할 때 나온 n과 곱하면 n2^(n-1)가 된다.
