Диаграммы Эйлера – Венна

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

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

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

Пересечением множеств и называется множество , состоящие из элементов, которые принадлежат как , так и .

Пример 1. - множество чётных чисел меньших 10, - множество делителей числа 24, тогда множество состоит из чисел принадлежащих и первому множеству и второму.

Пример 2. - множество прямоугольников, - множество ромбов, тогда множество - квадратов.

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

Пример 3.

Пример 4. - множество прямоугольных треугольников, - множество равнобедренных треугольников, тогда множество -……...

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

Пример 5.

Диаграммы Эйлера – Венна

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

В этом случае пишут:

Например, множество квадратов является подмножеством ромбов, а множество ромбов - подмножеством множества параллелепипедов.

Множество натуральных чисел, делящихся на 10, является подмножеством множества чётных натуральных чисел.

Простейшие комбинаторные задачи можно решать методом перебора возможных вариантов.

Пример 1. Четыре студента группы изучают математику- Яна, Настя, Наташа, Андрей. На математическую олимпиаду требуется послать двух студентов. Сколькими способами это можно сделать?

Яна	Настя	Наташа
Настя Наташа Андрей	Наташа Андрей	Андрей

Пример 2. В меню столовой три первых блюда А₁,А₂,А₃, два вторых В₁,В₂, и три сока С₁,С₂,С₃. Сколько вариантов комплексного обеда можно составить из этих блюд?

Решение. Составляем схему возможных вариантов.

А₁		А₂		А₃
В₁	В₂	В₁	В₂	В₁	В₂
С₁,С₂,С₃	С₁,С₂,С₃	С₁,С₂,С₃	С₁,С₂,С₃	С₁,С₂,С₃	С₁,С₂,С₃

Если множество содержит конечное число элементов, и они расположены в установленном порядке, то такое множество называется упорядоченное множество.

Например, упорядоченное множество образуют 33 буквы русского алфавита; множество студентов группы, если за порядок принять список журнала,…

Пример 3. В посёлке имеется 5 светофоров. Каждый может находиться в одном из трёх состояний (гореть красным, зелёным или жёлтым светом). Сколькими способами можно зажечь все светофоры?

Правило сложения.

Если элементов может быть выбран m способами, а элемент может быть выбран n способами, то число способов, которыми можно выбрать один элемент из множества А или множества В, равно сумме m+ n.

Пример 4. В одной группе 25 студентов, в другой – 27 студентов. Сколькими способами можно выбрать одного ученика из двух групп?

Решение. 25+27=52

Правило умножения (основное правило комбинаторики).

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

Пример 5. В одной группе 25 студентов, в другой – 27 студентов. Сколькими способами можно выбрать двух студентов по одному из каждой группы?

Решение. Одного студента первой группы можно выбрать 25 способами, а из второй -27 способами. Двух студентов по одному из каждой группы (по правилу умножения) можно выбрать способами;

Пример 6. На книжной полке стоит 6 исторических романов и 4 приключенческих. Сколькими способами можно взять с полки 2 книги разных жанров?

Решение. По правилу умножения существует способов взять с полки 2 книги разных жанров?

Пример 7. Собрание из 30 человек должно выбрать председателя и секретаря. Сколькими способами это можно сделать?

Решение. Председателем собрания можно выбрать 30 способами, после чего секретаря – 29 способами (из29 оставшихся членов собрания). По правилу умножения существует способов выбора председателя и секретаря.

Пример 8. Сколькими способами можно рассадить 5 гостей за праздничным столом, если приготовлено 8 мест?

Решение. Для первого гостя имеется 8 возможностей выбрать место. После выбора места первым, для второго гостя остаётся 7 возможностей, аналогично для третьего гостя-6 возможностей (из 6 свободных мест), для четвёртого -5 вариантов, для пятого-4. По правилу умножения получаем

Пример 9. Из 10 членов шахматного кружка требуется составить команду из 3 человек для участия в соревнованиях. Сколькими способами это можно сделать?

