集合の分割

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

定義

集合 X の分割 P は、X の空でない部分集合からなる集合族であり、X の個々の元 x について x ∈ A ∈ P を満たす X の部分集合 A が必ずただ一つ存在する。

X の部分集合族 P が X の分割であるためには、次が成り立つ必要がある。

P は元として空集合を持たない。
P の元の和集合は X と等しい（P は X を覆っている）。
P の任意の2つの異なる元の共通部分は空集合である（つまり P の相異なる元は互いに素である）。

数学的には、これら2つの条件を次のように表現できる。

$\emptyset \notin P$
$\bigcup P=X$
$A\cap B=\varnothing {\text{ if }}A\in P,\,B\in P,\,A\neq B$

P の元を分割の「ブロック (block)」あるいは「部分 (part)」と呼ぶ^[1]。

例

あらゆる単集合 {x} には唯一の分割 { {x} } しか存在しない。
空でない任意の集合 X について、P = {X} は X の分割の1つである。
集合 U の任意の空でない真部分集合 A について、A とその差集合からなる集合族は U の分割の1つである。
集合 { 1, 2, 3 } には5種類の分割がある。
- { {1}, {2}, {3} } これを 1/2/3 と表記することもある。
- { {1, 2}, {3} } これを 12/3 と表記することもある。
- { {1, 3}, {2} } これを 13/2 と表記することもある。
- { {1}, {2, 3} } これを 1/23 と表記することもある。
- { {1, 2, 3} } これを 123 と表記することもある。

ちなみに

{ {}, {1,3}, {2} } は分割ではない（空集合を含んでいるため）。
{ {1,2}, {2, 3} } は分割ではない（2 という元が2つの部分集合に含まれているため）。
{ {1}, {2} } は {1, 2, 3} の分割ではないが（3 がどのブロックにも含まれていないため）、{1, 2} の分割としては正しい。

分割と同値関係

集合 $X$ 上の任意の同値関係 $R$ について、その同値類の集合 $X/R$ は $X$ の分割である。集合 $X$ の同値関係 $R$ からその同値類集合として $X$ の分割を得ることを、 $R$ による $X$ の類別または分類 (classification) と呼ぶ^[2]。

逆に、 $X$ の任意の分割 $P$ から $X$ 上の同値関係 $R P$ を定義することができる。すなわち、 $X$ の任意の2つの元 $x$ と $y$ が $P$ の同じブロックに属するとき、 $x ~ y$ とすれば、これは同値関係を定める。このとき、同値関係 $R P$ を分割 $P$ に付随する (associated) 同値関係という^[2]。

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

分割の細分

集合 X の分割 π が集合 X の分割 ρ の細分 (refinement) であるとは、π の個々の元が全て ρ のいずれかの元の部分集合であることを言う。大雑把に言えば、π の方が p よりも分割が細かい。これを π ≤ ρ と表記することもある。

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

もう1つの例として、同値関係の観点から分割を細分化する方法を述べる。D を一般的なトランプの52枚のカードの集合とする。D における「色が同じ」という関係を ~_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 となっている。ベル数は次の漸化式で表される。

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}

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

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

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

脚注・出典

^ Brualdi, Richard A. (2004). Introductory Combinatorics (4th edition ed.). Pearson Prentice Hall. pp. 44-45. ISBN 0131001191
^ ^a ^b 松坂和夫『集合・位相入門』岩波書店、1968年。 p. 57
^ Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. p. 54. ISBN 0126227608

[brualdi44_45-1] Brualdi, Richard A. (2004). Introductory Combinatorics (4th edition ed.). Pearson Prentice Hall. pp. 44-45. ISBN 0131001191

[松坂-2] 松坂和夫『集合・位相入門』岩波書店、1968年。 p. 57

[schechter54-3] Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. p. 54. ISBN 0126227608

[1]

[2]

[3]