경우의 수 (4) - 이항정리

1. 이항 정리(Binomial Theorem)를 왜배울까?

• $(a+b)^2$와 같이 쉬운 이항 전개는 우리가 쉽게 할 수 있다.
• 근데 $(a+b)^5$와 같은 전개하라고 하면 일단 한숨이 나온다.
• 이항정리란 $(a+b)^n$과 같은 식이 어떻게 일반적으로 전개되는지 배우는 것이다.
• 왜 "이항"일까? $(a+b)^n$과 같이 항이 a와 b, 딱 두개뿐이기 때문이다. (2항 정리이다)

 

2. 이항 정리를 경우의 수로 바라보기

• 가장 쉬운 예인 $(a+b)^2 = (a+b)(a+b)$를 먼저 생각해보자.
• $(a+b)(a+b) = aa + ab + ba + bb$이라는 것은 누구나 아는 사실이다.
• 이걸 경우의 수의 관점에서 바라본다면, 아래처럼 생각 할 수 있다.
• 이항정리는 앞(a+b)와 뒤(a+b)에서 각각 원소를 하나씩 뽑아서 곱한 것들의 총합이다.
• 그러니까, 앞 (a+b)의 a, b중에 2개를 뽑을 확률 x 뒤 (a, b)의 a, b중에 2개를 뽑을 경우의수 = 4이고
• 그에 대한 경우의 수들은 {aa, ab, ba, bb}이다. (순서는 상관 없다)

 

3. 한발 더 나아가기

• $(a+b)(a+b)(a+b)$는 어떻게 생각할 수 있을까?
• 세개의 (a+b) 중에서 원소를 하나씩 뽑아서 곱한 것들의 총 합이라고 생각 할 수 있다.
• 첫번째 (a+b)에서 2개 x 두번째 (a+b)에서 2개 x 마지막 (a+b)에서 2개 = 8개이다.
• 경우의 수는 {aaa, {aab, aba, baa}, {abb, bab, bba}, bbb}와 같이 정리 할 수 있는데
• 그래서 우리가 알고있는대로 $a^3 + 3a^2b + 3ab^2 + b^3$가 되는 것이다.
• 가장 앞자리는 세개의 (a+b)에서 전부 a만 뽑는 경우, 두번째는 a가 2번 뽑히는 경우,
• 세번째는 a가 1번 뽑히는경우, 그리고 마지막은 a가 0개 뽑히는 경우이다.
• 그리고 a가 3개 뽑히면 b는 자연스레 0개, a가 2개뽑히면 b는 자연스레 1개,
• a가 1개 뽑히면 b는 자연스레 2개,  a가 한개도 안뽑히면 b는 자연스레 3개 뽑히는 경우라는 것이다.
• 즉, $3C3 * a^3b^0 + 3C2 * a^2b^1 + 3C1 * a^1b^2 + 3C0 * a^0b^3$처럼 해석할 수 있다.
• a의 계수는 3개의 (a+b)에서 a를 (3 to 0)개 뽑는 경우, b의 계수는 3 - (a의 계수)이다.

 

4. 일반화하기

• 이제 대망의 $(a+b)^n$가 남았다. 위의 3제곱 항에서 깨달은 것은 가장 첫번째항의 경우는
• n개의 (a+b)에서 a가 n번 뽑힐 경우이고, 두번째 항은 n개의 (a+b)에서 a가 n-1번 뽑힐 경우이다.
• 이걸 정리해보면 $(nCn) * a^nb^0 + (nCn-1) * a^{n-1}b^1 + ... + (nC0) * a^0b^n$이고,
• 합의기호 시그마를 써서 일반화하여 정리하면 아래와 같다.

[그림] 이항정리 공식 유도

 

5. 트리형태로도 풀 수 있다.

[그림] 트리형태로 풀기

• 위와 같이 트리형태로 숫자를 더해서 풀수도 있다.
• 저렇게 하면 n choose (n ~ 0)의 조합의 형태가 나타나게 되기 때문이다.

 

6. 문제 풀기

1) $(2x + 3y)^4 = (4C4) * (2x)^4 * (3y)^0$
                      $+ (4C3) * (2x)^3 * (3y)^1$
                      $+ (4C2) * (2x)^2 * (3y)^2$
                      $+ (4C1) * (2x)^1 * (3y)^3$
                      $+ (4C0) * (2x)^0 * (3y)^4$

2) 1~n까지 있는 집합의 원소로 만들 수 있는 부분집합의 개수는?

number of subset of {1, 2, 3, 4, ..., n} = 1이 있는 경우 or 없는 경우 = 2가지
                                                      * 2가 있는 경우 or 없는 경우 = 2가지
                                                      * 3이 있는 경우 or 없는 경우 = 2가지
                                                      *                    ...
                                                      * n이 있는 경우 or 없는 경우 = 2가지 = $2^n$가지 존재

집합을 이용한 풀이법 : 
number of subset of {1, 2, 3, 4, ..., n} = 원소 0개 뽑는 경우 : nC0
                                                     + 원소 1개를 뽑는 경우 : nC1
                                                     + 원소 2개를 뽑는 경우 : nC2
                                                     +                 ...
                                                     + 원소 n개를 뽑는 경우 : nCn

이항정리에서 $(1+1)^n = nC0 + nC1 + ... nCn$이고, $(1+1)^n = 2^n$이 됨.

 

7. Reference