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

(объекты), составляющие множество, называют его элементами
Предложение «объект a является элементом

множества A» записывается а ∈ А
Множество, не содержащее ни одного элемента, называют пустым и обозначают .

B, то говорят, что A — подмножество множества B , записывают

А ⊂ В.
Пересечением (произведением) множеств А и В называется множество, состоящее из всех элементов, принадлежащих одновременно и множеству А, и множеству В. Обозначают пересечение множеств A ∩ B. A ∩ B = {х | х ∈ A и х ∈ B}.

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

А или В. Обозначают объединение множеств A ∪ B


Разностью множеств А и В называется множество, состоящее из всех элементов, множества А, не принадлежащих множеству В. Обозначают разность множеств A \ B = {х | х ∈ A и х ∉ B}.

состоящее из всех элементов, принадлежащих только одному множеству А или

В, обозначают A  B


Универсальное множество U (S) — это самое большое множество элементов, рассматриваемых в задаче
Дополнением множества A до универсального называется множество элементов универсального множества, не принадлежащих множеству A - .

= А; А ∩ А = А;
А ∪ U = U; А ∩ U = А;
А ∪ ∅

= А; А ∩ ∅ = ∅;



(законы де-Моргана или формулы двойственности).

множеств четное.
Чаще эту формулу используют при k=2, оформляя ее отдельной

леммой:

Задача 1. Из 100 школьников английский знают 42, немецкий — 30, французский — 28, английский и немецкий — 5, английский и французский — 10, немецкий и французский — 8, английский, немецкий и французский — 3 школьника. Сколько школьников не знают ни одного языка?

английский язык; N — множество школьников, знающих немецкий язык; F —

множество школьников, знающих французский язык.
Тогда n(A) = 42, n(N) = 30, n(F) = 28, n(A ∩ N) = 5,
n(A ∩ F) = 10, n(N ∩ F) = 8, n(A ∩ N ∩ F) = 3.
Найдем с помощью формулы включений и исключений количество школьников, знающих хотя бы один из перечисленных иностранных языков.
n(A ∪ N ∪ F) = n(A) + n(N) + n(F) –
– n(A ∩ N) – n(A ∩ F) – n(N ∩ F) + n(A ∩ N ∩ F) =
= 42 + 30 + 28 – 5 – 10 – 8 + 3 = 80.
Следовательно, не знают ни одного иностранного языка: 100 – 80 = 20 школьников.

знают 3 школьника, то английский и немецкий знают 5 – 3 = 2, английский

и французский — 10 – 3 = 7, немецкий и французский — 8 – 3 = 5 школьников. Только английский знают 42 – (2 + 3 + 7) = 30, только немецкий — 30 – (2 + 3 + 5) = 20, только французский — 28 – (3 + 5 + 7) = 13 школьников. Ни одного языка не знают 100 – (2 + 3 + 5 + 7 + 13 + 20 + 30) = 20 школьников.

решаются задачи выбора элементов из исходного множества и расположения их

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

способами,
элемент - способами, …, -

способами, то или , или , … , или можно выбрать
способами.
Правило произведения
Если элемент можно выбрать способами,
элемент - способами, …, - способами,
то последовательность из k элементов -
картеж, т.е. и , и , … , и можно выбрать
способами.

и 5 видов гелиевых. Сколько существует способов выбрать одну шариковую

ручку и одну гелиевую?
Задача 3. В магазине есть 7 видов шариковых ручек и 5 видов гелиевых. Сколько существует способов выбрать ручку?
Задача 4. Сколькими способами можно назначить двух ребят на дежурство по столовой, если в классе 25 учащихся?

при каждом выборе мы будем извлекать из него новый элемент,

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

n различных объектов, называется размещением из n элементов по m

Размещение

с повторением

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

n различных объектов, называется сочетанием из n по m


Сочетание с

повторением

элементов содержат сами подмножества?
Важен ли порядок элементов?
Повторяются ли элементы в

выборках?

секретаря. Сколькими способами это можно сделать?
Задача 7.В классе учится 18

девочек и 14 мальчиков. Для участия в викторине нужно выбрать 4 мальчиков и 3 девочек. Сколько существует различных составов команд?
Задача 8.Сколько автомашин могут иметь номера Томской области (70 RUS)?
Задача 9.Сколькими способами можно составить набор из 8 пирожных, если в продаже есть пирожные 5 сортов?

различны, из цифр 0; 1; 2; 3; 4;?
Задача 11. Каждая

из 5 подруг собирается вечером пойти либо в кино, либо в театр. Сколькими различными способами эти 5 подруг смогли бы провести вечер?
Задача 12. «Вороне как-то Бог послал кусочек сыра», брынзы, колбасы, сухарика и шоколада. «На ель Ворона взгромоздясь, позавтракать совсем уж было собралась, да призадумалась»:
а) если есть кусочки по очереди. то из скольких вариантов придется выбирать;
б) сколько получится «бутербродов» из двух кусочков;
в) если съесть сразу три кусочка, а остальные спрятать, то из скольких вариантов придется выбирать;
г) сколько получится вариантов, если какой-то кусочек все-таки бросить Лисе, а потом ответить на вопрос пункта а)?