6. Сочетания с повторениями. Разбитие множеств на части

Пусть даны два натуральных числа n и k, k ≤ n. Пусть также у нас имеется набор предметов n различных сортов. Элементы одного сорта считаются одинаковыми, причем количество элементов одного сорта — неограниченно. Произвольный набор из k предметов называется сочетанием с повторениями из n элементов по k.

Пример.

Пусть в коробке лежат шары трех цветов—красного, синего и зеленого. Шары одного цвета считаются одинаковыми. Вопрос: сколькими способами можно составить набор из двух шаров?  Легко видеть, что это задача на определение числа сочетаний с повторениями. Пусть “к” означает произвольный красный шар, “c”—синий и “з”—зеленый. Тогда все сочетания с повторениями этих трех сортов по два суть : {с,к}, {с,с}, {с,з}, {з,к}, {з,з}, {к,к}. Число сочетаний с повторениями из n элементов по k обозначается ar{C}^k_n и равно C^k_n+k-1

Разбиение множества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.

Определение

Пусть X — произвольное множество. Семейство непустых множеств  , где A — некоторое множество индексов (конечное или бесконечное), называется разбиениемX, если:

1.  для любых  , таких что  ;

2. .

При этом множества   называются блоками или частями разбиения данного множества X.

Разбиения конечных множеств

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

Например, число Стирлинга второго рода S(n,m) представляет собой количество неупорядоченных разбиений n-элементного множества на m частей, в то время какмультиномиальный коэффициент   выражает количество упорядоченных разбиений n-элементного множества на m частей фиксированного размера  . Количество всех неупорядоченных разбиений n-элементного множества задается числом Белла B_n.

Примеры

• , где   - множества всех целых чисел, чётных целых чисел и нечётных целых чисел соответственно;

• Множество всех вещественных чисел   может быть представлено в виде:  ;

• Множество из трех элементов {a,b,c} может быть разбито пятью способами: {{a,b,c}}, {{a},{b,c}}, {{b},{a,c}}, {{c},{a,b}}, {{a},{b},{c}} — значит, число Белла B(3) = 5.

7. Отношения. Представления и свойства отношений

8. Отношения эквивалентности. Связь отношений эквивалентности и разбиений множеств

Отношение эквивалентности (∼) на множестве X — это бинарное отношение, для которого выполнены следующие условия:

1. Рефлексивность:   для любого a в X,

2. Симметричность: если  , то  ,

3. Транзитивность: если   и  , то  .

Запись вида « » читается как «a эквивалентно b».

Связанные определения

• Классом эквивалентности C(a) элемента a называется подмножество элементов, эквивалентных a. Из вышеприведённого определения немедленно следует, что, если  , то C(a) = C(b).

Множество всех классов эквивалентности обозначается X / ∼.

• Для класса эквивалентности элемента a используются следующие обозначения: [a], a / ∼,  .

• Множество классов эквивалентности по отношению ∼ является разбиением множества.