5.2 집합의 분할

원소의 개수가 유한개인 집합을 공집합이 아니고 서로소인 몇 개의 부분집합으로 나누는 것을 '집합의 분할'이라 한다.

 

원소의 개수가 $n$인 집합을 $k(1\leq k\leq n)$개의 부분집합으로 분할하는 방법의 수를 $S(n,k)$와 같이 나티내자. 이때 원소의 개수가 $n$인 집합을 분할하는 모든 방법의 수 $s(n)$는

   $s(n) = S(n,1) + S(n,2) + \cdots+ S(n,n)$

이다.

$S(n,k)$는 서로 다른 $n$개의 공을 서로 같은 상자 $k$개에 빈 상자가 없도록 넣는 방법의 수와 같다. 

---

두 자연수 $n,k(1<k<n)$에 대하여 다음 규칙이 성립한다.

   $S(n,k) = S(n-1,k-1) + k\cdot S(n-1,k)$

 

이것을 증명해 보자. 

집합 $\left\{1,2,3,\cdots,n-1,n\right\}$의 $k-$분할에 대하여 다음 두 가지로 나누어 생각할 수 있다.

   ⑴ 원소 $n$만으로 한 개의 부분집합을 이루는 경우

   ⑵ 원소 $n$이 다른 원소와 함께 한 개의 부분집합을 이루는 경우 

 

(1)의 경우는 $\left\{1,2,3,\cdots,n-1\right\}$의 $(k-1)-$분할만 생각하면 된다. 이 경우의 수는 

   $S(n-1,k-1)$

이다.

(2)의 경우는 $\left\{1,2,3,\cdots,n-1\right\}$을 $k-$분할한 다음, 이러한 $k$개의 부분집합 중 어느 하나에 원소 $n$을 넣으면 되고, 이 경우의 수는

   $k\cdot S(n-1,k)$

이다. (1), (2)에서 합의 법칙에 의해 주어진 식은 성립한다.