非交差分割
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Noncrossing_partitions_5.svg/220px-Noncrossing_partitions_5.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/00/Noncrossing_partitions_4%3B_Hasse.svg/220px-Noncrossing_partitions_4%3B_Hasse.svg.png)
非交差分割とは、集合の分割の内、「集合の要素を円状に並べ、同じ部分集合に属する要素を頂点とした多角形同士が交差しない」分割を指す。特に組合せ数学で重要である。 非交差分割の組み合わせの数は、その要素の数に対応するカタラン数で表される。k個の集合に分割する、n要素の集合の非交差分割の数は、ナラヤナ数N(n, k) である。
定義
[編集]集合 S の分割は、共通要素を持たないかつ空集合でないかつそれらの和集合がSとなるような、部分集合の集合である。順序付けられた、または(この定義の目的のために)正n角形の頂点に配列された有限集合を考える。 ここで、この集合とその要素をS = {1, ..., n }とすることで一般性が失われない。 Sの非交差分割は、部分集合が互いに「交差」しない分割、すなわち、aとbがある部分集合に属し、 xとyが他のある部分集合に属する場合、それらはaxbyの順に配列されない分割である。 aとbを基点とする弧と、 xとyを基点とする別の弧を描く場合、順序がaxbyであれば2つのアーチは交差し、axybやabxyであれば交差しない。後者の2種類の順序では、分割{{a, b},{x,y}}は非交差である。
交差 | axby |
非交差 | axyb |
非交差 | abxy |
同様に、正n角形の頂点に1からnの番号を付けると、分割の異なる部分集合の凸包は「互いに素(素集合)」になる。つまり、互いに交差しない。 Sの全ての非交差分割の集合は、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