1.7 분배문제

중복조합에 대한 새로운 시각

'중복조합의 수' $H(n,r)$은 다음 방정식
   $x_1 + x_2 + \cdots + x_n = r$
을 만족하는 음이 아닌 정수쌍의 개수와 같다. 

 

H(3,4)의 경우에 대하여 생각해 본다.

   $x_1 + x_2 + x_3 = 4$
를 만족하는 음이 아닌 정수쌍들을 구해보자. 만일 그중의 하나가
   $(x_1, x_2, x_3) = (2, 0, 2)$
이면 이것은 1, 1, 3, 3에 대응한다.  이 관계는 일대일 대응이다.

 

그럼, 위의 방정식을 만족하는 정수쌍의 개수를 어떻게 구할 수 있을까?

동일한 4개의 공을 세 개의 서로 다른 상자
   $x_1, x_2, x_3$
에 분배하여 보자. 첫 번째 상자 $x_1$에 2개, 두 번째 상자에 $x_2$에 0개, 세 번째 상자 $x_3$에 2개를 넣는다면
   (2, 0, 2)
의 순서쌍을 얻는다.

이것은 결국 '분배의 문제'와 관련이 있다.

 

4개의 동일한 공을 세 개의 서로 다른 상자에 분배하는 것을 다른 각도에서 보면 상자1, 상자2, 상자3을 중복을 허용해서 4번 선택하는 것과 동일하다. - 이것은 우리가 이미 논의한 '중복조합'의 경우이다. 

---

분배 문제

서로 다른 $n$개의 상자에 $r$개의 대상들을 특정한 조건을 만족하도록 분배하는 방법의 수를 구하려 한다. 이 문제는 $r$개의 대상들이 (1) 서로 다른 경우와 (2) 동일할 경우로 나누어 생각할 수 있다:

 

(1)의 경우 ;

 

각 상자에 대상들을 최대 하나씩만 담을 수 있다면 분배하는 방법의 수는
   $P(n,r)$ ; 순열의 수
이다. 만약 각 상자에 담을 수 있는 개수의 제한이 없다면 r개의 대상들을 분배하는 방법의 수는
   $\Pi(n, r)$ ; 중복순열의 수
이다.  위의 경우들은 모두 r개의 대상들 입장에서 선택 가능한 상자의 개수에 대해 '곱의 법칙'을 활용한 결과이다.

좀 더 복잡한 상황을 연출하자.

만약, 각 상자에  담을 수 있는 대상의 개수의 제한이 없고 각 상자 안에서 대상들이 배열되어 있는 순서에 따라 다르게 셈하는 경우에 대해 생각해 보자. 이 경우 $r$개의 서로 다른 대상과 함께 $(n-1)$개의 칸막이(/)가 필요하다. 따라서 이것은 '같은 것을 포함하는 순열'의 원리를 적용하여 계산 가능하므로 구하는 방법의 수는

   $P(n-1+r ;  n-1,1,\cdots,1)$, (단, $1$이 $r$개) ; 같은 것을 포함하는 순열의 수

이다. 이것의 최종 계산 결과는
   $P(n-1+r,r)$
으로 표현된다. 스스로 계산해보기 바란다!

 

이 문제를 해결하는 다른 방법도 있다. 

대상 $1$은 $n$개의 상자 중 어느 곳에나 놓일 수 있다. 이때, 대상 $2$가 놓일 자리는 $(n+1)$개이고, 대상 $3$이 놓일 자리의 수는 $(n+2)$개가 존재한다(why?).

 

이와 같은 과정을 반복할 수 있으므로 이 경우에 생성되는 배열의 가짓수는 '곱의 법칙'에 의해
   $\displaystyle n\times (n+1)\times (n+2)\times \cdots \times (n+(r-1)) = \frac{(n-1+r)!}{(n-1)!}$
이고, 이것은 $P(n-1+r,r)$과 같다.

(2)의경우 ;

 

만약 각 상자에 최대 한 개의 대상만 담을 수 있다고 하면, $r$은 $n$ 보다 작거나 같다. 이 경우 분배의 방법과 서로 다른 $n$개의 상자들 중 $r$개를 고르는 방법 사이에 일대일 대응이 존재한다. 그러므로 이 경우 분배하는 방법의 수는
   $C(n,r)$ ; 조합의 수
이다.만약 각 상자에  담을 수 있는 대상의 개수의 제한이 없다면, 이 경우 분배의 방법의 수는
   $x_1 + x_2 + \cdots + x_n = r$
을 만족하는 음이 아닌 정수쌍의 개수이다. 그리고 $x_i$는 $i$번째 상자에 들어가는 대상의 개수이다. 따라서 이 경우, 분배하는 방법의 수는
   $H(n,r)$ ; 중복조합의 수
이다.

우리는 1장에서 기초적인 Counting 원리를 알아보았다. 고교시절에 학습한 '경우의 수'와 관련된 개념의 전부이기도 하다. 기호가 주는 간결성은 수학의 개념을 기술하는데 매우 탁월하지만 그 의미나 표현을 정확하게 이해하지 못하고 사용하면 복잡하고 어려운 것이 된다. 고교 수학 수준의 '경우의 수'에 관한 문제 해결은 대부분 사건의 분할이나 대상의 분류, 합의 법칙, 곱의 법칙만으로도 해결 가능하다.

 

'경우의 수'의 문제를 해결하는 가장 중요한 요소는 셈하는 사람의 재치이다. '셈하는 방식'의 창의성이 바로 조합론의 역사이자 존재의 의미다.