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

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

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

Определение

Пусть $X$ — произвольное множество. Семейство непустых множеств $\{U_{\alpha }\}_{\alpha \in A}$, где $A$ — некоторое множество индексов (конечное или бесконечное), называется разбиением $X$, если:

1. $U_{\alpha }\cap U_{\beta }=\emptyset$ для любых $\alpha ,\beta \in A$, таких что $\alpha \not =\beta$;
2. $X=\bigcup \limits _{\alpha \in A}U_{\alpha }$.

При этом множества $\ U_{\alpha }$ называются блоками или частями разбиения данного множества $X$.

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

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

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

Примеры

• $\mathbb {Z} =(2\mathbb {Z} )\cup (2\mathbb {Z} +1)$, где $\mathbb {Z} ,2\mathbb {Z} ,2\mathbb {Z} +1$ — множества всех целых чисел, чётных целых чисел и нечётных целых чисел соответственно;
• Множество всех вещественных чисел $\mathbb {R}$ может быть представлено в виде: $\mathbb {R} =\cup _{n\in \mathbb {Z} }[n,n+1)$;
• Множество из трёх элементов $\{a,b,c\}$ может быть разбито пятью способами: $\{\{a,b,c\}\}$, $\{\{a\},\{b,c\}\}$, $\{\{b\},\{a,c\}\}$, $\{\{c\},\{a,b\}\}$, $\{\{a\},\{b\},\{c\}\}$ — значит, число Белла $B(3)=5$.

См. также

• Замощение
• Разбиение числа