집합의 분할

나눠 묶인 우표들. 동시에 두 묶음에 속하는 우표는 없으며, 빈 묶음도 없다.

5개 원소로 이루어진 집합의 52개의 분할

《겐지모노가타리》의 각 장을 나타내는 54개의 기호는 5개의 원소를 분할하는 52가지 방법에 기초하였다.

수학에서 집합의 분할(集合-分割, partition of a set)은 집합의 원소들을 비공(non-empty, 非空) 부분집합들에게 나눠주어, 모든 원소가 각자 정확히 하나의 부분집합에 속하게끔 하는 것이다. 집합 $X$의 분할은 $X$의 공집합이 아닌 부분집합들로 이루어진, 분리합집합이 $X$인 집합들이다.

정의

집합 $X$의 분할은 다음 조건을 만족하는 집합족 $P$로 정의된다.

• $P$는 공집합을 원소로 하지 않는다.
• $P$는 $X$를 덮는다.
• $P$는 서로소 집합족이다.

즉,

• $\emptyset \notin P$,
• $\bigcup P=X$
• $A,B\in P$이고 $A\neq B$이면 $A\cap B=\emptyset$

여기서, 공집합을 배제하는 것은 정형화를 위한 선택적인 규정이다.

예

• 한원소 집합 $\{x\}$의 분할은 $\{\{x\}\}$로 유일하다.
• 공집합의 분할은 공집합으로 유일하다.
• 공집합이 아닌 집합 $X$는 모두 분할 $P=\{X\}$를 가진다. 이를 자명 분할(trivial partition)이라고 한다.
• 공집합이 아닌 집합 $U$의 공집합이 아닌 진부분집합 $A$와 여집합 $U-A$는 $U$의 분할을 이룬다.
• 집합 $\{1,2,3\}$의 분할은 5개이다.
  • $\{\{1,2,3\}\}$, 즉 $123$
  • $\{\{1\},\{2,3\}\}$, 즉 $1|23$
  • $\{\{2\},\{3,1\}\}$, 즉 $2|31$
  • $\{\{3\},\{1,2\}\}$, 즉 $3|12$
  • $\{\{1\},\{2\},\{3\}\}$, 즉 $1|2|3$
• 다음은 $\{1,2,3\}$의 분할이 아니다.
  • $\{\{\},\{1,2\},\{3\}\}$은 공집합을 원소로 포함하므로, $\{1,2,3\}$의 분할이 아니며, 다른 어떤 집합의 분할도 아니다.
  • $\{\{1,2\},\{2,3\}\}$은 서로소이지 않으므로, $\{1,2,3\}$의 분할이 아니며, 다른 어떤 집합의 분할도 아니다.
  • $\{\{1\},\{2\}\}$. 합집합이 $\{1,2,3\}$이 아니기 때문이다.
• 정수는 홀수와 짝수로, 음과 양의 정수 및 0으로, 소수와 합성수 및 0과 1로 분류되며, 이들은 모두 정수 집합에 대한 분할에 대응한다.

동치관계와의 관계

집합 $X$ 위의 임의의 동치관계 $\sim$에 대해, 그에 의한 몫집합 $X/{\sim }$은 $X$의 분할이다. 역으로 $X$의 임의의 분할 $P$에 대해,

$x\sim y\iff \exists A\in P,\ x,y\in A,$

즉 $x,y$가 $P$ 안의 같은 집합에 속한다는, $X$ 위의 이항관계 $\sim$는 $X$ 위의 동치관계이다. 그러므로 동치관계와 분할의 개념은 동등하다.

선택 공리에 의하면 집합 $X$의 임의의 분할에 대하여 분할의 각 원소에서 하나의 원소를 취하여 구성한 $X$의 부분집합이 존재한다. 그러므로 집합 상의 동치관계가 주어졌을 때 각 동치류로부터 하나의 대표 원소를 선택해내는 것이 가능하다.

분할의 세분

4 원소 집합의 분할과 세분에 의한 부분 순서

집합 $X$의 두 분할 $\alpha ,\rho$에 대하여, $\alpha$의 모든 원소가 $\rho$의 어떤 원소의 부분집합이라면, $\alpha$를 $\rho$의 세분(細分, refinement)이라고 하고, $\alpha \leq \rho$로 표기한다. ($\alpha$가 $\rho$보다 더 섬세하다(纖細, finer), 또는 $\rho$가 $\alpha$보다 더 엉성하다(coarser)로 읽는다.)

