Непересекающаяся перегородка - Noncrossing partition

Всего имеется 42 непересекающихся и 10 пересекающихся перегородок пятиэлементного набора.

14 непересекающихся перегородок четырехэлементного набора, упорядоченного в Диаграмма Хассе

В комбинаторная математика, тема непересекающиеся перегородки приобрела некоторую важность из-за (среди прочего) его применения к теории свободная вероятность. Количество непересекающихся перегородок набора п элементы это пth Каталонский номер. Количество непересекающихся перегородок п-элементный набор с k блоки находится в Число Нараяны треугольник.

Определение

А раздел набора S является набором непустых, попарно непересекающихся подмножеств S, называемые «частями» или «блоками», объединяющие все S. Рассмотрим конечное множество, которое линейно упорядочено или (что то же самое для целей этого определения) расположено в циклический порядок как вершины регулярного п-гон. Если принять этот набор за S = { 1, ..., п }. А непересекающаяся перегородка из S представляет собой разбиение, в котором никакие два блока не «пересекаются», т. е. если а и б принадлежат к одному блоку и Икс и y другому, они не расположены в порядке а х б у. Если нарисовать арку на основе а и б, и еще одна арка на базе Икс и y, то две арки пересекают друг друга, если порядок а х б у но не если это а х у б или а б х у. В последних двух порядках разбиение {{ а, б }, { Икс, y }} не пересекается.

Пересечение:	а х б у
Некроссинг:	а х у б
Некроссинг:	а б х у

Эквивалентно, если мы помечаем вершины регулярного п-угольник с цифрами от 1 до п, то выпуклые оболочки различных блоков разбиения не пересекаются друг с другом, т.е. они также не "пересекаются" друг с другом. Множество всех непересекающихся разбиений S обозначаются ${\displaystyle {\text{NC}}(S)}$. Существует очевидный изоморфизм порядка между ${\displaystyle {\text{NC}}(S_{1})}$ и ${\displaystyle {\text{NC}}(S_{2})}$ для двух конечных множеств ${\displaystyle S_{1},S_{2}}$ с таким же размером. Это, ${\displaystyle {\text{NC}}(S)}$ существенно зависит только от размера ${\displaystyle S}$ и обозначим через ${\displaystyle {\text{NC}}(n)}$ непересекающиеся перегородки на Любые набор размеров п.

Структура решетки

Подобно множеству всех разбиений множества {1, ..., п }, множество всех непересекающихся разбиений есть решетка когда частично заказанный говоря, что более мелкий раздел «меньше» более грубый. Однако, хотя это подмножество решетки всех разделов, это не подрешетка решетки всех разбиений, потому что операции соединения не согласуются. Другими словами, лучший раздел, который грубее, чем оба из двух непересекающихся разделов, не всегда является лучшим. непересекающийся раздел, более грубый, чем они оба.

В отличие от решетки всех разбиений набора, решетка всех непересекающихся разбиений набора самодвойственна, т. Е. Она изоморфна по порядку решетке, которая возникает в результате инвертирования частичного порядка («переворачивания его вверх дном») . Это можно увидеть, заметив, что каждый непересекающийся раздел имеет дополнение. В самом деле, каждый интервал в этой решетке самодуальный.

Роль в свободной теории вероятностей

Решетка непересекающихся перегородок играет такую ​​же роль в определении бесплатные кумулянты в свободная вероятность теория, которую играет решетка все перегородки в определении совместных кумулянтов в классических теория вероятности. Чтобы быть более точным, пусть ${\displaystyle ({\mathcal {A}},\phi )}$ быть некоммутативное вероятностное пространство (Увидеть свободная вероятность для терминологии.), ${\displaystyle a\in {\mathcal {A}}}$ а некоммутативная случайная величина со свободными кумулянтами ${\displaystyle (k_{n})_{n\in \mathbb {N} }}$. потом

${\displaystyle \phi (a^{n})=\sum _{\pi \in {\text{NC}}(n)}\prod _{j}k_{j}^{N_{j}(\pi )}}$

где ${\displaystyle N_{j}(\pi )}$ обозначает количество блоков длины ${\displaystyle j}$ в непересекающейся перегородке ${\displaystyle \pi }$То есть моменты некоммутативной случайной величины могут быть выражены как сумма свободных кумулянтов по непересекающимся разбиениям суммы. Это бесплатный аналог формула моментного кумулянта в классической вероятности. см. также Распределение полукруга Вигнера.

использованная литература

• Жермен Креверас, "Sur les partitions non croisées d'un cycle", Дискретная математика, том 1, номер 4, страницы 333–350, 1972 г.
• Родика Симион, "Непересекающиеся перегородки", Дискретная математика, том 217, номера 1–3, страницы 367–409, апрель 2000 г.
• Роланд Спайкер, "Свободная вероятность и непересекающиеся разделы", Séminaire Lotharingien de Combinatoire, B39c (1997), 38 страниц, 1997