[조합론] 1. 조합론의 정의와 여러가지 증명방법

[조합론] 1. 조합론의 정의와 여러가지 증명방법

조합론(combinatorics)은 특정 성질을 만족하는 이산(discrete)적 대상의 존재성과 세기(헤아림, counting), 최적의 대상 찾기 등을 다루는 분야이다.

다음의 문제들은 조합론과 관련된 문제이다.

-10명의 사람들이 각자 자기 이름이 적힌 쪽지를 봉투에 넣고, 쪽지를 하나씩 뽑는 방법의 수는 \(10!\)이다.

이때 10명의 사람들 중 어느 누구도 자신의 이름이 적힌 쪽지를 뽑지 않는 방법의 수는?(교란수)

-15명의 학생들이 7일 동안 매일 3명으로 이루어진 5개의 조를 이루어서 협동과제를 수행하는데 어떤 두 학생도 정확히 한번 같은 조에 편성되어 공동과제를 수행하도록 7일간 조편성이 가능한가?(존재성), 만약 가능하다면 몇가지 경우가 있는가?(헤아림), 이러한 조편성을 어떻게 할 수 있는가?(알고리즘)

여러가지 증명방법

연역적 증명(deduction, 3단 논법)

연역적 증명은 다음의 단계를 거쳐서 증명하는 증명방법이다.

(1) 가정의 단계(\(p\)): 문제의 조건 등 이미 알려진 사실을 서술하는 단계.

(2) 추론의 단계(\(q_{1},\,\cdots,\,q_{n}\)): 이미 알려진 사실들을 기반으로 새로운 사실을 유도하는 과정.

(3) 결론의 단계(\(r\)): 가정의 단계와 추론의 단계에서 얻어진 사실들을 정리해서 답을 유도하는 단계.

위의 3가지 단계는 \(p\,\Rightarrow\,q_{1}\)이고 \(q_{1}\,\Rightarrow\,q_{2},\,\cdots,\,q_{n-1}\,\Rightarrow\,q_{n},\,q_{n}\,\Rightarrow\,r\), \(p\,\Rightarrow\,r\)를 이용하여 \(p\,\Rightarrow\,r\)을 보이는 방법이고, \(q_{1},\,\cdots,\,q_{n}\)은 추론과정을 통해서 얻어지거나 이미 알려진 사실(공리, 정의, 다른 증명된 이론)들이다.

예: 삼각형의 두 변의 길이가 같으면, 두 밑각은 서로 같다.

증명: 같은 변을 이웃하고 있는 꼭짓점으로부터 그 대변의 중점을 연결하는 보조선을 그리자.(아래 그림 참고)

보조선으로 인해 두 삼각형이 만들어지고, 이 두 삼각형은 SSS합동이므로 따라서 대응되는 두 밑각은 같다.

예: 2 이상의 자연수 \(n\)에 대하여 \(n^{4}+4\)는 2보다 큰 두 자연수의 곱으로 나타낼 수 있다.

증명:$$\begin{align*}n^{4}+4&=(n^{4}+4n^{2}+4)-4n^{2}\\&=(n^{2}+2)^{2}-(2n)^{2}\\&=(n^{2}+2n+2)(n^{2}-2n+2)\end{align*}$$이고, \(n\geq2\)이므로 \(n^{2}\geq4,\,n-1\geq1,\,(n-1)^{2}\geq1\)이고$$\begin{align*}n^{2}+2n+2&\geq4+4+2=10\\n^{2}-2n+2&=(n-1)^{2}+1\geq1+1=2\end{align*}$$이므로 따라서 \(n^{4}+4\)는 2보다 큰 두 자연수 \(n^{2}+2n+2\)와 \(n^{2}-2n+2\)의 곱으로 나타낼 수 있다.

귀류법(proof by contradiction)

명제 \(p\,\Rightarrow\,q\)가 참임을 보이기 위해 \(p\)와 \(\sim q\)가 동시에 성립하면, \(r\)과 \(\sim r\)이 동시에 성립(모순)함을 보이는 증명방법이다.

예: \(\sqrt{2}\)는 유리수가 아니다.

증명: \(\sqrt{2}\)를 유리수라고 하자. 그러면$$\sqrt{2}=\frac{p}{q}\,(\text{gcd}(p,\,q)=1)$$으로 나타낼 수 있고,$$2=\frac{p^{2}}{q^{2}}$$이므로 \(p^{2}=2q^{2}\)이고 \(p=2k\)로 나타낼 수 있다. 그러면 \(4k^{2}=2q^{2}\)이므로 \(q=2l\)로 나타낼 수 있고 따라서 \(\text{gcd}(p,\,q)\geq2\)가 되는데 이것은 \(\text{gcd}(p,\,q)=1\)이라는 사실에 모순이다. 따라서 \(\sqrt{2}\)는 유리수가 아니다.

예: 소수의 개수는 무한하다.

증명: 소수의 개수가 유한하다고 하고 다음과 같이 \(n\)개 있다고 하자.$$p_{1}(=2),\,p_{2}(=3),\,\cdots,\,p_{n}$$이때$$p=p_{1}\cdots p_{n}+1$$이라고 하면, \(p\)는 \(1\)보다 큰 합성수이므로 적당한 소수 \(p_{i}\)에 대하여 \(p_{i}|p\)로 나타낼 수 있다. 또한 \(p_{i}|p-1\)이므로$$p_{i}|p+(-1)(p-1)=1$$이 되는데 \(p_{i}\geq2\)이므로 모순이다. 따라서 소수의 개수는 무한히 많다.

