集合の分割のソースを表示

[[ファイル:Set partition.svg|right|thumb|集合を6つの部分に分割した図（[[オイラー図]]による表現）]]
[[数学]]において、[[集合]] ''X'' の'''分割''' (partition) とは、''X'' の[[集合の被覆|全体を覆う]][[素集合|互いに重ならない]][[部分集合]]の[[集合族|族]]のこと、あるいはその集合族を得ることである。

== 定義 ==
集合 ''X'' の分割 ''P'' は、''X'' の[[空集合|空でない]][[部分集合]]からなる[[集合族]]であり、''X'' の個々の[[元 (数学)|元]] ''x'' について ''x'' &in; ''A'' &in; ''P'' を満たす ''X'' の部分集合 ''A'' が必ずただ一つ存在する。

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

# ''P'' は元として空集合を持たない。
# ''P'' の元の[[合併 (集合論)|和集合]]は ''X'' と等しい（''P'' は ''X'' を[[集合の被覆|覆っている]]）。
# ''P'' の任意の2つの異なる元の[[共通部分 (数学)|共通部分]]は空集合である（つまり ''P'' の相異なる元は[[素集合|互いに素]]である）。

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

#<math>\emptyset \notin P</math>
#<math>\bigcup P = X</math>
#<math>A \cap B = \varnothing \text{ if } A \in P,\, B\in P,\, A \neq B</math>

''P'' の元を分割の「ブロック (block)」あるいは「部分 (part)」と呼ぶ<ref name="brualdi44_45">{{cite book |last= Brualdi |first= Richard A. |title= Introductory Combinatorics |edition= 4th edition |year= 2004 |publisher= Pearson Prentice Hall |pages=44-45 |isbn= 0131001191}}</ref>。

== 例 ==
* あらゆる[[単集合]] {''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} の分割としては正しい。

== 分割と同値関係 ==
集合 {{mvar|X}} 上の任意の[[同値関係]] {{mvar|R}} について、その[[同値類]]の集合 {{mvar|X/R}} は {{mvar|X}} の分割である。集合 {{mvar|X}} の同値関係 {{math|R}} からその同値類集合として {{mvar|X}} の分割を得ることを、{{mvar|R}} による {{mvar|X}} の'''類別'''または'''分類''' (classification) と呼ぶ<ref name="松坂">{{cite book|和書|author=松坂和夫|title=集合・位相入門|publisher=岩波書店|year=1968}}p. 57</ref>。

逆に、{{mvar|X}} の任意の分割 {{mvar|P}} から {{mvar|X}} 上の同値関係 {{mvar|R{{sub|P}}}} を定義することができる。すなわち、{{mvar|X}} の任意の2つの元 {{mvar|x}} と {{mvar|y}} が {{mvar|P}} の同じブロックに属するとき、{{math|''x'' ~ ''y''}} とすれば、これは同値関係を定める。このとき、同値関係 {{mvar|R{{sub|P}}}} を分割 {{mvar|P}} に'''付随する''' (associated) 同値関係という<ref name="松坂"/>。

したがって、集合に同値関係を設定することと集合の分割は本質的に等価である<ref name="schechter54">{{cite book |last= Schechter |first= Eric |title= Handbook of Analysis and Its Foundations |year= 1997 |publisher= Academic Press |page=54 |isbn= 0126227608}}</ref>。

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

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

[[ファイル:PartitionLattice.svg|center|480px]]

もう1つの例として、同値関係の観点から分割を細分化する方法を述べる。''D'' を一般的な[[トランプ]]の52枚のカードの集合とする。''D'' における「色が同じ」という関係を ~<sub>C</sub> などと表記する。このとき2つの同値類、{赤いカード} という集合と {黒いカード} という集合が得られる。この ~<sub>C</sub> に対応した2ブロックの分割には「[[スート]]が同じ」という関係 ~<sub>S</sub> による細分が存在し、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''<sub>''n''</sub> である。''n'' の小さいベル数を列挙すると、''B''<sub>0</sub> = 1、''B''<sub>1</sub> = 1、''B''<sub>2</sub> = 2、''B''<sub>3</sub> = 5、''B''<sub>4</sub> = 15、''B''<sub>5</sub> = 52、''B''<sub>6</sub> = 203 となっている。ベル数は次の[[漸化式]]で表される。

:<math>B_{n+1}=\sum_{k=0}^n {n\choose k}B_k</math>

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

:<math>\sum_{n=0}^\infty\frac{B_n}{n!}z^n=e^{e^z-1}</math>

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

''n'' 個の元を持つ集合の非交差な分割の総数は[[カタラン数]] ''C<sub>n</sub>'' であり、次の式で表される。

:<math>C_n={1 \over n+1}{2n \choose n}</math>

== 関連項目 ==
* [[データ・クラスタリング]]
* [[同値関係]]
* [[自然数の分割]]
* [[MECE]]

== 脚注・出典 ==
{{reflist}}

{{Normdaten}}
{{DEFAULTSORT:しゆうこうのふんかつ}}
[[Category:組合せ論]]
[[Category:集合論]]
[[Category:数学に関する記事]]