非交差分割

非交差分割とは、集合の分割の内、「集合の要素を円状に並べ、同じ部分集合に属する要素を頂点とした多角形同士が交差しない」分割を指す。特に組合せ数学で重要である。 非交差分割の組み合わせの数は、その要素の数に対応するカタラン数で表される。"k"個の集合に分割する、"n"要素の集合の非交差分割の数は、ナラヤナ数"N(n, k)" である。 
定義.
集合 "S の"分割は、共通要素を持たないかつ空集合でないかつそれらの和集合が"S"となるような、部分集合の集合である。順序付けられた、または（この定義の目的のために）正"n"角形の頂点に配列された有限集合を考える。 ここで、この集合とその要素を"S" = {1, ..., "n" }とすることで一般性が失われない。 "Ｓ"の非交差分割は、部分集合が互いに「交差」しない分割、すなわち、"ａ"と"ｂ"がある部分集合に属し、 "ｘ"と"ｙ"が他のある部分集合に属する場合、それらは"axby"の順に配列されない分割である。 "a"と"b"を基点とする弧と、 "x"と"y"を基点とする別の弧を描く場合、順序が"axbyで"あれば2つのアーチは交差し、"axyb"や"abxy"であれば交差しない。後者の2種類の順序では、分割は非交差である。 
同様に、正"n"角形の頂点に1から"n"の番号を付けると、分割の異なる部分集合の凸包は「互いに素（素集合）」になる。つまり、互いに交差しない。 "Ｓ"の全ての非交差分割の集合は、NC("S" )と表される。2つの要素数の等しい有限集合の非交差分割NC("S"_1)とNC("S"_2)には明らかな順序同型性がある。つまり、NC("S" )は集合の要素数にのみ本質的に依存し、要素数"n"の任意の集合の分割をそれをNC("n" )と表す。 
束構造.
集合{1, ..., "n" }のすべての非交差分割の集合のように、すべての非交差分割の集合は、より「細かい」分割はより「粗い」分割より「小さい」と言うことによって半順序集合であり、束になる。この構造は全ての非交差分割を束の要素として持つが、有効な結合操作が存在しないため、すべての分割の束の部分束とはならない。つまり、2種類の非交差分割の両方よりも粗い、最も細かい分割が、両方の非交差分割よりも粗い、最も細かい非交差分割であるとは限らない。 
集合のすべての分割の束とは異なり、集合のすべての非交差分割の格子は自己双対である。すなわち、それは半順序を逆にすることで得られる格子と順序同型である。 これは、非交差分割に非交差な補集合があることからわかる。 実際、この束のすべての分割は自己双対である。