대우증명법(contrapositive proof)

명제 \(p\,\Rightarrow\,q\)가 참임을 보이기 위해 대우명제인 \(\sim q\)이면 \(\sim p\)(\(\sim q\,\Rightarrow\,\sim p\))가 성립함을 보이는 증명방법이다. 

예: 정수 \(n\)에 대하여 \(n^{2}\)이 홀수이면, \(n\)은 홀수이다.

증명: 본 명제의 대우명제인 "\(n\)이 짝수이면, \(n^{2}\)은 짝수이다"를 보이자. 

\(n\)을 짝수라고 하면 \(n=2k\)로 나타낼 수 있고, \(n^{2}=4k^{2}=2(2k^{2})\)이므로 \(n^{2}\)은 짝수이다.

따라서 \(n^{2}\)이 홀수이면, \(n\)은 홀수이다.

예: 임의의 두 실수 \(x,\,y\)에 대하여 \(x+y\geq2\)이면, \(x\geq1\) 또는 \(y\geq1\)이다.

증명: \(x<1\)이고 \(y<1\)이면, \(x+y<2\)이고 따라서 \(x+y\geq2\)이면 \(x\geq1\) 또는 \(y\geq1\)이다.

귀납적 증명(mathematical induction)

모든 자연수 \(n\)(또는 \(n\geq c\)인 모든 자연수 \(n\))에 대하여 명제 \(P(n)\)이 성립함을 다음의 두 단계를 이용하여 보이는 방법이다.

기본단계: \(n=1\)(\(n\geq c\)인 경우, \(n=c\))일 때, \(P(n)\)이 성립한다.

귀납적 단계: \(n=k\)일 때 \(P(n)\)이 성립한다고 하면, \(n=k+1\)일 때도 \(P(n)\)이 성립한다.

귀납적 증명을 하기 위해서는 이론을 미리 예측해야 한다.(물리 또는 화학 이론의 증명 방법과 비슷하다)

예: 모든 자연수 \(n\)에 대하여 다음의 등식이 성립한다.$$1+3+5+\cdots+(2n-1)=n^{2}$$

증명: 여기에서 \(P(n)\)은 위의 등식이다.

기본단계: \(n=1\)일 때,$$2\cdot1-1=1^{2}$$이므로 \(P(1)\)은 참이다.

귀납적 단계: \(n=k\)일 때, 다음의 등식이 성립한다고 하자.$$1+3+5+\cdots+(2k-1)=k^{2}$$(\(P(k)\)가 참이라고 가정)

위 등식의 양변에 \(2k+1(=2(k+1)-1)\)을 더하면$$\begin{align*}1+3+5+\cdots+(2k-1)+(2(k+1)-1)&=k^{2}+(2(k+1)-1)\\&=k^{2}+(2k+1)\\&=(k+1)^{2}\end{align*}$$이므로 \(P(k+1)\)도 참이다.

따라서 모든 자연수 \(n\)에 대하여 등식 \(1+3+5+\cdots+(2n-1)=n^{2}\)가 성립한다.

예: 5 이상의 모든 자연수 \(n\)에 대하여 부등식 \(2^{n}>n^{2}\)이 성립한다.

증명: 여기에서 \(P(n)\)은 위의 부등식이다.

기본단계: \(n=5\)일 때,$$2^{5}=32>25=5^{2}$$이므로 \(P(5)\)는 참이다.

귀납적 단계: \(n=k\,(k\geq5)\)일 때, 다음의 부등식이 성립한다고 하자.$$2^{k}>k^{2}$$(\(P(k)\)가 참이라고 가정)

위 부등식의 양변에 \(2\)를 곱하면$$2^{k+1}=2^{k}\cdot2>2k^{2}$$이고 \(k\geq5\)이므로$$2k^{2}-(k+1)^{2}=k^{2}-2k-1=(k-1)^{2}-2>0$$이고 \(2k^{2}>(k+1)^{2}\)이므로 따라서$$2^{k+1}=2^{k}\cdot2>2k^{2}>(k+1)^{2}$$이고 \(P(k+1)\)도 참이다.

5 이상의 모든 자연수 \(n\)에 대하여 부등식 \(2^{n}>n^{2}\)이 성립한다.

존재성의 증명(proof of existence)

(1) 직접 만들어서 보임

예: 임의의 실수 \(a\)에 대하여 실수 \(x\)가 존재해서 \(3x-5=a\)이다.

증명: $$x=\frac{a+5}{3}$$이라고 하면, \(x\)는 실수이고, 위 식을 만족한다.

(2) 확률을 이용한 증명

(3) 기타 방법(비둘기집의 원리 등등)

비존재성의 증명은 대우명제 또는 귀류법을 많이 사용한다.

유일성의 증명(proof of uniqueness)

어떤 성질을 만족하는 원소가 하나밖에 없다는 것을 증명하는 방법은 \(a\)와 \(b\)가 주어진 성질을 만족하는 원소이면, \(a=b\)임을 보이는 것이다.

참고자료:

조합론과 그래프이론, 조성진, 김한두, 경문사

조합 및 그래프이론, 김정진, 교우사