Решение. Первого члена команды (на первую доску) можно выбрать 10 способами, после чего второго (на вторую доску0 – 9 способами, а третьего (на третью доску)- 8 способами.

Всего получаем вариантов выбора трёх шахматистов из десяти.

Перестановки

Перестановкой называется конечное множество, в котором установлен порядок его элементов.

Например, в множестве из одного элемента существует одна перестановка, в множестве из двух элементов – две.

Например,

а;в;с а;с;в с;а;в с;в;а в;с;а в;а;с

Число перестановок из элементов обозначим через Р_п.

Для произведения первых натуральных чисел принято специальное обозначение (эн - факториал)

Например.

Число перестановок из п элементов равно произведению всех натуральных чисел от1 до п;

Задача 1. Если на завод приняли 6 токарей и их нужно закрепить за имеющимися 6 токарными станками, то возможностей будет

У первого токаря имеется 6 возможностей выбрать станок,

у второго – уже только 5 возможностей,

у третьего – 4 возможности,

у четвёртого -3,

у пятого – две и, наконец,

у шестого – только одна возможность.

Задача 2. Сколькими способами семья из 5 человек может занять пять спальных мест в пятиместном гостиничном номере?

Решение.

Задача 3. Каким числом способов 8 человек могут находится в очереди?

Решение.

Задача 4. Сколько различных четырёхзначных чисел можно составить из цифр 9,7,5,0 если в каждом числе все цифры должны быть разными?

Решение. Если бы среди данных цифр не было нуля, то количество составленных из них четырёхзначных чисел (без повтора цифр в каждом числе) было бы равно количеству перестановок из4 элементов: , но целое число не может начинаться цифрой 0. Среди найденных 24 чисел с цифрой 0 будет начинаться столько чисел, сколько существует перестановок из 3 элементов (цифр 9,7,5): .

Значит, четырёхзначных чисел, составленных из данных цифр, будет

Задача 5. 9 студентов купили 9 билетов в театр. Сколькими способами они могут занять 9 кресел в театральном ряду, если Настя, Яна и Вика обязательно хотят сидеть рядом (в любом порядке).

Решение. Будем считать трёх подруг (Настю, Яну и Вику) как один элемент общей компании, а три занятых ими кресла - как одно место. Тогда можем считать, что размещаем 7 человек в 7 креслах. Это можно сделать столькими способами, каково число перестановок из 7 элементов: .

В то же время три подруги (Настя, Яна и Вика) в своих трёх креслах могут распределиться способами .

Таким образом, каждой перестановке из 7 элементов соответствует любая перестановка из трёх элементов. Всего перестановок по правилу умножения будет

Размещения

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

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

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

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

Например,

Значит,

Формула может быть записана и так: т.е.

Задача 6. Перед выпуском группа студентов колледжа из 30 человек обменялись фотокарточками. Сколько всего было роздано фотокарточек?

Решение. Группа студентов составляет множество элементов, участвовавших в обмене фотокарточками, следовательно, п =30. Каждое размещение есть передача фотокарточки одним студентом другому. Поэтому к=2. Таким образом, всех

фотокарточек было

Задача 7. Студенты группы изучают 11 различных предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 3 различных предмета?

Решение. Различные варианты расписания могут отличаться либо самими предметами, либо их порядком. Количество вариантов равно числу размещений из 11 элементов по 3:

Задача 8. Сколько четырёхзначных чисел можно составить из нечётных цифр, если все цифры в числе различны?

Решение. Нечётные цифры: 1,3,5,7,9. Различные числа могут отличаться или самими цифрами, или порядком четырёх цифр, из которых они составлены. Количество чисел равно числу размещений из5 элементов по 4.

Задача 9. Сколькими способами 10 человек могут занять четыре кресла, имеющиеся в комнате?

Решение.

Задача 9. Студенту необходимо сдать 4 зачёта за10 дней.

1. Сколькими способами это можно сделать?

2. Сколькими способами это можно сделать, если известно, что последний зачёт будет сдаваться на 10 день?

Решение.

1. Искомое число способов равно числу упорядоченных подмножеств из 4 элементов (дней сдачи зачётов), которые можно получить из данных 10 элементов.

2. Так как известно, что последний зачёт должен быть в последний день, число вариантов этого зачёта равно 4, а-число размещений из 9 элементов (дней для других зачётов) по 3 элемента (3 других зачёта) равно , то по правилу умножения общее число вариантов сдачи зачётов равно

Сочетания

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

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

Например, одно и то же сочетание.

Число сочетаний из элементов по обозначается .

Число сочетаний, составленных из элементов по , вычисляется по формуле , т.е.

Задача 10. В вазе стоят 10 красных и 5 белых роз.

А) Сколькими способами можно составить букет из 3 роз?

Б) Сколькими способами можно составить букет из 1 красной и 2 белых роз?

Решение.

А) Так как порядок выбора роз не имеет значения, то выбрать 3 розы из15 можно способами:

Б). Одну красную розу можно выбрать 10 способами, а 2 белые из имеющихся 5 можно выбрать способами. Поэтому букет из 1 красной и 2 белых роз можно составить по правилу умножения, способами

Задача 11. Из 9мальчиков и 11 девочек спортивного класса для участия в соревнованиях надо составить команду, в которую должны входить 3 мальчика и 3 девочки. Сколькитми способами это можно сделать?

Задача 12. На витрине магазина выставлено 6 сортов сыра и 5 видов йогурта. Покупателю требуется 2 куска сыра разных сортов и 3 йогурта разного вида. Сколькими способами покупатель может составить свою покупку?

Решение. Выбрать 2 сорта сыра из 6 имеющихся можно способами. Выбрать3 йогурта из 5 предлагаемых видов можно способами. По правилу умножения имеем вариантов составления покупки.

Задача 13. Сколько существует четырёхзначных чисел, у которых каждая следующая цифра меньше предыдущей?

Решение. Из 10 цифр (0;1;2;3;4;5;6;7;8;9) можно выбрать подмножеств, состоящих из 4 цифр. Расположив в каждой выбранной группе цифры в порядке убывания, получаем искомые четырёхзначные числа. При этом цифра 0 всегда будет стоять лишь последней, так как является наименьшей среди цифр.