집합의 분할

집합의 분할

집합의 분할 방법의 수

1 집합의 분할

• 주어진 집합을 공집합이 아닌 몇 개의 서로소인 부분집합으로 나누는 것

2 분할방법의 수

• 원소의 개수가 n인 집합을 서로소인 k개의 집합으로 분할하는 방법의 수

[math]\displaystyle{ S(n,k)=S(n-1, k-1)+kS(n-1, k) }[/math]

[math]\displaystyle{ S(n, 1)=S(n, n)=1 }[/math]

• 원소의 개수가 n인 집합의 모든 분할의 수

[math]\displaystyle{ B(n) = S(n, 1) + S(n, 2) + \cdots + S(n, n) }[/math]

3 예시 1

• 집합 [math]\displaystyle{ \{a, b, c\} }[/math]를 서로소인 2개의 집합으로 분할하는 방법의 수

[math]\displaystyle{ \{a\}\cup\{b, c\}, \{b\}\cup\{a, c\}, \{c\}\cup\{a, b\} }[/math] → 3가지

[math]\displaystyle{ S(3, 2)=S(2, 1)+2S(2, 2)=1+2=3 }[/math]

4 예시 2

• 신입사원 4명을 2개조로 나누는 방법의 수

[math]\displaystyle{ S(4, 2) = _4C_1 \times _3C_3 + _4C_2 \times _2C_2 \times \frac{1}{2!}= 4 + 3 = 7 }[/math]

[math]\displaystyle{ S(4, 2)=S(3, 1)+2S(3, 2)=1+2\times3=7 }[/math]

5 예시 3

• 집합 [math]\displaystyle{ {a, b, c} }[/math]의 모든 분할의 수

[math]\displaystyle{ \{a, b, c\}, \{a, b\}\cup\{c\}, \{a, c\}\cup\{b\}, \{b, c\}\cup\{a\}, \{a\}\cup\{b\}\cup\{c\} }[/math]

[math]\displaystyle{ B(3) = S(3, 1) + S(3, 2) + S(3, 3) = 1 + 3 + 1 = 5 }[/math]

6 같이 보기

• 집합
• 부분집합
• 동치관계
• 경우의 수
• 자연수의 분할
• 클러스터 분석

7 참고

• 위키백과 "집합의 분할"