WikiSort.ru - Не сортированное

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

Определение

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

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

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

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

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

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

Примеры

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

См. также

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