Перегородка набора - Partition of a set

Набор марок, разделенных на пачки: ни одной марки нет в двух пачках, ни одна пачка не пуста, и каждая марка находится в пачке.
В 52 перегородки в комплекте с 5 элементов. Цветная область указывает на подмножество X, образующее член включающего раздела. Неокрашенные точки обозначают одноэлементные подмножества. Первый показанный раздел содержит пять одноэлементных подмножеств; последний раздел содержит одно подмножество из пяти элементов.
Традиционные японские символы для 54 глав « Повести о Гэндзи» основаны на 52 способах разделения пяти элементов (два красных символа представляют одно и то же разделение, а зеленый символ добавляется для достижения 54).

В математике , А разбиение множества представляет собой группировку из ее элементов в непустые подмножества , таким образом , что каждый элемент включен в точности одного подмножества.

Каждое отношение эквивалентности на множестве определяет разбиение этого множества, и каждое разбиение определяет отношение эквивалентности. Набор оснащен отношением эквивалентности или раздел иногда называют setoid , как правило , в теории типа и теории доказательств .

Определение и обозначения

Разбиение множества X - это набор непустых подмножеств X таких, что каждый элемент x в X находится ровно в одном из этих подмножеств (т. Е. X является дизъюнктным объединением подмножеств).

Эквивалентно, семейство множеств P является разбиением X тогда и только тогда, когда выполняются все следующие условия:

Наборы в P называются блоками , частями или ячейками раздела. Если тогда мы представляем ячейку, содержащую a, by . Другими словами, это обозначение ячейки в P, которая содержит a .

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

Ранг из P является | X | - | P | , Если X является конечным .

Примеры

  • Пустой набор имеет ровно одну секцию, а именно . (Примечание: это раздел, а не член раздела.)
  • Для любого непустого множества X , Р = { Х } есть разбиение X , называется тривиальное разбиение .
  • Для любого непустого собственного подмножества A множества U множество A вместе со своим дополнением образуют разбиение U , а именно { A , UA }.
  • Набор {1, 2, 3} имеет эти пять разделов (по одному разделу на элемент):
    • {{1}, {2}, {3}}, иногда пишется 1 | 2 | 3.
    • {{1, 2}, {3}} или 1 2 | 3.
    • {{1, 3}, {2}} или 1 3 | 2.
    • {{1}, {2, 3}} или 1 | 2 3.
    • {{1, 2, 3}} или 123 (в случаях, когда не будет путаницы с числом).
  • Следующие элементы не являются разделами {1, 2, 3}:
    • {{}, {1, 3}, {2}} не является разделом (любого набора), потому что один из его элементов является пустым набором .
    • {{1, 2}, {2, 3}} не является разделом (любого набора), потому что элемент 2 содержится более чем в одном блоке.
    • {{1}, {2}} не является разделом {1, 2, 3}, потому что ни один из его блоков не содержит 3; однако это раздел {1, 2}.

Разбиения и отношения эквивалентности

Для любого отношения эквивалентности на множестве X , множество ее классов эквивалентности является разбиение X . С другой стороны , из любого разбиения P из X , мы можем определить отношение эквивалентности на X с помощью параметра х ~ у именно тогда , когда х и у находятся в одной и той же части в P . Таким образом, понятия отношения эквивалентности и разбиения по существу эквивалентны.

Аксиома выбора гарантий для любого разбиения множества X существование подмножества X , содержащего ровно один элемент из каждой части перегородки. Это означает, что для данного отношения эквивалентности на множестве можно выбрать канонический репрезентативный элемент из каждого класса эквивалентности.

Доработка перегородок

Перегородки из 4-х комплектов упорядочены по доработке

Перегородка α из множества X является уточнением разбиения р из X й мы говорим , что α является более тонким , чем р и что ρ является грубее , чем альфа -ел каждый элемент альфа является подмножеством некоторого элемента р . Неформально это означает, что α является дальнейшим дроблением ρ . В этом случае написано, что αρ .

