集合の分割

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
集合を6つの部分に分割した図(オイラー図による表現)

数学において、集合 X分割 (partition) とは、X 全体を互いに重ならない部分/ブロック/セルに分けることを言う。より形式的に言えば、それらの「セル」は分割された集合から見て相互に排他的で完全な全体集合 (MECE) となっている。

定義[編集]

集合 X の分割は、X空でない部分集合の集合であり、Xの個々の元 x は必ず1つの部分集合にのみ属している。

空でない集合の集合 PX の分割であるためには、次が成り立つ必要がある。

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

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

  1. \bigcup P = X
  2. 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 上の任意の同値関係について、その同値類の集合は X の分割である。逆に、X の分割 P から X 上の同値関係を定義することができる。すなわち、X の任意の2つの元 xyP の同じブロックに属するとき、x ~ y という同値関係を設定する。したがって、集合に同値関係を設定することと集合の分割は本質的に等価である[2]

分割の細分[編集]

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

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

PartitionLattice.svg

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

非交差な分割[編集]

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

各種分割の数え上げ[編集]

n個の元を持つ集合の分割の総数はベル数 Bn である。n の小さいベル数を列挙すると、B0 = 1、B1 = 1、B2 = 2、B3 = 5、B4 = 15、B5 = 52、B6 = 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個の元を持つ集合の非交差な分割の総数はカタラン数 Cn であり、次の式で表される。

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

関連項目[編集]

脚注・出典[編集]

  1. ^ Brualdi, Richard A. (2004). Introductory Combinatorics (4th edition ed.). Pearson Prentice Hall. pp. 44-45. ISBN 0131001191. 
  2. ^ Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. p. 54. ISBN 0126227608.