3. Покрытия и разбиения множеств, характеристическая функция

Система множеств {X₁,…,X_k} называется покрытием множества X, если X=X₁…X_k. Разбиением множества X называется его покрытие {X₁,…,X_k}, если X_iX_j= для различных i,j{1,…,k}.

Подмножества X₁,…,X_k множества X называются блоками покрытия (разбиения), число k блоков – порядком покрытия (разбиения). Последовательность записи блоков несущественна в силу коммутативности операции разбиения. Тривиальным блоком разбиения называют одноэлементный блок.

Разбиение {Y₁,…,Y_m} множества X называется продолжением разбиения {X₁,…,X_k} того же множества, если для любого i=1,…,m найдётся номер j{1,…,k} такой, что Y_iX_j. Отсюда следует, что mk.

Для разбиения конечного множества Х выполнено правило суммы:

X=X₁+…+X_k,

Для точного подсчёта или оценки порядка множества X через порядки блоков покрытия используется метод включения-исключения.

x_n(-1)^n-1 x₁…x_n-1=(-1)ⁿ x₁…x_n. u

Теорема 2.1. Мощность объединения конечного числа множеств равна:

X₁…X_k= .

Приведем формулу включения-исключения в более общем виде.

Пусть имеется n элементов и k свойств z₁,…,z_k, которыми обладает или не обладает каждый из элементов. Обозначим через n(t₁,…,t_i) число элементов, обладающих свойствами (и, может быть, некоторыми другими), где {t₁,…,t_i}{1,…,k}, и через n_ - число предметов, не обладающих ни одним из свойств z₁,…,z_k.

Теорема 2.2. Число n_ определено формулой:

n_=n-s₁+s₂+…+(-1)ⁱs_i+…+(-1)^ks_k,

где числа s_i определены формулой, i=1,…,k:

s_i= .

t Следует из теоремы 2.1 и равенства n_=X-X₁…X_k, где X_i – множество элементов, обладающих i–м свойством, i=1,...,k. u

Пусть n_r – число элементов, обладающих ровно r свойствами, r{1,…,k}.

Теорема 2.3. Число n_r определено формулой:

n_r= - +…+(-1)^k-r .

2.4. Урновые схемы

Урновыми схемами в комбинаторике называют схемы распределения элементов произвольной природы по некоторому множеству классов. Часто такие схемы интерпретируют как размещение шаров по урнам, частиц по ячейкам и пр.

Таблица 2.2. Число способов разместить n шаров по k урнам

№	Различимы ли шары?	Различимы ли урны?	Допустима ли пустая урна? Если нет, то n>k	Nсп
1	да	да	да	kn
2	нет	да	да
3	нет	да	нет

Урновые схемы характеризуются определенным многообразием: урны и шары могут различаться по свойствам, например, урны - по вместимости, шары – по цвету, порядок размещения шаров по урнам учитывается или не учитывается. Урновые схемы связаны со схемами выборок, но имеют свою специфику. В таблице 2.2 приведено N_сп - число способов разместить n шаров по k урнам при различных условиях.

Задачи, связанные с учетом ограничений на число шаров того или иного типа или на вместимость той или иной урны, решаются более сложными методами, например, методами производящих функций.

16