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

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

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

Определение

Пусть $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$.

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

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

Например, число Стирлинга второго рода $S(n,m)$ представляет собой количество неупорядоченных разбиений n-элементного множества на m частей, в то время как мультиномиальный коэффициент $\textstyle\binom{n}{k_1,\ k_2,\ \dots,\ k_m}$ выражает количество упорядоченных разбиений n-элементного множества на m частей фиксированного размера $k_1, k_2, \dots, k_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$.