꼭 알아야 하는 이항계수 공식

개인적으로 가장 알아야한다고 생각하는 네가지를 쓰겠다.

1번째

\(\binom n k = \binom {n-1}{k} + \binom {n-1}{k-1}\)

예를 들어 생각해보면 쉬운데 어떤 반에서 n명의 학생중 k명의 대표를 뽑으려고하는데 이 때의 경우의 수는

특정 학생 x 에 대해 두가지의 케이스로 나누어 생각해 볼 수가있다.

학생 x를 뽑는 경우와 뽑지 않는 경우 이렇게 두 가지의 케이스이다.

만약 학생 x를 뽑는다면 나머지 n-1 명의 학생들 중에 k-1명의 대표를 더 뽑아야 하므로 \(\binom {n-1}{k-1}\) 가지의

경우의 수가 있으며, 학생 x를 뽑지 않는다면 나머지 n-1 명의 학생들 중에 k명의 대표를 뽑아야 하므로

\(\binom {n-1}{k}\) 가지의 경우의 수가 있다. 그래서 두 경우의 수를 더하면 된다.

2번째

\(\binom n 0 + \binom n 1 + \binom n 2 + \cdots + \binom n n = 2^n\)

이건 (a+b)^n 를 전개했을 때 여러 항들의 계수는 말그대로 이항계수가 나온다 즉

0~n 의 모든 x에 대해 \(\binom n x\) 가 계수로 등장한다고 할 수 있는데 a=b=1 을 대입하면

\(a^ib^j\) 가 1이되므로 전개 식에서는 이항 계수만 남고 (a+b)^n 는 (1+1)^n 가 되어서 2^n 가된다.

3번째

\(\binom n n + \binom {n+1} n + \cdots + \binom {n+k} n = \binom {n+k+1} {n+1} \)

이건 표를 그려보면 이해하기 쉽다. 앞서 말한 1번 공식을 사용하여 \(\binom n r\) 을 분리해나가보자.

n = 4, r = 2 인 예를 들어보자.

\(\binom 4 2 \) 는 \(\binom 3 2 와 \binom 3 1\) 로 분리되고,

또 \(\binom 3 2 는 \binom 2 1 과 \binom 2 2 로 분리되며, \binom 2 2 는 \binom 1 1\) 과 같으므로

결국 밑줄 친 부분은 네모 친 부분으로 분리된다.

4번

\(\binom n 0 + \binom {n+1} 1 + \cdots + \binom {n+k} {k} = \binom {n+k+1} {k} \)

이것도 표를 그려보면 쉽다. 사실 3번과 비슷한 원리인데 3번은 표에서 한 이항계수에 대해 수평으로 분리해 나가서

최종적으로 수평한 한줄이 남게 되고 4번은 수직으로 분리해 나가서 최종적으로 수직한 한줄이 남게된다고 생각하면

이해가 쉬울 것같다.

근데 사실 낚시가 하나있는데 3번과 4번은 같은거다...

nCr = nC(n-r) 이기 때문에 변형해보면 식이 완전히 같다.

그리고 3번의 표에서 밑줄과 네모박스들을 위의 식에 따라 바꿔보면 4번과 같은 그림이 나온다.