Разбиение набора

• Определение и свойства разбиений

  • Разбиение множества 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 элементов — это каталонское число.