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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение[править | править вики-текст]

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

См. также[править | править вики-текст]