partition of a set
집합의 분할이란,
(mklink disjoint_subset - curr at 결합,joint)
- 원소가 유한개인 집합을
- 공집합이 아닌
- 서로소인
(mklink disjoint_subset - curr at 결합,joint)
원소가 n개인 집합을 k(1≤k≤n)개의 부분집합으로 분할하는 경우의 수:
원소가 n개인 집합을 분할하는 모든 경우의 수:
참고로
예
Q: {a, b, c, d}를 2개의 부분집합으로 분할하는 경우의 수는?
Q: {a, b, c, d}를 2개의 부분집합으로 분할하는 경우의 수는?
Sol.
S(4, 2)
각각 1개, 3개
S(4, 2)
각각 1개, 3개
4개 중에서 1개 택하고, 나머지 3개 중에서 3개를 택함 C(4,1)×C(3,3) = 4
각각 2개, 2개4개 중에서 2개 택하고, 나머지 2개 중에서 2개를 택함. 두 부분집합의 원소의 개수가 같아 중복되는 경우가 2!개 나타남.
C(4,2)×C(2,2)/(2!) = 3
4+3=7 (답)C(4,2)×C(2,2)/(2!) = 3
Up:
Misc: 원래 Wikipedia를 따라 페이지명이 '집합의 분할,partition of a set'이었으나, 분할,partition페이지와 겹치므로 현재 제목으로 변경함.
Misc: 원래 Wikipedia를 따라 페이지명이 '집합의 분할,partition of a set'이었으나, 분할,partition페이지와 겹치므로 현재 제목으로 변경함.