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

Шаблон:Значения Разбие́ние множества — представление множества $X$ в виде объединения произвольного количества попарно непересекающихся непустых подмножеств: $X = ⨄_{α \in A} U_{α}$ . Множества $U_{α}$ в этом случае называются блоками или частями разбиения.

Разбиения конечных множеств, а также подсчёт количества различных разбиений, удовлетворяющих тем или иным условиям, представляет особый интерес в комбинаторике. В частности, некоторые комбинаторные функции естественно возникают как количества разбиений того или иного вида. Например, числа Стирлинга второго рода представляют собой количество неупорядоченных разбиений $n$ -элементного множества на $m$ частей, в то время как мультиноминальный коэффициент выражает количество упорядоченных разбиений $n$ -элементного множества на $m$ частей. Количество всех неупорядоченных разбиений $n$ -элементного множества задаётся числом Белла $B_{n}$ . Например, множество из трёх элементов ${a, b, c}$ может быть разбито пятью способами: ${{a, b, c}}$ , ${{a}, {b, c}}$ , ${{b}, {a, c}}$ , ${{c}, {a, b}}$ , ${{a}, {b}, {c}}$ — значит, число Белла $B (3) = 5$ .

Примеры разбиений бесконечных множеств: множество целых чисел $ℤ$ разбивается на раздельную сумму множеств чётных чисел $2 ℤ$ и нечётных чисел $2 ℤ + 1$ ; множество вещественных чисел $ℝ$ может быть представлено в виде раздельного объединения счётного числа полуинтервалов $ℝ = ⨄_{n \in ℤ} [n, n + 1)$ .

Основополагающую роль разбиения играют в комбинаторной геометрии: задачи замощения и разбиения тела на составные части, в частности, опровергнутая гипотеза Борсука (существует ли разбиение тела конечного единичного диаметра в $n$ -мерном евклидовом пространстве разбить на не более чем $n + 1$ частей так, что диаметр каждой части будет меньше 1) оказали решающее влияние на развитие направления.

Также разбиения широко применяются в теории вероятностей, в частности, разбиения вероятностного пространства — полные группы событий.

Литература

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

Литература

Навигация

Поиск