집합의 분할

■집합의 분할

 

▶ 집합의 분할의 뜻

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

 

▶ 집합의 분할의 수

원소가 n개인 집합을 공집합이 아닌 k개의 서로소인 부분집합으로 분할하는 방법의 수를 기호로 S(n, k)와 같이 나타낸다. (단, )

 

S(n, k)에서 S는 Stirling number(스털링 수)의 첫글자이다.

 

S(n,1)=1, S(n, n) =1

원소가 n개인 집합을 분할하는 모든 방법의 수는

 

증명) S(n, n－1)은 원소의 개수가 n인 집합을 공집합이 아닌 (n－1)개의 서로소인 부분집합으로 분할하는 방법의 수이고, 원소의 개수가 1인 집합 (n－2)개와 원소의 개수가 2인 집합 1개로 분할하는 경우이다. 이 경우의 수는 n개의 원소 중 2개를 택하여 한 부분집합을 만들고 나머지 원소를 하나씩 원소로 가지는 부분집합으로 분할하면 되므로 S(n, n－1)＝

 

S(n＋1, 3)＝S(n, 2)＋3×S(n, 3)

증명) S(n＋1, 3)은 원소의 개수가 n＋1인 집합을 공집합이 아닌 3개의 서로소인 부분집합으로 분할하는 방법의 수이다.

원소의 개수가 n＋1인 집합을 공집합이 아닌 3개의 서로소인 부분집합으로 분할할 때 다음 두 가지 경우로 나누어 생각할 수 있다.

1) 특정한 한 원소를 제외한 원소의 개수가 n인 집합을 공집합이 아닌 2개의 서로소인 부분집합으로 분할하고 특정한 원소를 원소로 가지는 부분집합으로 분할하는 경우의 수는 S(n, 2)이다.

 

2) 특정한 한 원소를 제외한 원소의 개수가 n인 집합을 공집합이 아닌 3개의 서로소인 부분집합으로 분할하고 특정한 원소를 각 부분집합 중 하나에 포함시키는 경우의 수는 3×S(n, 3)이다.

 

1), 2) 에서

S(n＋1, 3)＝S(n, 2)＋3×S(n, 3)

 

이상 집합의 분할의 수의 경우의 수를 구하는 식을 알아 보았습니다.

집합의 분할의 수를 위와 같이 생각할 수 있다.