Разбиение множества

Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся непустых подмножеств.

Разбиение множества.

ОпределениеПравить

Пусть   — произвольное множество. Семейство непустых множеств  , где   — некоторое множество индексов (конечное или бесконечное), называется разбиением  , если:

  1.   для любых  , таких что  ;
  2.  .

При этом множества   называются блоками или частями разбиения данного множества  .

Разбиения конечных множествПравить

Разбиения конечных множеств, а также подсчёт количества различных разбиений, удовлетворяющих тем или иным условиям, представляет особый интерес в комбинаторике. В частности, некоторые комбинаторные функции естественно возникают как количества разбиений того или иного вида.

Например, число Стирлинга второго рода   представляет собой количество неупорядоченных разбиений n-элементного множества на m частей, в то время как мультиномиальный коэффициент   выражает количество упорядоченных разбиений n-элементного множества на m частей фиксированного размера  . Количество всех неупорядоченных разбиений n-элементного множества задаётся числом Белла  .

ПримерыПравить

  •  , где   — множества всех целых чисел, чётных целых чисел и нечётных целых чисел соответственно;
  • Множество всех вещественных чисел   может быть представлено в виде:  ;
  • Множество из трёх элементов   может быть разбито пятью способами:  ,  ,  ,  ,   — значит, число Белла  .

См. такжеПравить