$\leq$는 $X$의 모든 분할의 집합 위의 부분 순서이다. 임의의 부분집합이 상한과 하한을 가지므로, 이는 격자를 이루며, 나아가 유한 집합의 분할인 경우 기하격자를 이룬다.^:95 4원소 집합의 분할격자는 15개의 원소가 있으며, 왼쪽 그림에서 하세 도형으로 표현된다.

이 분할격자는, 기하격자와 동일한 개념인 매트로이드에도 대응한다. 이때 기저집합은 격자의 원자들, 즉 (n - 2)원소 집합과 2원소 집합으로 이루어진 분할들로 이루어진다. 이들 원자 분할은 완전 그래프의 변들과 일대일 대응한다. 어떤 주어진 원자 분할들의 집합의 매트로이드 폐포는, 그들 모두보다 엉성한 분할들 중 가장 섬세한 하나이며, 그래프 이론적으로 이는 주어진 변들에 의한 부분 그래프의 연결성분이다. 이로써 이 분할 격자는 완전 그래프의 그래프 매트로이드이다.

동치관계에 의한 분할의 세분의 예로, D를 52장의 플레잉카드의 집합이라 하면, D 상의 '같은 색깔'에 의한 동치관계 ~_C는 두 개의 동치류, 즉 {붉은색 카드}, {검은색 카드}를 가지고, '같은 슈트'에 의한 동치관계 ~_S는 {하트}, {다이아몬드}, {클럽}, {스페이드} 4개의 동치류를 가진다. ~_S에 대응하는 분할은 ~_C에 대응하는 분할의 세분이다.

비교차 분할

 비교차 분할 문서를 참고하십시오.

집합 $N$ 위의 순환순서는 간단히 말해 원 위에 모든 원소를 서로 다른 위치에 나열하고, 회전방향을 정하여 형성되는 삼항관계이다. 그 예로 모든 요일들의 집합 위에 자연적으로 정의한 순환순서에서, [화요일 , 수요일 , 토요일], [금요일 , 수요일 , 목요일]이 성립하지만 [금요일 , 화요일 , 월요일]은 성립하지 않는다.

순환순서가 정의된 유한집합 $N=\{1,2,\ldots ,n\}$의 분할 $P$와 그에 대응하는 동치관계 $\sim$에 대하여, 만약 $P$의 서로 다른 두 원소 $C_{1},C_{2}$에서 각각 임의의 서로 다른 두 원소 $a,b\in C_{1},x,y\in C_{2}$를 취했을 때, 그들이 $[a,x,b]$와 $[b,y,a]$를 동시에 만족하지 않는다면, 분할 $P$(또는 동치관계 $\sim$)가 교차하지 않는다고 한다. 이는 다르게 말해 원 또는 다각형에 표기한 분할이 교착하지 않는다는 것이다. 집합의 모든 비교차 분할 역시 격자를 이룬다. 그러나 이음 연산이 일치하지 않기 때문에, 모든 분할이 이루는 격자의 부분격자는 아니다.

분할의 수

n개 원소의 집합을 분할하는 방법수는 벨 수 $B_{n}$이다. 앞의 6개의 벨 수는 다음과 같다.

1, 1, 2, 5, 15, 52, 203 (OEIS의 수열 A000110)

벨 수에 대해 점화식

$B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}$

이 성립하며, 다음과 같은 지수생성함수를 가진다.

$\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}$

벨 삼각형의 구성

벨 삼각형을 이용하여 벨 수를 계산할 수도 있다. 각 행의 첫 수는 이전 행의 마지막 수이고, 뒤 잇는 수들은 왼쪽과 왼쪽 위의 수를 더한 것이다. 벨 수는 삼각형의 양 옆에서 각각 차례대로 나열된다. 삼각형 안에 있는 수도 의미를 가지는데, 예를 들어 3행 2열의 수가 3이라는 것은 집합 $\{1,2,3\}$의 모든 한원소 집합의 원소가 2이거나 2보다 작다는 것을 만족하는 분할이 3가지라는 것이다.

n원소 집합을 정확히 k 개의 집합으로 분할하는 방법 수는 제2종 스털링 수 $S(n,k)$이다.

n원소 집합의 비교차분할의 개수는 카탈랑 수 $C_{n}$이다.

$C_{n}={\frac {1}{n+1}}{2n \choose n}$

같이 보기

• 클러스터 분석
• 약한 순서의 정의법 중 하나는 집합의 분할에 순서를 정의하는 것이다.
• 동치관계

참고 문헌

• Brualdi, Richard A. (2004). 《Introductory Combinatorics》 (영어) 4판. Pearson Prentice Hall. ISBN 0-13-100119-1. 
• Schechter, Eric (1997). 《Handbook of Analysis and Its Foundations》 (영어). Academic Press. ISBN 0-12-622760-8.