Розбиття множини

Розбиття множини.

Розбиття множини — це подання її у вигляді об'єднання довільної кількості непорожніх підмножин, які попарно не перетинаються.

Означення

52 розбиття множини, яка складається з 5 елементів

Традиційні японські символи глав «Повісті про Ґендзі» базуються на 52 способах розбиття п'яти-елементної множини.

Система множин S={X₁ … X_n} називається розбиттям множини M, якщо ця система задовольняє такі умови:

• будь-яка множина X_k з S є підмножиною множини M:

∀X∈S: X⊆M

• будь-які дві множини X_i, X_j з S мають порожній перетин:

∀X_i, X_j ∈ S: X_i≠X_j→X_i∩X_j = ∅.

• об'єднання всіх множин, які входять в розбиття M, дає множину M:

$\bigcup _{X\in S}X=M$

Розбиття множини можна задати за допомогою задання на ній відношення еквівалентності. Утворене розбиття називатиметься фактор-множиною за даним відношенням еквівалентності (позначається А/~), а його елементи — класами еквівалентності.

Приклади

• Кожна одноелементна множина {x} має лише один елемент розбиття — { {x} }.
• Для кожної непорожньої множини X, P = {X} є поділом даної множини, цей поділ називається тривіальним.
• Для кожної непорожньої підмножини A множини U є справедливим те, що {A, U−A} є розбиттям множини U. Тобто підмножина та її алгебраїчне доповнення утворюють розбиття множини U.

• Множина{ 1, 2, 3 } має наступні п'ять поділів:
  • { {1}, {2}, {3} }, у англомовній літературі іноді записують 1|2|3.
  • { {1, 2}, {3} }, або 12|3.
  • { {1, 3}, {2} }, або 13|2.
  • { {1}, {2, 3} }, або 1|23.
  • { {1, 2, 3} }, чи 123 (якщо у даному контексті не виникає плутанини з числами).
• Наступні множини не є розбиттям множини { 1, 2, 3 }:
  • { {}, {1, 3}, {2} } не є розбиттям жодної множини, адже в ній присутній порожній елемент.
  • { {1}, {2} } не є розбиттям {1, 2, 3} адже жодна множина не містить елемента 3; однак, дана множина є розбиттям для {1, 2}.

Зв'язок між відношенням еквівалентності та розбиттям множини

Для кожного еквівалентного відношення X, множина класів еквівалентності є розбиттям множини X. Тобто будь-яке відношення еквівалентності на множині A визначає розбиття множини A, причому, серед елементів розбиття немає порожніх. Це розбиття єдине. І, навпаки, всяке розбиття множини A, яке не містить порожніх елементів, визначає відношення еквівалентності на множині A. Отже, поняття відношення еквівалентності та розбиття множини є, по суті, еквівалентними.

Кількість розбиттів

Загальна кількість поділів довільної n-елементної множини дорівнює числу Белла: C_n, Числом Белла $B_{n}$ називається число всіх невпорядкованих розбиттів n-елементної множини, при цьому, за означенням вважають $B_{0}=1$.

Число Белла можна обчислити як суму чисел Стірлінга другого роду:

$B_{n}=\sum _{m=0}^{n}S(n,m)$

Для чисел Белла справедлива також формула Добинського:

$B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}$.

Генератриса чисел Белла має вигляд

$\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=e^{e^{x}-1}$.