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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Розбиття множини.

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

Означення

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

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

XS: XM
Xi, XjS: XiXjXiXj = ∅.
  • об'єднання всіх множин, які входять в розбиття M, дає множину M:

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

Приклади

[ред. | ред. код]
  • Кожна одноелементна множина {x} має лише один елемент розбиття — { {x} }.
  • Для кожної непорожньої множини X, P = {X} є поділом даної множини, цей поділ називається тривіальним.
  • Для кожної непорожньої підмножини A множини U є справедливим те, що {A, UA} є розбиттям множини 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-елементної множини дорівнює числу Белла: Cn, Числом Белла називається число всіх невпорядкованих розбиттів n-елементної множини, при цьому, за означенням вважають .

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

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

.

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

.