1.5 중복순열과 중복조합

이제까지는 주어진 대상이 모두 서로 다른 경우에 배열하거나 선택하는 것에 대해여 생각하였다.

주어진 대상 속에 종류별로 같은 것들을 여러 개 포함하는 경우는 어떻게 셈하여야 할까?

또한

중복을 허용하여 배열하거나 선택하는 것이 가능하다면 어떻게 셈하여야 할까?

 

중복을 허용한다는 것은 같은 대상을 여러 번 선택할 수 있다는 것을 의미한다. 이런 일은 실제 생활에서도 일어난다. 서너 명의 후보에게 다수의 유권자가 투표를 하는 것이 그에 해당한다. 이때 복제된 각각의 후보가 자신을 선택한 유권자와 짝을 이룰 만큼 상당한 양으로 존재한다고 생각해도 좋다. 만일 후보자가  $a, b, c$라면 복제한 $a, b, c$의 수학적 표기는 중복집합

    $\left\{\infty a, \infty b, \infty c\right\}$

로 표현할 수 있다. 이 중복집합으로부터 유권자 수에 해당하는 r명을 선택(중복조합)하거나 배열하는 상황(중복순열)을 연출한다.

---

중복순열과 중복조합

서로 다른 $n$개의 대상에서 중복을 허용하여 $r$개를 순서 있게 일렬로 나열하는 방법의 수를 '중복순열'이라 한다. 이 값을

   $\Pi(n,r)$

라 하자. 이번에도 '곱의 법칙'에 의해 중복순열의 수는 다음과 같음을 쉽게 알 수 있다.

   $\Pi(n,r) = n\times n\times n\times\cdots n = n^r$ ($n$이 $r$개)

여기서 $r$은 $n$보다 커도 상관없다. 그 이유는 매우 단순하여 설명하지 않겠다.

 

중복순열의 경우는 간단히 해결되었지만, 서로 다른 $n$개의 대상에서 중복을 허용하여 $r$개를 선택하는 '중복조합'의 수

  $ H(n,r)$

를 셈하는 것은 앞에서 논의한 방식과 달라 조금 어려울 수 있다.

 

우선, 우리가 논의하고자 하는 서로 다른 대상을 $1$부터 $n$까지의 숫자로 정하자. 그리고 중복을 허용하여  $r$개의 숫자를 뽑을 것이다. 좀 더 부드러운 이해를 위해

$1, 2, 3$이 적힌 $3$개의 공을 중복을 허용하여 $4$개를 선택하는 방법의 수를 생각한다.

중복을 허용한 경우는 각 숫자가 적힌 공이 충분한 양만큼 있다고 생각하며 된다. 물론 조건에서 이 공의 숫자를 제한하여 문제를 제기할 수도 있다. 이처럼 작은 실험으로부터 일반화된 원리를 이끌어 내는 것이 뇌의 부담이 적다. 여기에 약간의

발상의 전환을 시도하자.

실상 이것은 수학적 용어로 '일대일 대응의 원리'라고 하는 것으로 비교적 셈하기 쉬우나 원래 셈하려는 사건과 동등한 의미를 가지는 사건으로 대체하여 생각하는 것이다. 

'일대일 대응'이라는 용어는 '함수'에서 등장한다. 공역과 치역이 같고, 일대일 함수일 때 이 관계를 '일대일 대응'이라고 한다. 짝짓기 프로그램에서 여성을 향한 남성의 사랑의 화살이 겹침 없이 일대일로 완전히 한 쌍씩 이루어진 경우를 생각하면 이해가 쉬울 것이다. 이때, 화살을 던진 남성의 수나 화살을 받은 여성의 수가 같고 일대일 관계이므로 남성의 수를 알기 위해 여성을 헤아려도 된다.

---

숫자가 적혀있지 않은 동일한 4개의 공을 준비하고 여기에 숫자 1, 2, 3을 중복을 허용하여 적절히 기입한다면 우리가 셈하려는 대상이 생성된다. 

이제, 이것들을 효과적으로 헤아릴  수 있는 아이디어를 생각해야 한다.

항상 이 단계가 매우 중요하다!

동일한 4개의 공에 1을 적을 공, 2를 적을 공 그리고 3을 적을 공으로 구별하기 위해서는 칸막이(/)가 필요할 것이다.

칸막이는 2개면 충분하다(왜일까?). 즉, 공 4개와 칸막이 2개

   ●, ●, ●, ●, /, /

이것을 일렬로 나열하였을 때, 그 중 하나가 다음과 같다면

   ● ● / / ● ●

이것은 1, 1, 3, 3에 대응한다. 이것은 일대일 대응이다. 따라서

 

숫자 1, 2, 3에서 중복을 허용하여 4개를 선택하는 중복조합의 수는

   ●, ●, ●, ●, /, /

를 일렬로 나열하는 방법의 수와 같다. 

 

이것은 또한, '같은 것을 포함하는 순열'의 수이다. 이것의 경우의 수는

   $C(6,4)\times C(2,2) = C(6,4)$

이다.

왜일까???

서로 다른 6(=3+4-1)개의 자리에 ○을 놓을 자리를 4개 선택하고,  /를  놓을 자리를 2개 선택하여야 하기 때문이다. 이것을 계산하는 바탕이 되는 기저는 늘 그렇듯이 두 가지 기본 원리 중의 하나 '곱의 법칙'이라는 사실을 기억하자. 그러므로

   $H(3,4) = C(6,4)$

이다. 이것을 일반화하면

   $H(n,r) = C(n+r-1,r)$