Это отношение тоньше, чем на множестве разбиений X, является частичным порядком (так что обозначение «≤» уместно). Каждый набор элементов имеет наименьшую верхнюю границу и наибольшую нижнюю границу , так что он образует решетку , а более конкретно (для разбиений конечного набора) это геометрическая решетка . Разбиение решетки из набора 4- х элементов имеет 15 элементов и изображен на диаграмме Хассе слева.

Эта решетка разбиений конечного множества, основанная на криптоморфизме между геометрическими решетками и матроидами , соответствует матроиду, в котором базовый набор матроида состоит из атомов решетки, а именно, разбиения с одноэлементными множествами и одного двухэлементного набора. установленный. Эти атомарные разбиения взаимно однозначно соответствуют ребрам полного графа . Матроид замыкание множества атомных перегородок является лучшим общим огрублением их всех; в терминах теории графов, это разбиение вершин полного графа на компоненты связности подграфа, образованного данным набором ребер. Таким образом, решетка разбиений соответствует решетке квартир графического матроида полного графа.

Другой пример иллюстрирует уточнение разделов с точки зрения отношений эквивалентности. Если D - это набор карт в стандартной колоде из 52 карт, отношение «тот же цвет-как» на D - которое можно обозначить ~ C - имеет два класса эквивалентности: наборы {красные карты} и {черные карты}. Двухчастное разбиение, соответствующее ~ C, имеет уточнение, которое дает отношение той же масти, что и ~ S , которое имеет четыре класса эквивалентности {пики}, {бубны}, {червы} и {трефы}.

Непересекающиеся перегородки

Разбиение множества N = {1, 2, ..., n } с соответствующим отношением эквивалентности ~ непересекающимся, если оно обладает следующим свойством: если четыре элемента a , b , c и d из N имеют a < b < c < d удовлетворяют a ~ c и b ~ d , тогда a ~ b ~ c ~ d . Название происходит от следующего эквивалентного определения: представьте, что элементы 1, 2, ..., n из N нарисованы как n вершин правильного n -угольника (в порядке против часовой стрелки). Затем можно визуализировать раздел, нарисовав каждый блок в виде многоугольника (вершины которого являются элементами блока). Таким образом, разбиение не пересекается тогда и только тогда, когда эти многоугольники не пересекаются.

Решетка непересекающихся разбиений конечного множества в последнее время приобрела важность из-за ее роли в свободной теории вероятностей . Они образуют подмножество решетки всех разбиений, но не подрешетку, поскольку операции соединения двух решеток не совпадают.

Подсчет разделов

Общее количество разбиений набора из n элементов - это число Белла B n . Первые несколько чисел Белла: B 0 = 1, B 1 = 1, B 2 = 2, B 3 = 5, B 4 = 15, B 5 = 52 и B 6 = 203 (последовательность A000110 в OEIS ). Числа Белла удовлетворяют рекурсии

и имеют экспоненциальную производящую функцию

Числа Белла также могут быть вычислены с использованием треугольника Белла, в котором первое значение в каждой строке копируется из конца предыдущей строки, а последующие значения вычисляются путем добавления двух чисел, числа слева и числа к указанному выше. слева от позиции. Числа Белла повторяются по обеим сторонам этого треугольника. Числа в треугольнике подсчитывают разделы, в которых данный элемент является наибольшим синглтоном .

Количество разбиений n -элементного множества ровно на k непустых частей - это число Стирлинга второго рода S ( n , k ).

Количество непересекающихся разделов набора n -элементов - это каталонское число C n , задаваемое формулой

Смотрите также

Примечания

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

  • Бруальди, Ричард А. (2004). Вводная комбинаторика (4-е изд.). Пирсон Прентис Холл. ISBN 0-13-100119-1.
  • Шехтер, Эрик (1997). Справочник по анализу и его основам . Академическая пресса. ISBN 0-12-622760-8.