Основные правила комбинаторики

Тема 2. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

Алгебраические свойства операций над множествами

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

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

А

В

Подмножеством A множества B (AÍB) или (A содержится в B) называется множество A, каждый элемент которого принадлежит B. Графически это изображается с помощью кругов Эйлера, как показано на рисунке.

Пустое множество есть подмножество любого множества.

Совокупность всех подмножеств множества А называется множеством-степенью и обозначается P(А), то есть P(А) ={ В ç В Í А }.

Множества A и B называются равными (A=B), если AÍB и BÍA.

Множество, не содержащее ни одного элемента, называется пустым и обозначается Ø. Совокупность всех допустимых объектов в рамках решаемой задачи называется универсальным множеством и обозначается U.

Дополнением множества A называется множество Ā, состоящее из элементов универсального множества, не являющихся элементами множеством A.

Пересечение множеств A Ç B, есть множество элементов принадлежащих A и B.

Объединение AÈB есть множество всех элементов принадлежащих A или B. Следует иметь в виду, что существуют два значения союза или:

1) «исключающее или» - либо то, либо другое и третьего не дано;

2) «не исключающее или» - то или другое, или то и другое вместе.

В определении объединения множеств подразумевается второе “не исключающее или”, то есть элемент может принадлежать только A, только B, а также одновременно этим множествам

Разность A\B, есть множество, состоящее из элементов A, не входящих в множество В.

Симметричная разность

1. идемпотентность
1.1. AÈA=A	1.2. AÇA=A
2. коммутативность
2.1. AÈ B=BÈA	2.2 AÇB=BÇA
3. ассоциативность
3.1. AÈ(BÈC)=(AÈB)ÈC	3.2 AÇ(BÇC)=(AÇB)ÇC
4 дистрибутивность
4.1. AÈ(BÇC)=(AÈB)Ç(AÈC)	4.2 AÇ(BÈC)=(AÇB)È(AÇC)
5. поглощение
5.1. AÈ(AÇB)=A	5.2. AÇ(AÈB)=A
6. свойства нуля
6.1. AÈØ=A	6.2. AÇØ=A
7. свойства единицы
7.1. AÈU= U	7.2. AÇU=A
8. инволютивность
9. законы де Моргана
9.1.	9.2
10. дополнительность
10.1. AÈĀ=U	10.2 AÇĀ=Ø

Комбинаторика – раздел математики, связанный с решением задач выбора и размещения элементов конечного множества в соответствии с заданными правилами.

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

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

Большинство комбинаторных задач решается с помощью двух основных правил - правила суммы и правила произведения.

Правило суммы. Пусть A, B – конечные множества, |A| = n, |B| = m.

,

следовательно

.

Комбинированная интерпретация.

Если некоторый объект A можно выбрать n способами, а другой объект B можно выбрать m способами, то выбор "либо A, либо B " можно осуществить n+m способами.

Правило произведения. Если мощность |A| = n, |B| = m, то.

Комбинаторная интерпретация.

Если объект A можно выбрать n способами, а после каждого такого выбора другой объект B можно выбрать (независимо от выбора объекта A) m способами, то пары объектов A и B можно выбрать способами.

Пусть, и | А | - число элементов множества A. Составим декартово произведение множеств A и B, т.е. множество пар.

Тогда правило произведения записывается следующим образом:

Пример. Сколько всего существует двузначных чисел?

Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то A = {1, 2,..., 9}, B = {0, 1, 2,..., 9} и,

Дата добавления: 2014-01-11