Оглавление
Разбиение набора
-
Определение и свойства разбиений
- Разбиение множества X – это набор непересекающихся подмножеств, называемых блоками, которые покрывают X.
- Разбиение является конечным, если множество блоков конечно.
- Разбиение является точным, если каждый элемент X принадлежит ровно одному блоку.
- Разбиение является строгим, если каждый блок непуст.
-
Примеры разбиений
- Пустое множество имеет одно разбиение, состоящее из одного пустого блока.
- Одноэлементное множество имеет одно разбиение, состоящее из одного блока.
- Разбиение множества {1, 2, 3} может быть представлено как 1 | 2 | 3 или 1 2/3 или 1 3/2 или 1/2 3 или 123.
- Разбиение {1, 2} не является разделением {1, 2, 3}, так как ни один из блоков не содержит 3.
-
Разбиения и отношения эквивалентности
- Разбиение множества X является множеством классов эквивалентности отношения эквивалентности на X.
- Из любого разбиения можно определить отношение эквивалентности, установив x ~ y, если x и y находятся в одной части.
- Разбиения и отношения эквивалентности являются эквивалентными понятиями.
-
Уточнение и упорядочение разбиений
- Разбиение α является уточнением разбиения ρ, если каждый элемент α является подмножеством элемента ρ.
- Разбиения образуют решетку, которая является геометрической и сверхразрешимой.
- Решетка разбиений соответствует матроиду, где атомарные разбиения соответствуют ребрам полного графа.
-
Непересекающиеся разделы
- Разбиение множества N является непересекающимся, если блоки не пересекаются.
- Непересекающиеся разбиения имеют важное значение в теории свободных вероятностей.
-
Подсчет разделов
- Общее количество разделов набора из n элементов равно числу колокола Bn.
- Числа колокола удовлетворяют рекурсии и имеют экспоненциальную производящую функцию.
- Число разбиений n-элементного множества на k частей равно числу Стирлинга второго рода S(n, k).
- Число непересекающихся разделов набора из n элементов – это каталонское число.
Полный текст статьи: