1.3 순열과 조합

어떤 사건이 일어날 방법의 수를 보통 '경우의 수'라고 하는데 고교시절의 학습을 통해 우리는 '경우의 수'에 관한 문제를 해결하는 것은 곧 '순열과 조합'을 사용하는 것으로 생각하는 경우가 대부분이다. 분명히 말하지만 '순열과 조합'은 '경우의 수'의 문제 중 아주 특별한 사건을 셈하는 방법일 뿐이다. '경우의 수'의 문제를 해결하는 방식은 다양하며, 기발한 재치와 아이디어가 요구된다.

 

무엇보다도,

'Counting(셈하기)'에 있어서 모든 대상을 빠짐없이 낱낱이 헤아리는 것이 중요하다.

하지만 하나하나 일일이 헤아리는 것은 헤아려야 할 대상의 단위가 커지면 부담스러운 일이다. 인간의 인내심이 한계에 도달하면 모든 것이 뒤죽박죽 되고 수학 학습자에게 '경우의 수'의 문제는 늘 달갑지 않은 종목이다.

빠짐없이 낱낱이 헤아리면서도 힘겹지 않게 효과적으로 어떻게 헤아릴 수 있을까? 

이것이 조합론의 주된 주제이자 관심사다. 여기서 '힘겹지 않게'라는 말은 수학에서 '조직적으로', '구조적으로'라는 말과 일맥상통한다. 논리와 체계를 갖춘 질서 정연한 구조체는 이해하거나 사용하기에 편리하다.

 

순열과 조합은 조건을 조금씩 다르게 하면 여러 형태로 구분된다:

 

원순열, 중복순열, 중복조합, 서로 같은 것을 포함하는 순열, 분배문제 등이 그러하다. 

 

이와 같은 기초적인 Counting 기법에 대해 알아보기 전에, 경우의 수를 구하는 문제를 해결하기 위해 우선적으로 생각하여야 할 것은 셈하려는 대상 즉, 주어진 전체 사건을 작은 사건들로 적절하게 분할하거나 대상들을 적절하게 몇 가지 범주로 분류하는 것이다.  그다음 그것들의 각각을 효과적으로 헤아린 한 후 위에서 언급한 두 가지 기본 원리를 활용함으로써 전체를 셈하는 것이 기초적인 수순이다. 어쩌면 적절하게, 효과적으로 라는 말은 꽤나 난해하고 때로는 학습자에게 책임을 전가하는 용어라는 생각이 든다. 이것은 경우의 수와 관련된 문제들을 풀며 생각을 모방하고, 기발한 아이디어를 고민하는 과정을 통해 감각이 터득되는 일이기도 하다. 그러나 기본적으로 누구나 접근 가능한 생각의 틀을 제공함으로써 학습자의 의욕을 자극시키고 언젠가 더 향상된 추론과 분석 과정을 통해 그 틀에서 자유롭게 되기를 바란다.

 

---

순열과 조합

서로 다른 $n$개의 대상에서 $r$개를 선택하여 순서 있게 일렬로 나열하는 경우의 수를 '순열'이라 한다. 간단한 예로 숫자

$1, 2, \cdots, n$을 중에서 $r$개를 선택하여  일렬로 나열하는 경우의 수를 생각하면 된다. 이때, 이 값을

   $P(n,r)$

이라고 하자. 여기서 $r$은 $n$보다 작거나 같다. 이 기호에 대해 지금 너무 신경 쓸 필요는 없다. 단순히 순열의 수를 표현한 값으로 여기자. 나중에 확인하겠지만, 이 값은 분명 '곱의 법칙'에 의해 쉽게 계산된다. 이제 순열의 경우에서 '순서 있게 일렬로 나열하는'이란 조건을 제외시키면 '조합'이 된다. 다시 말하면, 서로 다른 $n$개의 대상에서 $r$개를 선택하는 경우의 수가 바로 '조합'인 것이다. 이 값을

   $C(n,r)$

이라 하자.

 

 

주어진 대상을 셈하기 위해서는 대상들 사이에 분명한 차이가 존재해야 한다.

그렇지 않으면  우리는 그것들을 다르게 구별할 수 없다. 조합론의 세상에서 일관성 쌍둥이는 서로 구분할 수 없는 존재로 인식된다. 이때 둘이 아니라 하나로 헤아려진다. 각 대상들은 한 사건 속에 속하는 공통의 속성을 가지지만 대상들끼리 반드시 구별됨이 존재한다. 따라서 다르게 구별할 수 없는 대상들은 하나로 취급하여 셈하여야 한다. 다음 그림에서 경로 문제를 생각해 보자:

 

한번 지난 길은 다시 지날 수 없고 (1) 갈림길에서 위쪽과 우측 길만 허용된 경우와 (2) 위쪽과 우측, 그리고 아래쪽 길도 허용된 경우, 점 $\rm A$에서 출발하여 점 $\rm B, C, D$에 도착하는 길잡이 수를 구한다. 

(1)의 경우, 점 B, C, D에서의 길잡이 수가 각각 3, 2, 1가지로 모두 다르지만

(2)의 경우는 모두 3가지로 같다.

따라서 (2)의 경우는 점 $\rm B, C, D$를 하나의 점으로 취급하여 생각하는 것이 좋다. 같은 대상들이 시각적으로 다른 것처럼 분리되어 있을 때, 우리의 뇌는 다른 것으로 착각을 일으키기 쉽다. 고려하지 않아도 될 상황에 집착하게 된다. 인생도 그렇지만 가장 중요한 것, 구별된 것을 남겨야 한다.

 

우리는 '경우의 수'를 구하는 문제를 풀 때, 흔히 셈하고자 하는 대상들 사이의 차이를 명확히 식별하지 못하여 더 헤아리거나 덜 헤아리는 오류를 범하기 쉽다.

---

우리는 이미 순열의 수 $P(n,r)$를 알고 있다고 가정하고, 조합의 수 $C(n,r)$을 구할 것이다. 순열과 조합의 차이점은

"순서를 고려하느냐, 하지 않느냐."

이다. '순열'에서 순서를 고려하지 않을 때, 서로 구별되지 않는 대상들을 하나의 묶음 속에 두기로 하자. 각 묶음 속에는 '곱의 법칙'에 의해 정확히

   $r!$

개의 대상들을 포함(why?)하며, 이것들은 '조합'에서 구별되지 않는 동일한 것으로 취급된다. 이제

이 묶음들의 수를 셈하면 그것이 바로 조합의 수이다.

이것은 간단한 초등 나눗셈 계산에 지나지 않는다. $\displaystyle C(n,r) = \frac{P(n,r)}{r!}$

 

이제, 순열의 수  $P(n,r)$를 계산해 보자.

첫 번째 선택은 $n$가지,

두 번째 선택은 $(n-1)$가지,

세 번째 선택은 $(n-2)$가지, ......,

그리고 $r$ 번째 선택은 $(n-r+1)$가지 방식이 존재한다. 이것은 일련의 연속된 사건들이다. 따라서 '곱의 법칙'에 의해 다음과 같다. 

 

   $\displaystyle P(n,r) = n\times(n-1)\times\cdots\times(n-r+1)=\frac{n!}{(n-r)!}$

 

여기서 $n! = n\times(n-1)\times(n-2)\times\cdots\times2\times1$이다.