Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

А. Неупорядоченные разбиения с фиксированными размерами частей



Неупорядоченное разбиение 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 ≤ kn; 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; Прочитано: 1783 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...