분할과 분배 Pt. 2

이전글

이전글에 이어서 이번 글에서는 나머지 2가지 경우에서 공을 상자에 나눠담는 경우를 생각해 볼 것이다. 이전글에서 이어지는 내용도 일부 있으니 파트 1을 먼저 읽고 오는 것을 추천한다. 이 글에서는 상자를 구분할 수 없는 경우에 대해 알아본다.

---

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

$n$개의 같은 공을 $k$개의 같은 상자에 빈상자를 허용하지 않으며 넣는다고 하자. $i$번째 상자에 들어가는 공의 개수를 $n_i$라고 하면 다음과 같은 식이 성립할 것이다.

$n_1+n_2+\cdots+n_k=n$, 여기서 $(n_i \geq 1)$, $(i=1, 2, 3, \cdots, k)$

즉, $n$을 $k$개의 자연수의 합으로 나타내는 경우의 수와 같으며 이를 $p(n,\:k)$라고 한다.

여기까지 했으면 나머지는 노가다를 하는 것이 좋다. 이때 기준을 세워 노가다를 하면 경우를 빠짐없이 구할 수 있다. 여기서 기준이란 다음과 같다.

상자를 구분할 수 없으므로 일반성을 잃지 않고 $i \geq j$라면 $n_i \geq n_j$라고 하기

예를 들어 $p(5,\:7)$는 다음과 같이 구할 수 있다.

$n_1+n_2+n_3=7$이라고 하며, 일반성을 잃지 않고 $n_1 \leq n_2 \leq n_3$라고 하자.
$n_1=1$인 경우부터 노가다해보면
$(n_1,\:n_2,\:n_3)=$$(1,\:1\:,5),\:(1,\:2,\:4),$$\:(1,\:3,\:3),\:(2,\:2,\:3)$이며, 더이상은 없다. 즉, 4가지이다.

참고로 $p(n,\:k)$에 대해 다음과 같은 성질이 성립하긴 한다.

$p(n,\:k)=p(n-k,\:1)$$+p(n-k,\:2)+\cdots+p(n-k,\:k)$

위 식은 $n$개중 $k$개를 우선적으로 모든 상자에 1개씩 분할해놓고, 나머지 $n-r$개를 1개에, 2개에... r개에 분배하는 경우를 모두 더한 경우와 $n$개를 $k$개에 분할하는 경우는 같음을 이용한 것이다. 하지만, 대부분의 경우 노가다가 훨씬 빠르고, 위 관계식도 시간이 만만치 않게 들어가므로 경우마다 무엇을 쓸지 재량껏 선택해야 한다.

만일 빈상자를 허용하는 경우 간단하게 $p(n,\:1)$부터 $p(n,\:k)$까지 다 더하면 된다. 예를 들어 5개의 공을 3개의 상자에 빈 상자를 허용하여 넣는 경우는 $p(5,1)+p(5,2)+p(5,3)$과 같다.

---

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

$n$개의 공을 위의 조건을 지키며 $k$개의 상자에 빈상자 없이 넣는 경우의 수를 $S(n,\:k)$라고 하며, 이를 제 2종 스털링수라고 한다.

$S(n,\:k)$는 다음의 사실들을 이용해 표를 그려 알아낸다.

• $S(n,k)$에서 $n<k$인 경우는 정의되지 않는다.
  예를 들어 3개의 공을 4개의 상자에 빈 상자 없이 넣는 경우는 불가하기 떄문이다.
• $S(n,n)$은 항상 1이다.
  3개의 구분되는 공을 3개의 구분되지 않는 상자에 넣는다고 가정해보자. 자명하게 1가지밖에 없다.
• $S(n, 1)$은 항상 1이다.
  $n$개의 공을 1개 상자에 몰아넣는 경우, 1가지뿐이다.
• $S(n,k)=S(n-1,k-1)$$+kS(n,k-1)$
  $n$개의 공을 $k$개의 상자에 빈상자 없이 넣는 경우는
  $n$개중 1개의 공을 아무 상자에나 넣고, 나머지 $n-1$개를 $k-1$개의 상자에 마저 분할하는 경우와
  $n-1$개의 공을 $k$개의 상자에 넣고 나머지 1개를 $k$개중 임의의 상자에 넣는 경우와 같다.
  
  

이상의 규칙으로 표를 만들어보면 다음과 같다(가로줄이 $k$, 세로줄이 $n$이며 이 둘의 교점에 적힌 수가 $S(n, k)$이다).

	1	2	3	4	5	6
1	1	-	-	-	-	-
2	1	1	-	-	-	-
3	1	3	1	-	-	-
4	1	7	6	1	-	-
5	1	15	25	10	1	-
6	1	31	90	65	15	1

또한 $p$의 경우와 마찬가지로 빈상자를 허용하고자 하는 경우 예를 들어 $n$개의 공을 $k$개의 상자에 빈상자를 허용하여 분할하려면 $S(n,1)+S(n,2)+\cdots+S(n,k)$와 같다.

그리고 $S(n,k)$와 $T(n,k)$사이에는 다음과 같은 식이 성립한다.

$k!S(n,k)=T(n,k)$

이는 $T(n,k)$는 상자를 구분하지만 $S(n,k)$는 상자를 구분하지 않기 때문이다. $S(n,k)$에 상자를 구분하여 나열하는 경우인 $k!$을 곱해주면 $T(n,k)$가 되는 것이다. 일반적으로 $k$가 조금만 커져도 $T(n,k)$를 이전 글에서 소개한 방법으로 구하는 것은 복잡하므로 지금 설명한 방법이 훨씬 효율적이다.

 

---

활용하기

문제를 통해 이 글의 내용을 활용해보자.

 

1. 낙인찍힌자들의 종착지

이승에서 악업을 많이 쌓아 "낙인"찍힌 망자는 매 1000년간 7개의 지옥중 임의의 1개에서 구형을 받게 된다. 오늘 낙인찍힌 망자 5명이 들어왔을 때, 이들을 7개의 지옥에 나누어넣는 경우의 수를 구하여라.

 

1. 낙인찍힌자들의 종착지
5명의 구분되는 사람들은 7곳의 구분되는 지옥으로 아무 지옥에도 넣지 않는 경우를 포함해서 지옥에 넣는 경우의 수로 $T(n, k)$를 써서 $T(5, 1)+T(5,2)+T(5,3)+T(5,4)+T(5,5)$와 같다. $k$가 5보다 큰 경우는 성립하지 않으므로 생략한다. 여기서 $T(n,k)$의 값을 각각 구해서 다 더해도 되지만 그렇게 하면 시간이 너무 오래 걸리므로 $S(n,k)$를 이용하기로 한다.
위의 표를 보면 $S(5,1)~S(5,5)$의 값을 볼 수 있다. 이를 이용해 각 값을 구하고, $T(n,k)=k!S(n,k)$로 최종 값을 계산하면

	$S(n,k)$	$k!$	$T(n,k)$
$k=1$	1	1	1
$k=2$	15	2	30
$k=3$	25	6	150
$k=4$	10	24	240
$k=5$	1	120	120

그래서 $T(5,k)$의 값을 모두 더하면 총 541가지이다.