집합의_분할,set_partition

partition of a set

집합의 분할이란,

부분집합,subset 몇 개로 나누는 것이다.
(mklink disjoint_subset - curr at 결합,joint)

원소가 n개인 집합을 k(1≤k≤n)개의 부분집합으로 분할하는 경우의 수:

$S(n,k)$

원소가 n개인 집합을 분할하는 모든 경우의 수:

$S(n,1)+S(n,2)+S(n,3)+\;\cdots\;+S(n,n)$

참고로

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

예
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 (답)

분할의 정의는 pairwise_disjoint에서도 언급 - curr at 결합,joint

rel.
집합의 분할의 수와 관련: 벨_수,Bell_number

Up:

Misc: 원래 Wikipedia를 따라 페이지명이 '집합의 분할,partition of a set'이었으나, 분할,partition페이지와 겹치므로 현재 제목으로 변경함.

VeryGoodWiki