Введение

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

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

Как и множество всех разбиений множества {1, ..., n}, множество всех непересекающихся разбиений является решеткой при частичном упорядочении, определяемом тем, что более точное разбиение "меньше" более грубого разбиения. Однако, хотя оно является подмножеством решетки всех разбиений множества, оно не является подрешеткой, поскольку это подмножество не замкнуто относительно операции объединения в большей решетке. Иными словами, наигрубейшее разбиение, которое является грубее двух непересекающихся разбиений, не всегда является наигрубейшим непересекающимся разбиением, которое грубее обоих этих разбиений. В отличие от решетки всех разбиений множества, решетка всех непересекающихся разбиений является самодвойственной, то есть она изоморфна самой себе относительно порядка, получаемого при обращении частичного порядка ("перевороте"). Это можно увидеть, заметив, что у каждого непересекающегося разбиения есть непересекающееся дополнение. Действительно, каждый интервал в этой решетке самодвойственен.

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

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

где обозначает число блоков длины в непересекающемся разбиении. То есть моменты некоммутативной случайной величины могут быть выражены как сумма свободных кумулянтов по всем непересекающимся разбиениям. Это свободный аналог формулы момента и кумулянтов в классической теории вероятности. См. также полукруговое распределение Вигнера.