 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
А. Неупорядоченные разбиения с фиксированными размерами частей
|
|
Неупорядоченное разбиение n -элементного множества X — это любое семейство { X 1, X 2,…, X k}, где 1≤ k≤п; X 1, X 2,…, X k - непустые попарно непересекающиеся подмножества множества X, объединение которых равно X.
Называем такое разбиение неупорядоченным, так как семейство — это неупорядоченная совокупность.
Пример. Для множества {а,b,с} неупорядоченное разбиение это, например, {{а},{b,с}}. Причем {{а},{b,с}}={{b,с},{а}}.
Для множества с п элементами обозначим через D (n; k 1, k 2,…, k n) число всех таких неупорядоченных разбиений, в которых есть k 1 подмножеств с одним элементом, k 2 подмножеств с двумя элементами и т.д., где k 1≥0, k 2≥0,…, k n≥0; k 1+2 k 2+…+ n k n= n.
Имеем
5б. Упорядоченные разбиения с фиксированными размерами частей
Упорядоченным разбиением конечного множества X с n элементами называется любой кортеж вида < X 1, X 2,…, X k>, где 1 ≤ k ≤ n; X 1, X 2,…, X k - непустые попарно непересекающиеся, подмножества множества X, объединение которых равно X.
Называем такое разбиение упорядоченным, так как элементы кортежа упорядочены.
Пример. Для множества {а,b,с} упорядоченное разбиение это, например, кортеж < {{а},{b,с}} >. Причем < {{а},{b,с}}> ¹< {{b,с},{а}} > .
Для множества с п элементами обозначим через E (n; m 1, m 2,…, m k,) число всех таких упорядоченных разбиений на подмножества X 1, X 2,…, X k, содержащие m 1, m 2,…, m k, где m 1≥0, m 2≥0,…, m k≥0; m 1+ m 2+…+ m k= n.
Число всех упорядоченных разбиений < X 1, X 2,…, X k> множества с п элементами на подмножества X 1, X 2,…, X k, содержащие m 1, m 2,…, m k, элементов соответственно. определяется по полиномиальной формуле E (n; m 1, m 2,…, mk)= 
, где m 1≥0, m 2≥0,…, m k≥0; m 1+ m 2+…+ m k= n.
2. Разбиения множества на k блоков с не фиксированными размерами частей
Определение. Упорядоченнымразбиением множества A на k блоков называется семейство множеств R = { A 1,..., Ak } таких, что 
, 
для любых 
и для всех i 
{1, …, k }.
Любому разбиению множества на блоки можно взаимно однозначно сопоставить отношение эквивалентности Q, заданное на множестве 
, в котором элемент х находится в отношении Q с элементом y тогда и только тогда, когда элементы х и y принадлежат одному блоку разбиения. Поэтому задачи на разбиения часто встречаются на практике там, где возникают классы эквивалентности.
Например, отношению "2 x + y делится на 3", заданному на множестве {1,..., 10}, соответствует разбиение R = {{1, 4, 7, 10}, {2, 5, 8}, {3, 6, 9}}.
Дата публикования: 2014-11-03; Прочитано: 1784 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
