Множества. Комбинаторика

Множества

Множество – это любая совокупность объектов, называемых элементами множества.

К примеру, буквами N, Z, Q, R, C обозначаются множества:

N (Naturalis) – натуральные числа;

Z (Zahlen) – целые числа;

Q (Quisque) – рациональные числа;

R (Realis) – действительные числа;

C (Complex) – комплексные числа.

 

a ∈ A – объект «а» есть элемент множества А (a принадлежит множеству А)

a ∉ А – объект «а» не является элементом множества А

 

Если каждый элемент множества А является элементом множества В, то говорят, что множество А является подмножеством множества В (А содержится в В) и обозначается А ⊂ В.

Если А ⊂ В и В ⊂ А, то множества равны А = В

Пустое множество (∅)не содержит объектов, но имеется в каждом множестве.

---

 

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

 

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

 

 

 

Множество, которое состоит из элементов, как множества А, так и множества В называется пересечением множества А и В, которое обозначается AB или АВ. Если A∩B = ∅, то значит, что множества не пересекаются.

 

 

Множество, которое состоит из элементов множества А, но не содержит элементов множества В называется разностью множеств А и В, которое обозначается АВ.

 

 

Если А является подмножеством В (А⊂В), то разность множеств (ВА) называют дополнением множества А до множества В, которое обозначается А^’_B .

Кстати, если рассматривается только одно конкретное подмножество, то чаще всего его просто называют дополнением и обозначают А’.

Отсюда следуют следующие равенства:

А∪А’ = B;     A∩A’ = ∅;   (A’)’ = A

Для любых подмножеств А и В множества U также следуют равенства:

(А∪В)’ = A’∩В’;     (A∩В)’ = А’∪ В’

Данные равенства называют законами двойственности (законы де Моргана).

---

Упорядоченные множества

Множество называется упорядоченным, если его элементы a и b обладают отношение порядка a ≤ b или b ≤ a, т.е (а не превосходит b или b не превосходит a), а также обладающие следующими свойствами:

• рефлексивности: (a ≤ a), т. е. ни один из элементов не превосходит самого себя;
• ассиметричности если (a ≤ b и b ≤ a), то элементы a и b равны;
• транзитивности: если a ≤ b, а b ≤ c, то и a ≤ c.

---

 

Размещения и перестановки

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

Обозначается число размещений: 

Формула вычисления числа размещений:

Размещением из n-элементов по n-элементов называют перестановками из n-элементов.

Обозначается число перестановок:

Формула вычисления числа перестановок:

 

Пример №1

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

И вот она, наша первая задачка.

Решается тут все довольно просто, главное правильно определить, где у нас множество, а где подмножество.

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

Итак, n — общее количество дисциплин (8), а k — количество предметов в понедельник (3).

Ответ: существует 336 способа составления расписания.

Пример №2

Сколько шестизначных чисел, кратных пяти можно составить из чисел: 1, 2, 3, 4, 5, 6, но при условии что в числе цифры не повторяются!

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

И чтобы найти количество шестизначных чисел кратных пяти, нужно найти число перестановок из пяти элементов, т.е. вычислить

Ответ: Из данных чисел можно составить 120 шестизначных чисел, кратных пяти.

---

 

Сочетания

Пусть имеется множество, состоящее из n-элементов. Каждое его подмножество, состоящее из k-элементов называется сочетанием из n-элементов по k-элементов. (не путайте с размещением).

Число всех сочетаний обозначается:

Вычисляется число сочетаний по формуле:

Также число сочетаний можно вычислить и по другой формуле: 

Пример №3

Проходит чемпионат страны по футболу (высшая лига), в котором участвуют 18 команд. Каждые две команды встречаются между собой дважды. Определить общее количество матчей в сезоне.

На самом деле, чтобы решить данную задачку можно прибегнуть к маленькой хитрости, а именно если всего команд 18 и каждые две играют между собой по два раза, то общее количество игр в сезоне можно найти перемножив общее количество команд (18) на общее количество команд минус 1 (18-1 = 17). В итоге 18*17 = 306 матчей.

Но комбинаторика советует все таки действовать по правилам и решить нашу задачу по формуле сочетания чисел, где n = 18 (равно количеству команд), а k = 2 (количество игр каждой команды с другой).

Итак,

Получилось не совсем то, что мы ожидали — правда?

Нет, мы решили все правильно) Просто мы нашли количество матчей в первом круге сезона (т.е. каждые команды сыграли между собой по одному разу), а так как во втором круге играется  ровно столько же матчей, то сложив их получим 153+153 = 306 матчей. Задача решена))

Ответ: в течение всего сезона будет сыграно 306 матчей.

Решим еще несколько примеров, в качестве закрепления

ПРИМЕР №4 Никакие три диагонали выпуклого десятиугольника не пересекаются в одной точке. Определить число точек пересечения диагоналей.

Можно перепроверить другим способом: число точек пересечения диагоналей выпуклого n-угольника, лежащих внутри этого многоугольника можно найти по формуле:

Посчитаем для нашего случая: 10*9*8*7:24 = 210

Ответ: 210 точек

ПРИМЕР №5 Сколько различных десятизначных чисел можно записать, используя только цифры 1 и 2.

Если число, записанное единицами и двойками, содержит десять цифр, то таких чисел будет:

Ответ: 1024 числа

ПРИМЕР №6 Сколькими способами можно упаковать 9 разных книг в 5 бандеролей, если 4 бандероли должны содержать по 2 книги.

1. выбираем книгу в маленькую бандероль — 9 способов;
2.  из оставшихся 8 выбираем пару книг в первую бандероль 8*7, причем так как у нас получается дублирующие случаи (сначала берем 1, потом 3 или сначала 3, потом 1 книги) , делим пополам;
3.  аналогично заполняем третью, четвертую и пятую бандероли.

В итоге получаем:

Ответ: 945 способов.

 

Спасибо за внимание, я надеюсь все разобрались с данной темой.

Если вам что-то непонятно (или нашли неточности в уроке) пишите в комментариях и мы вам обязательно ответим в ближайшее время.