* 이항 정리
이항 정리란 이항식의 거듭제곱을 이항 계수로 일련의 단항식들의 합으로 전개하는 정리이다.
위 그림처럼,
( x + y ) 인 이항식을 연속적으로 곱할 때 몇 번 곱했는지 n 만 알 수 있으면 쉽게 해당 식을 전개할 수 있음을 의미한다.
자세히 들여다보면 어느 일정 규칙을 가진 패턴을 보임을 짐작할 수 있다.
이는 전개되는 식에서 n (시그마) k = 0 으로 ( n k ) 조합을 합한 수열로 나타낼 수 있는데
전개될 때의 계수들을 조합으로 알 수 있음을 뜻한다.
( 첫번째 그림에서 마치 열행렬을 나타내는 (n k) 기호는 조합을 의미한다. nCk 와 같은 의미이다. )
이를 '이항 계수' 라고 한다.
* 이항 계수
앞서 설명했듯이,
이항 계수란 이항식을 이항 정리로 전개했을 때 각 항의 계수를 말한다.
가장 중요한 질문은 "왜 이항 계수는 조합과 같은 원리가 사용되어지는걸까 ??" 일 것이다.
먼저,
nCr 의 의미는서로 다른 n 개의 원소에서 순서가 상관없는 r 개를 뽑는 경우의 수와 같다.
여기서
( x + y ) 는 x, y 둘 중 하나를 고르는 선택지이며 이를 확장하면
( x + y )n 에서 n 은 조합에서의 선택할 수 있는 n 개의 원소 의미와 같다.
그렇다면 계수는 어떻게 될까 ??
만약 총 개수 n = 4 라고 가정할 때, x 가 r = 2 개 선택될 수 있는 경우의 수는 4C2 와 같고 이는 곧 해당 항의 계수가 된다.
또, 알 수 있는 사실은
항이 2개이기 때문에 x 가 구해진다면 자동적으로 y 는 x 개 선택한 갯수를 뺀 승이 구해진다.
결과적으로,
x, y 어느 기준으로 전개하던 상관없이 식이 구해진다.
( x + y )3 에서 x 를 2개 선택한 계수와 y 를 2개 선택한 계수가 같은 것을 볼 때 조합의 성질도 간접적을 볼 수 있다.
* 파스칼의 삼각형
이항식을 거듭 제곱한 식들을 아래로 전개한 후, 이항 계수를 살펴보자.
위 그림처럼 이항 계수들만을 떼어놓고 보게되면 규칙적인 수들의 삼각형 모양이 만들어지는데
이를 '파스칼의 삼각형' 이라고 부른다.
파스칼의 삼각형에서 찾아볼 수 있는 여러가지 특성들이 있다.
대표적인 특징들을 살펴보자.
첫번째는 이항식 전개에서 이항 계수의 총합은 2n 이된다는 사실이다.
왜냐하면, 이항식이 ( x + y ) 라고 가정할 때 x 와 y 를 고를 수 있는 상황이 n 번이 존재하기 때문이다.
( 이전에 배운 중복 순열과 같다. )
또 다른 중요한 특징은 아래의 식이 성립한다는 것이다.
nCk = n-1Ck-1 + n-1Ck
우리는 이 식의 의미를 해석해볼 가치가 있다.
단지 "보이는 규칙이 그러해서 혹은 파스칼의 삼각형에서 알 수 있다."
이런식으로 말하는 것보다 이유를 찾는 것이 더 의미있어보인다. 생각해보면 그렇게 어렵지 않다.
먼저 처음부터 살펴보자.
( x + y )1 의 각 항의 계수는 1,1 이 될것이다. 이는 x, y 를 각 상황에서 1번 선택한 상황이다.
( x + y )2 에서 xy 의 계수인 2C1 을 보자.
위 식을 통해 해석하면 2C1 은 앞선 두 가지 상황 ( 1C0, 1C1 ) 의 경우의 수를 합한 결과가 되는데
이는 xy 의 계수는 xy 가 될 수 있는 경우의 수이므로
x 가 선택한 상황에서는 y 를, y 가 선택한 상황에서는 x 를 고르기만 하면 되므로 이는 곧 앞선 ( 1C0, 1C1 ) 인 상황이 된다.
어차피 각각 x, y 를 고르는 선택은 1가지이기 때문이다.
마찬가지로,
( x + y )3 에서 x2y 인 계수인 3C1 인 상황에서도 x2 이 되는 경우의 수에서 y 를 선택하는 상황 ( 2C0 ),
xy 이 되는 경우의 수에서 x 를 선택하는 상황 ( 2C1 ) 을 더한 값이 최종적으로 x2y 계수가 되겠다.
마지막으로 ( x + y )4 의 x2y2 계수를 살펴보면,
x2y 가 되는 경우의 수 ( 3C1 ) + xy2 가 되는 경우의 수 ( 3C2 ) 가 되므로 4C2 라는 결과가 도출된다.
결국, 이항식을 거듭제곱하는 것이기 때문에
x,y 가 선택될 수 있는 2가지 경우의 수를 계속 더해가면서 x, y 로 표현될 수 있는 다항식의 계수를 구할 수 있다.
더 나아가서, 해당 식을 이용해서 코드로 조합을 표현하는 것 또한 굉장히 단순하다.
다만,
조합식을 계산할 때마다 매번 계산해야하는 비효율을 없애기 위해서 부분 문제로 나뉘어질 수 있는 특성을 이용해
'다이나믹 프로그래밍 ( Dynamic Programming, 흔히 DP )' 라고 불리는 개념이 적용해 구현한다.
이는 계산된 결과 값을 메모리에 저장해서 다시 재사용하는 '메모이제이션' 기법을 활용한다.
참고 자료
'수학 > 개념 정리' 카테고리의 다른 글
| [Math]순열 & 조합 (0) | 2023.01.07 |
|---|