非交差分割

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

同様に、正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