- Разбиение множества
-
Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.
Определение
Пусть
— произвольное множество. Семейство непустых множеств
, где
— некоторое множество индексов (конечное или бесконечное), называется разбиением
, если:
для любых
, таких что
;
.
При этом множества
называются блоками или частями разбиения данного множества
.
Разбиения конечных множеств
Разбиения конечных множеств, а также подсчет количества различных разбиений, удовлетворяющих тем или иным условиям, представляет особый интерес в комбинаторике. В частности, некоторые комбинаторные функции естественно возникают как количества разбиений того или иного вида.
Например, число Стирлинга второго рода
представляет собой количество неупорядоченных разбиений n-элементного множества на m частей, в то время как мультиномиальный коэффициент
выражает количество упорядоченных разбиений n-элементного множества на m частей фиксированного размера
. Количество всех неупорядоченных разбиений n-элементного множества задается числом Белла
.
Примеры
, где
— множества всех целых чисел, чётных целых чисел и нечётных целых чисел соответственно;
- Множество всех вещественных чисел
может быть представлено в виде:
;
- Множество из трех элементов
может быть разбито пятью способами:
,
,
,
,
— значит, число Белла
.
Категории:- Комбинаторика
- Теория множеств
Wikimedia Foundation. 2010.