Перейти к содержанию

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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

Определение

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

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

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

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

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

Например, число Стирлинга второго рода [math]\displaystyle{ S(n,m) }[/math] представляет собой количество неупорядоченных разбиений n-элементного множества на m частей, в то время как мультиномиальный коэффициент [math]\displaystyle{ \textstyle\binom{n}{k_1,\ k_2,\ \dots,\ k_m} }[/math] выражает количество упорядоченных разбиений n-элементного множества на m частей фиксированного размера [math]\displaystyle{ k_1, k_2, \dots, k_m }[/math]. Количество всех неупорядоченных разбиений n-элементного множества задаётся числом Белла [math]\displaystyle{ B_n }[/math].

Примеры

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

См. также