partition of a set
원소가 n개인 집합을 k(1≤k≤n)개의 부분집합으로 분할하는 경우의 수:
원소가 n개인 집합을 분할하는 모든 경우의 수:
참고로
예
Q: {a, b, c, d}를 2개의 부분집합으로 분할하는 경우의 수는?
Sol.
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 (답)
Up:
Misc: 원래 Wikipedia를 따라 페이지명이 '집합의 분할,partition of a set'이었으나,
분할,partition페이지와 겹치므로 현재 제목으로 변경함.