Урок - лекция
Тема: Основные понятия комбинаторики.
Цель: освоение основных понятий и формул комбинаторики для решения задач.
Задание: изучить материал урока, решить задачи самостоятельной работы и выполнить домашнее задание.
Ход урока
Изучение нового материала
Что изучает комбинаторика?
Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально возможное количество различных вариантов развития событий.
Рассмотрим несколько типичных для комбинаторики задач.
Пример 1. В группе 20 учащихся. Сколькими способами могут быть выбраны староста и заместитель старосты?
Решение. Пусть сначала избирается староста. Поскольку каждый член группы может быть выбран старостой, то, очевидно, есть 20 способов его выбора. Тогда заместителем старосты может стать каждый из оставшихся 19 человек. Любой из 20 способов выбора старосты может осуществиться вместе с любыми из 19 способов выбора заместителя старосты. Поэтому всего существует 20 ∙ 19 = 380 способов выбора старосты и его заместителя.
Пример 2. На собрании пожелали выступить четыре человека. Сколькими способами можно расположить их в списке ораторов?
| А |
| В |
| С |
| D |
| С |
| D |
| D |
| С |
| В |
| D |
| D |
| В |
| В |
| С |
| В |
| С |
Каждый способ выбора первого оратора может быть скомбинирован с шесть случаями выбора остальных, то число способов составляет
4 ∙ 6 = 24.
Пример 3. Группу учащихся техникума должна экзаменовать по математике комиссия из двух преподавателей. Сколькими способами может быть составлена такая комиссия, если в техникуме пять преподавателей.
Решение. Обозначим преподавателей буквами A, B, C, D, E, можно выписать все возможные экзаменационные комиссии, а именно: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE. Мы видим, что их число равно десяти.
- Выявим сходства и различия между этими задачами:
1) Сходства. Во всех примерах речь идет о некотором конечном множестве элементов и о количестве его подмножеств, удовлетворяющих некоторым заданным требованиям.
2) Различия. В примерах 1, 3 различия состоят в порядке следования элементов подмножества. Если в примере 3 преподаватели Иванов и Петров это тоже самое, что Петров и Иванов, то в задаче 1 если Ваня – староста, а Коля – его заместитель, то наоборот это уже будут разные множества.
Основные понятия и формулы комбинаторики
Определение. Пусть имеется множество, содержащее n элементов. Размещениями из n элементов по m называются такие соединения, которые отличаются друг от друга либо самими элементами, либо порядком их следования.
(1)
В 1 задаче получим 
Если условиться, что 0! = 1, то получим 
Символ n! (читается: «эн факториал»). Используя знак факториала, можно, например, записать
Пример 4. Группа учащихся изучает 7 учебных дисциплин. Сколькими способами можно составить расписание занятий на понедельник, если в этот день недели должно быть 4 различных урока?
Решение. Число способов равно числу размещений из 7 элементов по 4, т.е. равно 
По формуле получаем 
Размещения с повторениями – каждый элемент, входящий в комбинацию, может быть представлен более чем одним экземпляром.
| Число возможных размещений из n различных элементов по m находятся по формуле: | 
|
Определение 2. Перестановками из n элементов называются такие соединения из n элементов, которые отличаются друг от друга лишь порядком следования элементов.
В задаче 2 требовалось найти число всех перестановок ораторов. Это число оказалось равным 24, следовательно, P4 = 24.
В общем случае число перестановок из n элементов 
и, следовательно, его можно найти по формуле (1): 
. Таким образом
(2)
Пример 5. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что все числа не повторяются.
Решение. Так как число кратно пяти, следовательно, цифра пять должна стоять на последнем месте. Остальные пять цифр могут стоять на оставшихся местах в любом порядке. Следовательно, искомое число шестизначных чисел, кратных пяти, равно числу перестановок из пяти элементов, т.е. 
.
Определение 3. Сочетаниями из n элементов по m называются такие соединения, которые отличаются друг от друга хотя бы одним элементом. (Подмножества, отличающиеся друг от друга только порядком следования элементов, не считаются различными.)
Число сочетаний из n элементов по m обозначается символом 
и вычисляется по формуле:
(3)
Пример 6. Сколько матчей будет сыграно в футбольном чемпионате с участием 16 команд, если каждые две команды встречаются между собой один раз?
Решение. Матчей состоится столько, сколько существует двухэлементных подмножеств у множества, состоящего из 16 элементов, т.е. их число равно 
, т.е. всего будет сыграно 120 матчей.
Свойства сочетаний:
1) 
2) 
Сочетания с повторениями
Сочетание с повторениями – каждый элемент, входящий в соединение, может быть представлен более чем одним элементом:
Общие правила комбинаторики
Правило суммы
Если некоторый объект А можно выбрать m способами, а объект В - k способами (не такими, как А), то объект либо А, либо В можно выбрать m + k способами.
Пример: В ящике имеется n разноцветных шариков. Произвольным образом вынимаем один шарик. Сколькими способами это можно сделать? Конечно, n способами.
Теперь эти n шариков распределены по двум ящикам: В первом m шариков, во втором k. Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами это можно сделать? Из первого ящика шарик можно вытянуть m различными способами, из второго k: различными способами, всего n = m + k способами.
Правило произведения
Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора А) k способами, то пары объектов А и В можно выбрать m·k способами.
Задача: В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать, для выполнения различных заданий, двух студентов одного пола?
По правилу умножения двух девушек можно выбрать 14 ·13 = 182 способами, а двух юношей 6·5 = 30 способами. Следует выбрать двух студентов одного пола: двух студентов или студенток. Согласно правилу сложения таких способов выбора будет 182 + 30 = 212.
Задача: Сколько можно записать двузначных чисел в десятичной системе счисления?
Поскольку число двузначное, то число десятков (m) может принимать одно из девяти значений: 1,2,3,4,5,6,7,8,9. Число единиц (k) может принимать те же значения и может, кроме того быть равным нулю. Отсюда следует, что m = 9, а k= 10. Всего получим двузначных чисел n = m ·k = 9·10 =90.
Следствие
Правило произведения справедливо и для любого конечного числа объектов.
Если некоторый объект Аi (i = 1, 2, …, n) можно выбрать Кi (i = 1, 2, …, n) способами (причем, каждый следующий объект выбирается независимо от выбора предыдущего объекта), то объекты А1, А2, …, Аn можно выбрать k = k1 · k2 ·…· kn способами.
Например, сколькими способами можно составить трехзначное число, делящееся на 5? Число имеет три позиции, каждую из которых мы назовем событием:
- событие А1 –число сотен, их можно выбрать k1 =9 (все цифры, кроме 0) способами;
- событие А2 – число десятков, их можно выбрать k2 = 10 (все цифры, включая 0) способами;
- событие А3 – число единиц, которым удовлетворяет только две цифры: 0 и 5, следовательно, k3 = 2. Таким образом, всего получаем n = k1 · k2 · k3 = 9 · 10 · 2 = 180 чисел.
Самостоятельная работа
1. Сколько различных экзаменационных комиссий по 3 человека можно составить, если на кафедре 20 преподавателей?
2. Имеется 7 путевок в различные дома отдыха и 7 кандидатов. Сколькими способами можно распределить эти путевки?
3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?
4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?
Домашнее задание: §60-63, № 1068, 1079, 1088