임을 알 수 있다. 일반화하는 것은 그리 어렵지 않다. 위의 풀이에서 3을 $n$으로 4를 $r$로 바꾸어 놓으면 된다. 이때 칸막이의 개수는  $(n-1)$개가 필요하다. 그리고 나머지는 같은 방식으로 진행된다. 이것이 전부다. 아주 쉽다!

---

중복순열과 중복조합의 차이점

중복순열과 중복조합의 차이점은 (1) 기명 투표할 경우와 (2) 무기명 투표할 경우에서 명백히 드러난다. 세 명의 선거인이 A, B 두 후보자에게 투표하는 상황에서 (1)과 (2)의 개표 결과에 따라 어떻게 달라지는지 일아보자. (1)과 (2)의 경우 모두 분명 A, B를 중복을 허용하여 세 번 뽑는 경우다.

(1)의 경우, 세 명의 선거인을 x, y, z라 할 때 모든 가능한 투표의 결과를 나열하면 다음과 같다.

   x  y  z

   A  A  A

   A  A  B 

   A  B  A

   B  A  A

   A  B  B

   B  A  B

   B  B  A

   B  B  B

이때 (2)의 경우는 기명 투표에서

   AAB, ABA, BAA

는 어느 경우든 구별되지 않고 A가 2표, B가 1표라는 한 가지 경우만 나타난다. 마찬가지로

   ABB, BAB, BBA

또한 어느 경우든 구별되지 않고 A가 1표, B가 2표라는 한 가지 경우만 나타난다. 위의 (1)의 경우는 A, B의 두 개에서 중복을 허용하여 세 개를 택해 그것을 나열하는 순서까지 생각한 것이다. 그러나 (2)의 경우는 A, B의 두 개의 중복을 허용하여 세 개를 택하되 그것을 나열하는 순서는 생각하지 않으므로 (1)의 경우와 다르다. 

 

순열의 수에서 조합의 수를 추론한 것처럼 중복순열의 수에서 중복조합의 수를 추론할 수는 없을까?

 

위의 예에서도 살펴볼 수 있듯이 중복순열의 대상들 중 중복조합에서 같은 것들을 하나의 묶음 안에  두면 각 묶음 안에 대상들의 수가 모두 일정치 않다. 결국 묶음의 수를 일일이 하나하나 헤아려야 하는 수고를 하게 된다. 이런 수고를 하지 않으려면,

 

생각의 전환이 필요하다. 

 

위의 예에서

중복조합(무기명 투표)의 경우  세 명의 선거인이 모두 동일한 공을 하나씩 가지고 있고, 자신이 투표하기를 원하는 후보자에서 투표하는 행위를 상자 A와 상자 B에 자신의 공을 넣는 것으로 생각하자.

 

앞에서도 얘기했지만 주어진 문제에 대한 상황 묘사는 수학적 사고 실험의 가능하게 해 준다. 그리고 그것이 성공적이라면 수식으로 어떻게 표현할 것인지를 고민하는 것이 수학을 즐기는 방식이다. 발상이 기호화될 때의 짜릿한 순간을 경험해 보자.

 

그러면 상자마다 넣어진 공의 수에 따라 다음의 경우가 발생한다.

   (A,B) = (3,0), (2,1), (1,2), (0,3)

이것을 중복순열(기명 투표)의 경우와 비교해 보자.

   (3,0) ; AAA

   (2,1) ; AAB, ABA, BAA

   (1,2) ; ABB, BAB, BBA

   (0,3) ; BBB

이제 우리는 이러한 순서쌍을 어떻게 찾을 것인가 생각하면 된다! 나중에 설명하겠지만 미리 얘기하면

   $x_1 + x_2 = 3$

을 만족하는 음이 아닌 정수 순서쌍과 동일하다. 여기서 $x_1$은 상자 A에 들어가는 공의 개수, $x_2$는 상자 B에 들어가는 공의 개수이다.

---

H(n,r)을 계산하는 또 다른 방법을 탐구해 보자. 

이미 계산 방법을 알고 있는데 왜? 또!, 굳이, 이런 시도를 해야 할까 의문이 든다면 이 글을 더 이상 읽지 않기를 바란다. 머리만 아플 뿐이다. 수의 계산은 우리보다 컴퓨터가 더 잘하는 영역이다. 우리는 수학적 사고의 영역을 확장하고 논리적인 생각이나 창의적인 생각을 풍요롭게 하려는 것이다. 결과보다는 과정을 중요하게 생각할 때 인생은 풍요롭다. 실패에 대한 아픔도 적다. 그 실패 또한 성공을 위한 과정인 거다.

 

간단히 두 개의 숫자 1, 2에서 중복을 허락하여 세 개를 택하는 방법을 생각하자. 즉 $H(2,3)$의 값 구하려고 한다. 모든 경우를 나열하면 다음 네 가지이다. 

   (1, 1, 1)

   (1, 1, 2)

   (1, 2, 2)

   (2, 2, 2)

크기 순으로 정리하여 표현하였다. 이렇게 한 이유가 있다. 이제, 이것을 셈하는 방법을 고안하자.

 

항상 이 단계가 매우 중요하다!

 

중복된 수들을 서로 다르게 보이도록 하기 위해 첫 번째 수에 0을, 두 번째 수에 1을, 세 번째 수에 2를 더하면 다음과 같다.

   (1, 2, 3)

   (1, 2, 4)

   (1, 3, 4)

   (2, 3, 4)

이것은 곧! 1, 2, 3, 4에서 세 개를 택하는 조합과 같아진다. 즉,

   $H(2,3) = C(2+3-1,3)$

이다. 같은 방법에 의해 일반적으로 다음 관계가 성립한다.

   $H(n,r) = C(n+r-1,r)$