분할과 분배 Pt.1

다음글

분할과 분배는 기본적으로 전체를 여러개의 소부분으로 나누는 문제이다. 이를테면 $n$개의 과제를 $k$명이 나눠가지는 경우의 수이다. 분할과 분배는 종류에 따라 8가지로 나뉜다. 공을 상자에 나눠담을 때 1.공을 구분할 수 있는가 2.상자를 구분할 수 있는가 3.빈상자가 있어도 되나이다. 이 8개의 조건이 모여 총 8개의 부분경우를 만든다.

이 글에서는 이중 4가지만을 다루겠다.

---

공을 구분할 수 있고, 상자를 구분할 수 있는 경우

$n$개의 구분되는 공을 $k$개의 구분되는 상자에 넣는 경우를 본다.

만일 빈 상자를 허용하는 경우, $n$개의 공은 각각 $k$개의 상자로 들어갈 수 있으며, 이는 각각의 공이 $k$개의 선택지를 가지고 있음을 말한다. 즉, 곱의 법칙에서 $k^n$임을 알 수 있다.

공과 상자를 구분할 수 있을 때, 빈상자를 허용하여 $n$개의 공을 $k$개의 상자에 넣는 경우의 수=$k^n$

한편, 빈 상자를 허용하지 않는 경우, 앞서 구한 경우에서 빈상자가 있는 경우를 빼야 한다. 즉, 빈상자를 허용하여 분할하는 경우에서 빈상자가 1개라도 생가는 경우를 빼야 한다. 만일 상자가 3개라면 전체경우는 $3^n$가지이고, 1개 이상의 상자(1개가 아니다!)를 비웠을 때 경우의 수는 $2^n$가지, 2개 이상의 상자를 비웠을 때 경우의 수는 $1^n$가ㅣ이다.

따라서 3개의 상자에 $n$개의 공을 빈상자 없이 분할하는 방법은 $3^n-_3 C_2 \times 2^n + _3 C_1 \times 1^n$$=3^n-3 \times 2^n + 3$가지이다.

경우의 수를 $T(n, k)$가지로 하여 이를 더 일반화하면 다음과 같다.

공과 상자를 구분할 수 있을 때, 빈상자를 불허하여 $n$개의 공을 $k$개의 상자에 분할하는 경우의 수
$T(n, k)=k^n-(_kC_{k-1} \times (k-1)^n)$$+(_kC_{k-2} \times (k-2)^n)$$-\cdots+{(-1)^{k-1}}{}_kC_{1}\times 1^n$

---

공을 구분할 수 없고, 상자를 구분할 수 있는 경우

$n$개의 구분되지 않는 공을 $k$개의 구분되는 상자에 넣는 경우이다.

빈상자를 허용하는 경우 $k$개의 상자에 각각 들어가는 공의 개수를 $x_1, x_2, \cdots x_k$이라고 하면 $x_1+x_2+\cdots+x_k=n$이다. 이 식을 좌변에 $n$번 1을 더할건데 각 경우에 대해 $x_1$에 더할지, $x_2$에 더할지... 이렇게 생각하면 $k$개중 $n$개를 중복을 허용해서 뽑는 경우이다. 즉, $_k H_n=_{n+k-1}C_n$과 대응된다.

공을 구분할 수 없고, 상자를 구분할 수 있을 때, 빈상자를 허용하여 $n$개의 공을 $k$개의 상자에 넣는 경우의 수=$_k H_n$

만일 빈 상자를 허용하지 않는 경우, $x_i \geq 1$, $(1 \leq i \leq k)$이다. 이때 $x_i'=x_i-1$으로 한다면 $x_1+x_2+\cdots+x_k$$=(x_1'+1)+(x_2'+1)$$+\cdots+(x_k'+1)=n$, $x_1'+x_2'+\cdots+x_k'=n-k$이여서 중복조합을 사용하면 다음과 같음을 알 수 있다.

공을 구분할 수 없고, 상자를 구분할 수 있을 때, 빈상자를 불허하여 $n$개의 공을 $k$개의 상자에 넣는 경우의 수=$_k H_{n-k}$

참고로 $a_1+a_2+\cdots+a_n=k$이고 $a_i$가 0또는 자연수일 때 가능한 $(a_1,\:a_2,\cdots,a_n)$의 개수는 $_n H_k$임은 굉장히 자주 쓰이는 조합적 아이디어이므로 반드시 기억해놓자.