많은 사람들이 ‘합의 법칙’과 ‘곱의 법칙’에 대해 한 번은 들어보았을 것이다. ‘합의 법칙’과 ‘곱의 법칙’은 조합의 기초가 되는 이론 중 하나이다. ‘조합’은, 간단히 말해서, 경우의 수를 세는 다양한 방법을 제시하는 학문이라고 할 수 있다. 물론, ‘비둘기집의 원리’ 등도 조합의 이론들 중 하나이지만, 경우의 수를 세는 방법은 아니다. 하지만, 전체적으로 보면, 이렇게 조합을 정의할 수 있다. 이 글에서는, 조합에서 학습하는 다양한 이론들에 대해 논의해 보겠다.
먼저, 조합론에서 가장 먼저 학습하는 것은, 순열(Permutation)과 조합(Combination)이다. 순열은 n개의 물체 중에서 r개를 뽑아 순서대로 나열하는 방법의 수이다. 조합은 n개의 물체 중에서 r개를 뽑는 방법의 수이다. 즉, 순열과 조합의 차이점은 ‘순서’이다. 순열 nPr=(n)!/(n-r)!이며, 조합 nCr=(n)!/(n-r)!r!이다.(이 때, x!은 1부터 x까지의 모든 자연수를 곱한 값이다.) 이 공식들을 간단히 증명해 보겠다. n개의 물체 중에서 r개를 뽑아 1번 칸, 2번 칸, ---, r번 칸에 나열하는 상황을 생각하자. 1번 칸에 나열할 수 있는 물체의 종류는 n개, 2번 칸에 나열할 수 있는 물체의 종류는 (n-1)개, ---, r번 칸에 나열할 수 있는 물체의 종류는 (n-r+1)개이므로, 곱의 법칙에 의해 앞에서 언급한 공식이 도출된다. 순서를 고려하지 않는 경우, r!개의 순열은, 조합에서 1개로 counting되므로, nCr=(nPr)/r!이다. 그래서, 앞에서 언급한 공식이 도출되는 것이다.
다음으로, ‘비둘기집의 원리’가 있다. ‘비둘기집의 원리’는 n개의 비둘기집에 (n+1)마리 이상의 비둘기를 넣을 때, 2마리 이상의 비둘기가 들어가는 비둘기집이 적어도 1개는 존재한다는 것이다. 비둘기집의 원리를 활용하여 해결할 수 있는 대표적인 문제는 다음과 같다. ‘점 6개로 이루어진 완전그래프의 각 변을 붉은색 또는 푸른색으로 칠할 때, 이 그래프에 세 개의 변의 색이 모두 같은 삼각형이 반드시 존재함을 보여라‘는 문제이다. 이 문제는 다음과 같이 해결할 수 있다. 임의의 한 점 A를 생각할 때, 비둘기집의 원리에 의해 A와 연결된 5개의 변 중 같은 색(붉은색)으로 칠해진 3개의 변이 반드시 존재한다. 이 3개의 변을 AD, AE, AF라 할 때, 변 DE, EF, FD가 모두 푸른색으로 칠해져 있으면 증명이 완료되고, 변 DE, EF, FD 중 1개라도 붉은색으로 칠해져 있으면 그 변의 양끝점과 점 A로 이루어진 삼각형을 생각하면, 증명이 완료된다.
또한, 점화식이 있다. 많은 사람들이 ‘피보나치 수열’에 대해 한 번은 들어보았을 것이다. 피보나치 수열 {F_n}은 F_1=1, F_2=1, F_(n+2)=F_(n+1)+F_(n)으로 주어진다. 처음 몇 개의 수를 나열해 보면 1,1,2,3,5,8,13,21,34---와 같다. 즉, 점화식은 수열에서 수들 사이의 관계를 나타낸 식이고, 점화식을 풀면 일반항을 구할 수 있다. ‘특성 방정식’을 이용하면 피보나치 수열의 일반항을 구할 수 있다.
뿐만 아니라, 생성함수가 있다. 생성함수를 이용해 경우의 수를 세는 방법은, 어떤 수열 {a_n}의 수들을 계수로 하는 다항식을 생각한 후, 다항식의 계수를 이용해 경우의 수를 구하는 방법이다. 예를 들어, 물체 9개를 1개 이상 4개 이하의 물체를 담을 수 있는 3개의 상자에 나누어 담는 방법의 수는, 다항식 (x+x^2+x^3+x^4)^3의 x^9의 계수와 같다.
마지막으로, 그래프 이론이 있다. 그래프 이론은 어려운 조합 문제를 해결하는데 많이 활용되며, 주어진 문제 상황을 점과 선을 이용해 그래프로 나타낸 후, 문제를 해결하는 방법이다. 그래프를 이용해 문제를 해결할 때 자주 이용하는 사실 중 하나는, 각 점의 차수(degree)의 합은 짝수라는 것이다.(이 때, 점 A의 차수는, 점 A에 선으로 연결된 점의 수를 의미한다.)
지금까지 조합 문제 풀이에 활용하는 다양한 이론들에 대해 논의하였다. 지금까지 언급한 조합의 기본 이론들을 충분히 익히고, 다양한 조합 문제 해결에 조합 이론들을 이용해 보려고 노력한다면, 수학 실력을 더 향상시킬 수 있을 것이다.
HOME > 
