集合の分割

数学において、集合の分割（英: partition）とは、その集合の全体を覆う互いに重ならない部分集合の族のこと、あるいはその集合族を得ることである。

集合を6つの部分に分割した図（オイラー図による表現）

主にビジネスの文脈では、そのような集合族のあり方をMECEという。

定義

集合 𝑋 の分割 𝒫 は、𝑋 の非空部分集合からなる集合族である。ただし、𝑋 の任意の元 𝑒 について、𝑒 ∈ 𝑠 かつ 𝑠 ∈ 𝒫 となる 𝑋 の部分集合 𝑠 がただ一つ存在する。

以下の条件を全て満たす 𝒫 を 𝑋 の分割という。

• 空集合は 𝒫 に帰属しない。

${\displaystyle \varnothing \not \in {\mathcal {P}}}$

• 𝒫 は 𝑋 を覆っている。

${\displaystyle X={\begin{aligned}\textstyle \bigcup \limits _{s\,\in \,{\mathcal {P}}}\end{aligned}}\,s}$

• 𝒫 の任意の異なる二元は互いに素である。

${\displaystyle \forall \ s_{1},\,s_{2}\in {\mathcal {P}},\,s_{1}\not =s_{2}\rightarrow s_{1}\cap s_{2}=\varnothing }$

𝒫 の元を分割のブロック（英: block）または部分（英: part）という^[1]。

例と反例

例

• 非空集合 S について、集合族 {S} は S の分割の一つである。
• 二元以上の集合 S とその任意の非空の真部分集合 s について、集合族 {S ∖ s, s} は S の分割の一つである。
• 単集合 {x} には唯一の分割 {{x}} しか存在しない。
• 三元集合には五通りの分割がある。

反例

• {∅, {1, 3}, {2}} は空集合を含むため、分割ではない。
• {{1, 2}, {2, 3}} は 2 という元が二つのブロックに含まれるため、分割ではない。
• {{1}, {2}} は {1, 2, 3} の分割ではない。

分割と同値関係

集合 𝑋 上の任意の同値関係 𝑅^{[注釈 1]} について、その同値類の集合 𝑋 / 𝑅 は 𝑋 の分割である。集合 𝑋 の同値関係 𝑅 からその同値類集合として 𝑋 の分割を得ることを、𝑅 による 𝑋 の類別または分類（英: classification） という^[2]。

逆に、𝑋 の任意の分割 𝒫 から 𝑋 上の同値関係 𝑅_𝒫 を定義することができる。すなわち、𝑋 の任意の二元 𝑥 と 𝑦 が 𝒫 の同じブロックに属するとき、𝑥 ∼ 𝑦 とすれば、これは同値関係を定める。このとき、同値関係 𝑅_𝒫 を分割 𝒫 に付随する（英: associated）同値関係という^[2]。

したがって、集合に同値関係を設定することと集合の分割は本質的に等価である^[3]。

分割の細分

集合 𝑋 の任意の分割 𝒫 と 𝒬 について、𝒫 の任意のブロックが 𝒬 のいずれかのブロックの部分集合であるとき、𝒫 を 𝒬 の細分（英: refinement）という。大雑把に言えば、𝒫 と 𝒬 は等しいか、𝒫 は 𝒬 より細かな分割である。

これを 𝒫 ≤ 𝒬 と表記することもある。
${\displaystyle {\mathcal {P}}\leq {\mathcal {Q}}\Leftrightarrow \forall \ s\in {\mathcal {P}},\,\exists \ t\in {\mathcal {Q}},\,s\subseteq t}$

𝑋 の分割の集合におけるこの「より細かい」関係は半順序であり（そのため、≤ で表すのが適当）、実のところ完備束である。例えば、𝑋 = {1, 2, 3, 4} の「分割束」には15の元があり、以下のハッセ図で表される。

もう1つの例として、同値関係の観点から分割を細分化する方法を述べる。𝐷 を一般的なトランプの52枚のカードの集合とする。𝐷 における「色が同じ」という関係を ~_C などと表記する。このとき2つの同値類、{赤いカード} という集合と {黒いカード} という集合が得られる。この ~_C に対応した2ブロックの分割には「スートが同じ」という関係 ~_S による細分が存在し、4つの同値類 {スペード}、{ダイヤ}、{ハート}、{クラブ} が得られる。

非交差な分割

自然数の集合 N = {1, 2, ..., n} の同値関係 ~ に対応した分割が非交差 (noncrossing) であるとは、N 内のそれぞれ別の数 a、b、c、d が a < b < c < d という大小関係で、しかも a ~ c および b ~ d ということがない場合である。 上記のX = {1, 2, 3, 4} では、13/24のみが非交差ではない分割である． 有限集合の非交差な分割の束は、自由確率論において重要であることが近年わかってきた。2つの束の結びをとる操作が合致しないため、これらは全ての分割の束の部分集合を形成するが、部分束ではない。

各種分割の数え上げ

n 個の元を持つ集合の分割の総数はベル数 B_n である。n の小さいベル数を列挙すると、B₀ = 1、B₁ = 1、B₂ = 2、B₃ = 5、B₄ = 15、B₅ = 52、B₆ = 203 となっている。ベル数は次の漸化式で表される。

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

そして、次のような指数型母関数が存在する。

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

n 個の元を持つ集合を k 個のブロックに分ける分割の総数は、第2種スターリング数 S(n, k) である。

n 個の元を持つ集合の非交差な分割の総数はカタラン数 C_n であり、次の式で表される。

${\displaystyle C_{n}={1 \over n+1}{2n \choose n}}$

関連項目

• データ・クラスタリング
• 同値関係
• 自然数の分割
• MECE

注釈

1. 𝑅 ⊆ 𝑋²