非交差分割

非交差分割とは、集合の分割の内、「集合の要素を円状に並べ、同じ部分集合に属する要素を頂点とした多角形同士が交差しない」分割を指す。特に組合せ数学で重要である。非交差分割の組み合わせの数は、その要素の数に対応するカタラン数で表される。k個の集合に分割する、n要素の集合の非交差分割の数は、ナラヤナ数N(n, k) である。

定義

集合 S の分割は、共通要素を持たないかつ空集合でないかつそれらの和集合がSとなるような、部分集合の集合である。順序付けられた、または（この定義の目的のために）正n角形の頂点に配列された有限集合を考える。ここで、この集合とその要素をS = {1, ..., n }とすることで一般性が失われない。Ｓの非交差分割は、部分集合が互いに「交差」しない分割、すなわち、ａとｂがある部分集合に属し、ｘとｙが他のある部分集合に属する場合、それらはaxbyの順に配列されない分割である。 aとbを基点とする弧と、 xとyを基点とする別の弧を描く場合、順序がaxbyであれば2つのアーチは交差し、axybやabxyであれば交差しない。後者の2種類の順序では、分割{{a, b},{x,y}}は非交差である。

交差	axby
非交差	axyb
非交差	abxy

同様に、正n角形の頂点に1からnの番号を付けると、分割の異なる部分集合の凸包は「互いに素（素集合）」になる。つまり、互いに交差しない。Ｓの全ての非交差分割の集合は、NC(S )と表される。2つの要素数の等しい有限集合の非交差分割NC(S_1)とNC(S_2)には明らかな順序同型性がある。つまり、NC(S )は集合の要素数にのみ本質的に依存し、要素数nの任意の集合の分割をそれをNC(n )と表す。

束構造

集合{1, ..., n }のすべての非交差分割の集合のように、すべての非交差分割の集合は、より「細かい」分割はより「粗い」分割より「小さい」と言うことによって半順序集合であり、束になる。この構造は全ての非交差分割を束の要素として持つが、有効な結合操作が存在しないため、すべての分割の束の部分束とはならない。つまり、2種類の非交差分割の両方よりも粗い、最も細かい分割が、両方の非交差分割よりも粗い、最も細かい非交差分割であるとは限らない。

集合のすべての分割の束とは異なり、集合のすべての非交差分割の格子は自己双対である。すなわち、それは半順序を逆にすることで得られる格子と順序同型である。これは、非交差分割に非交差な補集合があることからわかる。実際、この束のすべての分割は自己双対である。

参考文献

Germain Kreweras, "Sur les partitions non croisées d'un cycle", Discrete Mathematics, volume 1, number 4, pages 333–350, 1972.
Rodica Simion, "Noncrossing partitions", Discrete Mathematics, volume 217, numbers 1–3, pages 367–409, April 2000.
Roland Speicher, "Free probability and noncrossing partitions", Séminaire Lotharingien de Combinatoire, B39c (1997), 38 pages, 1997