조합 = 전체가 같은 것이 있는 순열

조합 = 전체가 같은 것이 있는 순열

본문은 도서 내용의 일부임

같은 것이 있는 순열을 배웠다면, 이제 조합(Combination)에 대한 이야기를 할 수 있다.

 

(같은것이없는)순열 → 같은것이있는순열 → 조합

 

이 순서대로 공부하고 있는 것이다. ‘같은 것이 있는 순열’은 ‘일부’ 같은 것이 있기 때문에 이들끼리 자리를 바꾸는 경우를 1가지 경우로 만들기 위해 ‘같은 것끼리 배열하는 경우’를 나누어주었다.

지금부터 이야기할 조합은 사실 같은 것이 있는 순열의 확장판이라고 생각하면 된다. 먼저 조합의 정의를 살펴보자.

 

순열 : 서로 다른 n개 중 | r개를 택하여 |일렬로 나열하는 | 방법의 수

조합 : 서로 다른 n개 중 | r개를 택하는 | 방법의 수

 

이 둘의 차이가 무엇일까? 바로 순열은 `일렬로 나열‘하지만 조합은 일렬로 나열하지 않는다는 것이다. 일렬로 나열한다는 말은 ’순서가 다르면 다른 경우로 본다‘는 뜻이고, 일렬로 나열하지 않는다는 것은 ’순서가 달라도 같은 경우로 본다‘는 뜻이 된다.

 

처음 제시한 사례를 가지고 설명해보면,

이 숫자를 이용하여 세 자리 정수를 만든다고 하면 이것은 ‘순열’ 문제이다. 왜냐하면 ‘순열’의 정의가 말해주듯이 서로 다른 5개 중(1 2 3 4 5) 3개를 택하여(가령 3, 4, 5) 일렬로 나열(345 354 435 453 534 543)하는 방법인 것이다.

물론 3개를 택하는 방법은 3,4 5말고도 더 많이 있다. 이 모든 경우가 ‘순열’인 것이다.

일렬로 나열하는 60가지가 된다. 이를 기하학적으로 해석해보면

왼쪽 직사각형은 가로의 길이가 1, 세로의 길이가 10,

오른쪽 직사각형은 가로의 길이가 6, 세로의 길이가 10 으로 해석할 수 있다.

왼쪽 직사각형이 바로 ‘조합’의 경우의 수이고 오른쪽 직사각형이 ‘순열’의 경우의 수이다. 그렇다면 조합을 구하는 방법에 대한 열쇠를 찾을 수 있다.

순열을 구한 다음에 가로의 길이(일렬로 배열하는 경우)를 나누어 조합으로 만드는 것이다.

순열은 3단계를 거치고 조합은 2단계를 거치는데,

①, ②, ③ 과정을 모두 거치는 것이 ‘순열’이고

①, ②, ③ 과정을 모두 거친 후 ③과정을 제거하는 것이 ‘조합’이다.

 

즉, 조합은 뽑기(택하기)만 할 뿐 순서(나열)는 고려하지 않기 때문에

1 2 3 4 5 중 3개의 숫자를 택하는 경우만 찾는 것이 조합이다.

여기서 확실히 알 수 있는 것은 이 경우 ‘조합의 경우 < 순열의 경우’ 라는 것이다.

 

이쯤에서 조합(Combination)의 수학 기호를 소개하겠다.

그럼 계산은 어떻게 할까? 조합의 풀이공식은 다음과 같다.

이 공식이 무엇을 의미하는 것일까? 왜 _nP_r이 나오며 r!로 나누는 것일까?

1 2 3 4 5중 3개를 택하여 일렬로 나열하는 ‘순열’을 구하는 과정을 다시 살펴보면,

가령 1 2 3 4 5중에서 2, 3, 5를 택했다고 하자. ‘순열’의 입장에서 바라보면 순서를 고려하므로 일렬로 나열하는 235 253 325 352 523 532라는 6가지 경우의 수가 나오지만, ‘조합’의 입장에서 바라보면 순서는 상관없으므로 235 253 325 352 523 532 모두 같은 경우로서 1가지 경우밖에 되지 않는다. 조합은 2와 3와 5를 선택했다는 사실만 중요하기 때문이다. 그렇다면 조합을 구하는 것은 순열의 경우를 구하는 것에서 ③단계를 취소시키는 것이다. 항상 3개를 일렬로 나열하는 방법의 수는 3! = 6(가지)이므로 6으로 나누는 것이다.

따라서 서로 다른 5개 중에서 3개를 택하는 방법의 수 (조합)는

이와 같은 식이 된다는 것을 알 수 있다. 분모에 3! = 6 을 나누는 이유는 일렬로 배열하는 경우의 수인 6가지 경우를 나누어 오로지 택하는 경우(조합)를 보겠다는 의미가 담겨있다.

 

 

따라서 조합 공식의 풀이식에서 분자의 _nP_r은 ①,②,③단계를 모두 거친 다음 r!로 나누어 ③단계를 취소시키는 식인 것이다.

이 식의 양변에 r!를 곱하면 ‘순열’과 ‘조합’이 일렬로 배열하는 부분에서 차이가 남을 확연히 알 수 있다.

즉 nCr × r!이 바로 _nP_r의 설명인 것이다.

 

그럼 이제 1 2 3 4 5에서 3개를 택하는 방법의 수를 조합 공식을 통해 구해보자.

이고 5P3 = 5 × 4 × 3 = 60이고 3! = 3 × 2 × 1 = 6이므로

가 된다. 3!으로 나누는 것은 ₅P₃에서 일렬로 나열하는 행위를 지우는(되돌리는) 것과 같다.

 

 

조합과 ‘같은 것이 있는 순열’과의 어떤 공통 고리가 있다.

‘같은 것이 있는 순열’은 처음에는 모두 다른 것처럼 취급하여 전체를 일렬로 나열한 다음, [같은 것끼리 나열된 것]을 나누어 순서를 없애는 것이고, 조합은 전체 혹은 일부를 나열한 다음, [선택된 것들이 나열된 것]을 나누어 순서를 없애는 과정이 포함된 것이다. 둘 다 모두 배열하는 경우의 수를 나눗셈에 의해 제거하는 것이다.

본문은 도서 내용의 일부임.