Непересекающийся раздел

В наборе из 5 элементов имеется 42 непересекающихся и 10 пересекающихся разбиений.

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

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

Определение

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

Пересечение:	Аксби
Непересекающиеся:	аксиб
Непересекающиеся:	абкси

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

Решетчатая структура

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

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

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

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

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

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

Ссылки

• Жермен Креверас, «О непересекающихся разбиениях цикла», Дискретная математика , том 1, номер 4, страницы 333–350, 1972.
• Родика Симион , «Непересекающиеся разделы», Дискретная математика , том 217, номера 1–3, страницы 367–409, апрель 2000 г.
• Роланд Спайхер, «Свободная вероятность и непересекающиеся разбиения» , Лотарингский семинар по комбинаторике , B39c (1997), 38 страниц, 1997 г.