История создания компьютеров и принципы их работы

Информационные модели

Компьютерные технологии

Современные информационные технологии

Математика как наука

Элементы теории множеств и комбинаторики

Событие и вероятность

Случайные величины

Элементы математической статистики

Указания к лабораторным работам

Задачи по курсу математики

Литература

Тема 7. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ И КОМБИНАТОРИКА

7.1. Понятие множества. Подмножества
7.2. Операции над множествами
7.3. Основные формулы комбинаторики
7.4. Контрольные вопросы

7.1. Понятие множества. Подмножества

Под множеством понимают объединение в одно целое объектов, связанных между собой неким свойством. Термин "множество" в математике не всегда обозначает большое количество предметов, оно может состоять и из одного элемента и вообще не содержать элементов, тогда его называют пустым и обозначают Ж.
Множество B называют подмножеством множества А, если любой элемент множества В является элементом множества А. Обозначается В М А.

Свойства включения множеств:

1. Пустое множество является подмножеством любого множества: Ж М А.
   
2. Любое множество является подмножеством самого себя, т. е. для любого множества А справедливо включение А М А.
   
3. Если А - подмножество множества В, а В - подмножество множества С, то А - подмножество множества С.

Универсальное множество - это самое большее множество, содержащее в себе все множества, рассматриваемые в данной задаче.
На диаграмме Эйлера - Венна универсальное множество обозначают в виде прямоугольника и буквы U:

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

Равными называются множества, состоящие из одних и тех же элементов.

Два множества равны, если каждое из них является подмножеством другого (A = B Ы (A М B и В М А)).

Множества не равны, если хотя бы в одном множестве существует хотя бы один элемент, не принадлежащий другому множеству.

Объединением множеств А и В называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А или В. Обозначается AB.

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

Свойства объединения множеств:
1.
2.
3.
4.
5.
6.
Пересечением множеств А и В называется множество, состоящее из всех элементов, принадлежащих обоим множествам А и В. Обозначается А З В.

Свойства пересечения множеств:
1.
2.
3.
4.
5.
6.
Разностью множеств А и В называется множество элементов, принадлежащих множеству А, которые не принадлежат множеству В. Обозначается А \ В.

Свойства разности множеств:
1. Если то А \ В = А.
2. Если А М В, то А \ В = Ж.
3. А \ В = А \ (АВ).
Разность между универсальным множеством U и множеством А называется дополнением множества А. Обозначается = U \ A.

Свойства разности и дополнения:

7.3. Основные формулы комбинаторики

На практике часто приходится выбирать из некоторого множества объектов подмножества элементов, обладающих теми или иными свойствами, располагать элементы одного или нескольких множеств в определенном порядке и т. д. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют "комбинаторные задачи".

Комбинаторика занимается различного рода соединениями, которые можно образовать из элементов некоторого конечного множества. Термин "комбинаторика" происходит от латинского combina - сочетать, соединять.

Комбинаторика - область математики, в которой рассматриваются задачи о тех или иных комбинациях объектов.

Правило суммы: пусть имеется n попарно непересекающихся множеств A₁, A₂, …, A_n, содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно

m₁ + m₂ + … + m_n.

Кортеж - конечная последовательность (допускающая повторения) элементов какого-нибудь множества.
Правило произведения: пусть имеется n множеств A₁, A₂, …, A_n содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества, т. е. построить кортеж (а₁, а₂, ..., а_n), где а_i О А_i1 (i = 1, 2, …, n), равно

m₁ · m₂ · … · m_n .

Размещениями из n элементов по m элементов (m < n) называются комбинации, составленные из данных n элементов по m элементов, которые отличаются либо самими элементами, либо порядком элементов.
Размещения без повторений (n различных элементов):

Размещения с повторениями (n различных элементов, элементы могут повторяться):

Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?
1) Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.

2) Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

Перестановками из n элементов называются размещения из этих n элементов по n. Перестановки - частный случай размещений.
Перестановки без повторений (n различных элементов):

Перестановки c повторениями (k различных элементов, где элементы могут повторяться m₁, m₂, …, m_k раз и m₁ + m₂ + … + m_k = n, где n - общее количество элементов):

Пример. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?
1) Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

Сочетаниями из n элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом.
Отличие сочетаний от размещений в том, что в сочетаниях не учитывается порядок элементов.
Сочетания без повторений (n различных элементов, взятых по m):

Сочетания c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться):

Пример. Возьмем плоды: банан (Б), ананас (А) и репа (Р). Какие сочетания из этих плодов, взятых по два, можно получить? Сколько таких наборов получится, если: 1) плоды в наборе не повторяются; 2) можно брать по два одинаковых плода?
1) Получатся наборы: БА ("банан, ананас" и "ананас, банан" - один и тот же набор), АР и РБ.

2) Получатся наборы: ББ, БА, БР, АА, АР, РР.

Вопросы

1. Приведите примеры множеств и их подмножеств.
2. Проиллюстрируйте примерами "из жизни" пересечение, объединение и разность множеств.
3. Постройте диаграммы Эйлера - Венна на свойства разности и дополнения множеств.
4. Назовите виды комбинаций, где важен порядок при составлении наборов и где он не важен.

Ключевые слова

множества, подмножества, пересечение, объединение, разность, комбинаторика, размещения, перестановки, сочетания.