Элементы комбинаторного анализа

Глава 1

Элементы комбинаторного анализа

1.1. Начальные понятия теории множеств

Под множеством понимают объединение в единое целое определенных вполне различаемых объектов. Объекты при этом называют элементами образуемого ими множества.

Для обозначения множеств используют прописные буквы, а для обозначения элементов множеств – строчные буквы латинского алфавита.

Запись означает, что является элементом множества ; в противном случае пишут .

Множество называют конечным , если оно содержит конечное число элементов, и бесконечным , если оно содержит бесконечное число элементов. Множество, не содержащее элементов, называют пустым и обозначают символом .

Число элементов конечного множества называют его мощностью и обозначают .

Множество можно описать, указав свойство, присущее элементам только этого множества. Множество всех объектов, обладающих свойством , обозначают так: .

Конечное множество можно задать путем перечисления его элементов, т.е. .

Если каждый элемент множества есть элемент множества B , то говорят, что есть подмножество и записывают .

Заметим, что пустое множество считают подмножеством любого множества.

Если и , то говорят, что множества и равны , и пишут: .

Если и , то называют собственным подмножеством .

Обычно в конкретных рассуждениях элементы всех множеств берут из некоторого одного, достаточно широкого множества (в каждом случае своего), которое называют универсальным и обозначаютI .

Пусть A и B - подмножества универсального множества I . Введем следующие операции над множествами :

Название операции	Обозначение операции	Определение операции	Геометрическая иллюстрация
Объединение A и B
Пересечение A и B
Разность A и B
Дополнение A
Декартово произведение A и B	, здесь - упорядоченная пара

В последнем столбце таблицы приведены диаграммы Эйлера, которые служат для наглядного пояснения операций. Области на этих диаграммах соответствуют множествам, над которыми операция производится. Штриховкой выделены области, соответствующие тем множествам, которые являются результатами совершения операций.

Свойства операций над множествами

Пусть задано универсальное множество I . Тогда для любых множеств выполняются следующие свойства:

коммутативные законы :

1. ; 2. ;

ассоциативные законы :

3.;

4. ;

дистрибутивные законы :

5.;

6. ;

законы идемпотентности :

7. ; 8. ;

законы де Моргана :

9. ; 10. ;

законы нуля :

11. ; 12. ;

законы единицы :

13. ; 14. ;

законы поглощения :

15. ; 16. ;

законы дополнения :

17. ; 18. ;

закон двойного дополнения :

19. .

Операции объединения, пересечения и декартового произведения можно обобщить на случай произвольного конечного числа участников.

Декартовым произведением n множеств называют множество

.

В частном случае одинаковых сомножителей декартово произведение обозначают .

Объединением множеств называют множество, любой элемент которого является элементом хотя бы одного из данных множеств. Обозначение: или .

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

Если , то множества и называются непересекающимися .

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

Утверждение 1. Если между конечными множествами и существует взаимно однозначное соответствие, то .

Утверждение 2. Если - конечные попарно непересекающиеся множества, то множество также конечно и .

Утверждение 3 (принцип включения-выключения). Если - конечные множества, то множество также конечно и

.

Утверждение 4. Если - конечные множества, то множество также конечно и .

1.2. Комбинаторные объекты и комбинаторные числа

В комбинаторном анализе изучаются различные объекты, порождаемые элементами из конечного множества , а также числовые характеристики этих объектов.

При подсчете числа объектов с наперед заданными свойствами используются следующие два правила.

Правило суммы. Если объект может быть выбран способами, а объект способами, то выбор «либо , либо » может быть осуществлен способами.

Правило произведения. Если объект может быть выбран способами и после каждого из таких выборов объект в свою очередь може

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать