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

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

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

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

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

1. $U_{\mathrm{\alpha <!--\; \alpha \; -->}}\cap <!--\; \cap \; -->U_{\mathrm{\beta <!--\; \beta \; -->}}=\mathrm{\varnothing <!--\; \varnothing \; -->}$$U_{{\alpha }}\cap U_{{\beta }}=\emptyset$  для любых $\mathrm{\alpha <!--\; \alpha \; -->},\mathrm{\beta <!--\; \beta \; -->}\in <!--\; \in \; -->A$$\alpha ,\beta \in A$ , таких что $\mathrm{\alpha <!--\; \alpha \; -->}\ne \mathrm{\beta <!--\; \beta \; -->}$$\alpha \not =\beta$ ;
2. $X=\underset{\mathrm{\alpha <!--\; \alpha \; -->}\in <!--\; \in \; -->A}{\bigcup <!--\; \bigcup \; -->}{U}_{\mathrm{\alpha <!--\; \alpha \; -->}}$$X=\bigcup \limits _{{\alpha \in A}}U_{{\alpha }}$ .

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

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

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

Например, число Стирлинга второго рода $S(n,m)$$S(n,m)$  представляет собой количество неупорядоченных разбиений n-элементного множества на m частей, в то время как мультиномиальный коэффициент $(\genfrac{}{}{0ex}{}{n}{k_1,k_2,\dots <!--\; \dots \; -->,k_m})$$\textstyle {\binom {n}{k_{1},\ k_{2},\ \dots ,\ k_{m}}}$  выражает количество упорядоченных разбиений n-элементного множества на m частей фиксированного размера $k_1,k_2,\dots <!--\; \dots \; -->,k_m$$k_{1},k_{2},\dots ,k_{m}$ . Количество всех неупорядоченных разбиений n-элементного множества задаётся числом Белла $B_n$$B_{n}$ .

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

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

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

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