Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально возможное количество различных вариантов развития событий.
Основная формула комбинаторики
Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k .
Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая - из n 2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2 . Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2 . Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2 .
Пример 2.
Сколько
трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если
цифры могут повторяться?
Решение:
n 1 =6
(т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7
(т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5,
6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4,
6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.
В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.
Пример 3.
Сколько всех четырехзначных чисел
можно составить из цифр 1, 5, 6, 7, 8?
Решение.
Для каждого разряда
четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.
Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .
Число размещений из n элементов по m
Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.
Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:
Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.
Пример 5
. Сколько существует двузначных
чисел, в которых цифра десятков и цифра единиц различные
и нечетные?
Решение:
т.к. нечетных цифр
пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на
две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:
Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.
Число сочетаний из n элементов по m
Число сочетаний обозначается C n m и вычисляется по формуле:
Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?
Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:
Перестановки из n элементов
Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.
Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).
Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.
Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?
Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.
Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.
Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).
Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.
И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.
Пример 9.
На родительском собрании
присутствует 20 человек. Сколько существует различных вариантов состава
родительского комитета, если в него должны войти 5 человек?
Решение:
В этом примере нас
не интересует порядок фамилий в списке комитета. Если в результате в его
составе окажутся одни и те же люди, то по смыслу для нас это один и тот же
вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний
из 20 элементов по 5.
Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.
Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5,
6, если цифры могут повторяться?
2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?
4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?
5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо?
6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?
Конспект урока по теме «Элементы комбинаторики»
Цели:
О бучающие:
Формирование основных понятий комбинаторики: размещения из mэлементов по n, сочетания из m элементов по n, перестановки из nэлементов;
Формирование умений и навыков вычисления значений комбинаторных выражений по формулам, решения простейших комбинаторных задач;
Развивающие:
Развитие умения анализировать, обобщать изучаемые факты, выделять и сравнивать существенные признаки, выбирать наиболее эффективные способы решения задач в зависимости от конкретных условий; рефлексия способов и условий действия; контроль и оценка процесса и результатов деятельности;
Воспитательные:
Воспитание интереса к дисциплине, честности, аккуратности, эстетического отношения к оформлению математических решений, воспитание умения слушать и вступать в диалог, участвовать в коллективном обсуждении проблем, интегрироваться в группу сверстников и строить продуктивное взаимодействие, настойчивости в достижении цели и заинтересованности в конечном результате труда; прививать чувство патриотизма.
Обучающийся должен:
знать:
Определения трех важнейших понятий комбинаторики:
Размещения из n элементов по m;
Сочетания из n элементов по m;
Перестановки из n элементов, а также, формулы вычисления их количества.
уметь:
Отличать задачи на «перестановки», «сочетания», «размещения» друг от друга;
Применять основные комбинаторные формулы при решении простейших комбинаторных задач.
ХОД УРОКА
1. Организационный момент.
Ребята, каждая группа в течении года дежурит по техникуму.
Являются ли бригады дежурных в группах постоянными? Скажите, а сколько всего существует способов назначить из n студентов группы mдежурных. В математике есть раздел, который занимается решением подобных задач. Этот раздел называется комбинаторикой.
2. Сообщение темы, целей урока.
Тема сегодняшнего урока «Основные понятия комбинаторики». Давайте вместе попробуем сформулировать цели урока
Ознакомиться с основными понятиями комбинаторики (размещения, сочетания, перестановки)
Научиться решать простейшие комбинаторные задачи
3. Актуализация опорных знаний.
Прежде чем перейти к изучению нового материала, повторим то, что имеет к нему непосредственное отношение. Это уже известное вам понятие «факториал». Итак, кто помнит, что называют «n-факториалом»? Запишите формулу.
Чему, к примеру, равны 2!, 3!, 4!, 5!, 6! ? А кто сможет показать вычисления на доске? А чему равен 1! ? 0! ? Какие значения в данном случае может принимать n?
4. Изложение нового материала.
4.1. Введение общих понятий
Комбинаторикой называют область математики, которая изучает вопросы о числе различных комбинаций (удовлетворяющих тем или иным условиям), которые можно составить из данных элементов.
Комбинаторика – раздел математики, в котором исследуются и решаются задачи выбора элементов из исходного множества и расположения их в некоторой комбинации, составляемой по заданным правилам.
Группы, составленные из каких-либо элементов, называются соединениями .
Различают три вида соединений: размещения , перестановки и сочетания .
Задачи, в которых производится подсчет возможных различных соединений, составленных из конечного числа элементов по некоторому правилу, называются комбинаторными , а раздел математики, занимающийся их решением, - комбинаторикой . Рассмотрим три основных вида соединений и формулы вычисления их количества. Для этого сначала рассмотрим 2 задачи, которые помогут нам сосредоточиться на сути новых понятий.
4.2. Создание проблемной ситуации.
Тексты двух задач на слайде:
Задача 1. В некотором учреждении имеются две различные вакантные должности, на каждую из которых претендуют три сотрудника: A, B, C. Сколькими способами из этих трех кандидатов можно выбрать два лица на эти должности?
Задача 2. Для участия в соревнованиях требуется выбрать двоих спортсменов из трех кандидатов: A, B, C. Сколькими способами можно осуществить этот выбор?
Студентам предлагается два проблемных задания: 1) установить различие между этими двумя внешне схожими задачами и 2) предположить, в какой задаче результат будет больше, и почему. После этого предлагается решить эти задачи методом перебора всевозможных вариантов.
Р ешение задачи 1. AB, BA, BC, CB, AC, CA (всего шесть способов).
Решение задачи 2. AB, BC, AC (всего три способа).
Преподаватель обращает внимание студентов на то, что эти задачи оказались похожими только внешне, из-за того, что в обеих присутствуют два числа: m=3 – общее количество элементов и n=2 – количество выбранных элементов. Но в первой задаче составляются упорядоченные соединения, тогда как во второй задаче порядок следования элементов в соединении не имеет значения.
А если вместо чисел 3 и 2 будут например числа 8 и 3. Подойдет ли этот метод для решения этих задач? Поэтому существуют комбинаторные выражения (формулы) для этих соединений
5.3. Лекция «Основные комбинаторные понятия и формулы».
1) Размещения.
Определение. Размещениями из m элементов по n элементов (n ≤ m) называются такие соединения, каждое из которых содержит n элементов, взятых из m данных разных элементов, и которые отличаются одно от другого либо самими элементами, либо порядком их расположения.
Число размещений из m элементов по n обозначают (от французского «arrangement» - «размещение») и вычисляют по формуле:
Пример 1. Решим задачу 1 с помощью этой формулы:
2) Перестановки.
Определение. Перестановкой из n элементов называют размещение из n элементов по n.
Число перестановок из n элементов обозначается
и вычисляется по формуле:
Задача. Сколькими способами можно расположить в столбик три детали конструктора, различающиеся по цвету?
Ответ:6.
3) Сочетания.
Определение.
Сочетаниями из m элементов по n элементов (n ≤ m) называются такие соединения, каждое из которых содержит n элементов, взятых из m данных элементов, и которые отличаются друг от друга по крайней мере одним элементом.
Число сочетаний из n элементов по m обозначают
(от французского «combination» - «сочетание») и вычисляют по формуле:
Пример 2. Решим задачу 2 с помощью этой формулы:
А теперь решим ту же задачу для случая m=8, n=3:
Снова, как и ожидалось, результат в первой задаче оказался больше, чем во второй.
Мы рассмотрели теоретические основы комбинаторики. Теперь перейдем к этапу закрепления новых знаний при решении задач.
6. Закрепление материала
6.1. Игра «Математическое лото»
Студентам раздаются наборы раздаточных материалов «Математического лото» (по одному на парту). Каждый комплект состоит из 16 математических заданий по основам комбинаторики, картонного листа в виде матрицы размерности 4 на 4 с написанными в ячейках числами-ответами и цветной фотографии, разрезанной на 16 равных прямоугольника. Все части фотографии пронумерованы в соответствии с порядком заданий и перемешаны. Задача студентов – решить 16 заданий, соответствующие частям разрезанной фотографии, и в соответствии с полученными числовыми ответами отыскать их место на картонной матрице, сложив в итоге фото. Задание выполняется как соревнование между малыми группами По 3-4 человека. Определяются три пары, которые не только сложат картинку раньше всех, но и представят в письменном виде все подробные решения.
Перед началом игры преподаватель мотивирует студентов на активное участие в ней, сообщая, что это упражнение позволит наилучшим образом сформировать навыки комбинаторных вычислений, что значительно упростит выполнение домашнего задания. Кроме того, выполняя это упражнение, можно совместить полезное с приятным, так как результат вызовет эстетические чувства.
Задания.
Вычислите.
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
.
Решения:
В завершении игры объявляются и поощряются победители.
6.2. Решение комбинаторных задач.
При решении комбинаторных задач важно научиться различать виды соединений.
Чтобы отличать задачи на подсчёт числа размещений от задач на подсчёт числа сочетаний, определим, важен или нет порядок в следующих выборках:
а) судья хоккейного матча и его помощник;
б) три ноты в аккорде;
в) «Шесть человек останутся убирать класс!»
г) две серии для просмотра из многосерийного фильма.
Ответ: а)да; б)нет; в)нет; г)да.
Задача 1. Сколькими способами могут занять I, II, III места 8 участниц финального забега на дистанции 100 м?
Ответ: 366.
Задача 2. Из 30 обучающихся группы надо выбрать старосту и помощника старосты. Сколькими способами это можно сделать?
Ответ: 870.
Задача 3. Сколькими способами можно составить букет из трёх цветков, выбирая цветы из девяти имеющихся?
Ответ: 84.
Задача 4. В группе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
Ответ:21
6.3 Самостоятельная работа
Проверь себя
1 .Определите вид соединений:
а) Соединения из n элементов, отличающиеся друг от друга только порядком расположения в них элементов, называются __________ перестановки
б) Соединения из m элементов по n , отличающихся друг от друга только составом элементов, называются _______________ сочетания
в) Соединения из m элементов по n , отличающихся друг от друга составом элементом и порядком их расположения, называются _________ размещения
2 .Восстановите соответствие типов соединений и формул для их подсчёта
А.сочетания Ответ:
Подведение итогов самостоятельной работы
7. Подведение итогов урока
Обобщаются новые знания, делаются выводы о достигнутых целях урока. Поощряются активные студенты, выставляются обоснованные преподавателем оценки.
8. Домашнее задание
Подготовка сообщений по темам: «Истории комбинаторики», «Комбинаторика и ее применение в реальной жизни».
Комбинаторика — раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.
Комбинаторика возникла в XVI веке. Первые комбинаторные задачи касались азартных игр. Сегодня комбинаторные методы используются для решения транспортных задач, составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики. Комбинаторика используется для составления и декодирования шифров, для решения других проблем теории информации.
Значительную роль комбинаторные методы играют и в чисто математических вопросах — теории групп и их представлений, изучении основ геометрии, неассоциативных алгебр и др.
Пример комбинаторной задачи. Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?
I способ. Постараемся выписать все такие числа. На первом месте может стоять любая цифра кроме 0. Например, 2. На втором месте любая цифра из 0, 4, 6 и 8. Пусть 0. Тогда в качестве третьей цифры можно выбрать любую из 4, 6, 8. Получаем три числа
Вместо 0 на второе место можно было поставить 4, тогда третье цифрой можно записать или 0, или 6, или 8:
Рассуждая аналогично, получаем ещё две тройки трёхзначных чисел с цифрой 2 на первом месте:
Других, кроме выписанных 12-ти, трёхзначных чисел с цифрой 2 на первом месте, и удовлетворяющих условию, нет.
Если на первом месте записать цифру 4, а остальные выбирать из цифр 0, 2, 6, 8, то получим ещё 12 чисел:
По столько же трёхзначных чисел можно составить с цифрой 6 на первом месте и цифрой 8 на первом месте. Значит, искомое количество:
Вот эти числа:
204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;
402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;
602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;
802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.
Ответ: 48. ◄
Метод рассуждения, которым мы воспользовались при решении предыдущей задачи, называется перебором возможных вариантов .
Правила сложения и умножения
Комбинаторное правило сложения (правило "или") — одно из основных правил комбинаторики, утверждающее, что, если имеется n элементов и элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 A n можно выбрать m n способами, то выбрать или A 1 , или A 2 , или, и так далее, A n можно
m 1 + m 2 + ... + m n
способами.
Например, выбрать подарок ребёнку из 9 машинок, 7 плюшевых медведей и 3 железных дорог можно
способами.
Ответ: 19. ◄
Правило умножения (правило "и") — ещё одно из важных правил комбинаторики. Согласно ему, если элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 способами и так далее, элемент A n можно выбрать m n способами, то набор элементов (A 1 , A 2 , ... , A n ) можно выбрать
m 1 · m 2 · ... · m n
способами.
Например.
1) Выбрать ребёнку в подарок машинку, плюшевого медведя и железную дорогу, выбирая из 9 машинок, 7 плюшевых медведей и 3 железных дорог, можно
9 · 7 · 3 = 189
способами.
Ответ: 189.
2) Воспользуемся правилом умножения для решения задачи, уже рассмотренной выше: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?
II способ.
0 не может стоять первым, значит первую цифру нужно выбрать из 2, 4, 6, 8 — 4 способа;
второй цифрой может быть любая из четырёх оставшихся — 4 способа;
третью цифру можно выбрать среди трёх оставшихся — 3 способа.
Итак, искомое количество трёхзначных чисел:
4 · 4 · 3 = 48.
Ответ: 48. ◄
Перестановки
Множество из n элементов называется упорядоченным , если каждому его элементу поставлено в соответствие натуральное число от 1 до n .
Перестановкой из n элементов называется любое упорядоченное множество из n элементов.
Например, из 4 элементов ♦ ♣ ♠ можно составить следующие 24 перестановки:
| ♦
♣ ♠
| ♦
♣ ♠
| ♣
♦
♠
| ♠
♦
♣
|
| ♦
♠ ♣
| ♦
♠ ♣
| ♣
♦
♠
| ♠
♦
♣
|
| ♦
♣
♠
| ♣
♦
♠
| ♣
♦
♠
| ♠
♦
♣
|
| ♦
♣ ♠
| ♣ ♠ ♦
| ♣
♠ ♦
| ♠
♣
♦
|
| ♦
♠ ♣
| ♠ ♦
♣
| ♣
♠ ♦
| ♠
♣
♦
|
| ♦
♠ ♣
| ♠ ♣ ♦
| ♣
♠ ♦
| ♠
♣
♦
|
◄
Количество перестановок из n элементов принято обозначать P n . С помощью перебора возможных вариантов легко убедиться, в том что
P 1 = 1; P 2 = 2; P 3 = 6; P 4 = 24.
Вообще, число всевозможных перестановок из n элементов равно произведению всех натуральных чисел от 1 до n , то есть n ! (читается "эн факториал"):
P n = 1 · 2 · 3 · ... · (n - 1 ) · n = n !.
Для P n справедлива рекуррентная формула:
P n = n · P n - 1 .
Значение факториала определено не только для натуральных чисел, но и для 0:
0! = 1 .
| Таблица факториалов целых чисел от
0 до
10
|
|||||||||||
| n
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
| n
!
| 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5 040 | 40 320 | 362 880 | 3 628 800 |
Например, сколькими способами 5 мальчиков и 5 девочек могут занять в театре места в одном ряду с 1-го по 10-е место, если никакие два мальчика и никакие две девочки не сидят рядом?
Возможны два случая с одинаковым количеством способов: 1) мальчики — на нечётных местах, девочки на чётных и 2) наоборот.
Рассмотрим первый случай. Мальчики по нечётным местам могут сесть
P 5 = 120
способами. Столько способов и для девочек на чётных местах. Согласно правилу умножения, мальчики — на нечётных местах, девочки на чётных могут расположиться
120 · 120 = 14 400
способами. Значит, всего способов
14 400 + 14 400 = 28 800.
Ответ: 28 800. ◄
Перестановки с повторениями
Перестановкой с повторениями из n элементов, среди которых k разных, при этом насчитывается n 1 неразличимых элементов первого типа, n 2 неразличимых элементов второго типа и так далее, n k неразличимых элементов k -го типа (где n 1 + n 2 + … + n k = n ), называется любое расположение этих элементов по n различным местам.
Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n 1 , n 2 , …, n k раз каждый обозначается и вычисляется следующим образом:$$P_{n_1,n_2, ... , n_k}=\frac{n!}{n_1!n_2! ... n_k!}~.$$
Например, сколько различных десятизначных чисел можно составить из цифр: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?
В данном случае: n = 10, n 1 = 1, n 2 = 2, n 3 = 3, n 4 = 4,$$P_{1, 2, 3, 4}=\frac{10!}{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$
Ответ: 12 600. ◄
Размещения
Размещением из n элементов по m (m ≤ n) m элементов, взятых в определённом порядке из данных n элементов.
Два размещения из n элементов по m считаются различными, если они различаются самими элементами или порядком их расположения.
Например, составим все размещения из четырёх элементов A, B, C, D по два элемента:
A B; A C;A D;
B A; B C; B D;
C A; C В; C D;
D A; D В; D C.
◄
Число всех размещений из n элементов по m обозначают \(A_n^m\) (читается: "А из n по m ") и вычисляется по любой из формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m=\frac{n!}{(n-m)!}$$
Примеры задач.
1) Воспользуемся понятием размещений из n элементов по m для решения задачи, уже дважды рассмотренной ранее: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?
II I способ.
Первую цифру можно выбрать четырьмя способами из набора 2, 4, 6, 8. В каждом из этих случаев количество пар второй и третей цифры равно числу размещений из 4 оставшихся цифр по 2. Значит искомое количество трёхзначных чисел равно:$$4\cdot A_4^2=4\cdot \frac{4!}{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48.
2) Для полёта в космос необходимо укомплектовать экипаж из шести человек. В него должны входить: командир корабля, первый и второй его помощники, два бортинженера, один из которых старший, и один врач. Командный состав выбирается из 20 лётчиков, бортинженеры — из 15 специалистов, а врач — из 5 медиков. Сколькими способами можно укомплектовать экипаж?
Поскольку в выборе командного состава важен порядок, то командира и двух его помощников можно выбрать \(A_{20}^3\) способами. Порядок бортинженеров тоже важен, значит, для их выбора существует \(A_{15}^2\) способов. Врач всего один, для его выбора существует 5 способов. Воспользуемся комбинаторным правилом умножения и найдём количество возможных экипажей корабля:$$A_{20}^3\cdot A_{15}^2\cdot 5=\frac{20!}{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. ◄
Понятно, что, если m = n , то$$A_n^m=A_n^n=P_n=n!.$$
Справедливо также, что, если m = n - 1 , то$$A_n^{n-1}=A_n^n=P_n=n!.$$
Размещения с повторениями
Помимо обычных размещений бывают и размещения с повторениями или выборки с возвращением .
Пусть имеется n различных объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем под номером 1 его название, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был только что взят), запишем его название, пометив номером 2, и снова вернём объект обратно. И так далее, пока не получим m названий.
Размещения с повторениями обозначаются \(\overline{A}_n^m\) и, согласно правилу умножения, вычисляются по формуле$$\overline{A}_n^m=n^m.$$Заметим, что здесь допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после "использования" возвращается обратно и может быть использован повторно.
Например, количество вариантов шестизначного пароля, в котором каждый знак является цифрой от 0 до 9 или буквой латинского алфавита (одна и та же строчная и прописная буква — один символ) и может повторяться, равно:$$\overline{A}_{10+26}^6=\overline{A}_{36}^6=36^6=2~176~782~336.$$Если же строчные и прописные буквы считаются различными символами (как это обычно и бывает), то количество возможных паролей становится ещё более колоссальным:$$\overline{A}_{10+26+26}^6=\overline{A}_{62}^6=62^6=56~800~235~584.$$
◄
Сочетания
Сочетанием из n элементов по m (m ≤ n) называется любое множество, состоящее из m элементов, выбранных из данных n элементов.
В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по m считаются различными, если они различаются хотя бы одним элементом.
Например, составим все сочетания из четырёх элементов A, B, C, D по два элемента:
A B; A C;A D;
B C; B D;
C D .
◄
Число всех сочетаний из n элементов по m обозначают \(C_n^m\) (читается: "C из n по m ") и вычисляется по любой из формул:$$C_n^m=\frac{A_n^m}{P_m}$$$$C_n^m=\frac{n\cdot (n-1)\cdot (n-2)~\cdot~ ...~\cdot~ (n-m+1)}{1\cdot2\cdot3~\cdot~...~\cdot ~m}$$$$C_n^m=\frac{n!}{m!\cdot (n-m)!}.$$
Примеры задач.
1) Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляров и 2 плотников. Сколькими способами можно это сделать?
Так как порядок маляров в каждой выбранной четвёрке и порядок плотников в каждой выбранной паре не имеет значения, то, согласно комбинаторному правилу умножения, искомое количество способов равно:$$C_{12}^4 \cdot C_5^2 =\frac{12!}{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. ◄
2) В классе обучаются 30 учащихся, среди которых 13 мальчиков и 17 девочек. Сколькими способами можно сформировать команду из 7 учащихся этого класса, если в неё должна входить хотя бы одна девочка?
Количество всех возможных команд по 7 человек из класса равно \(C_{30}^7\). Количество команд в которых только мальчики — \(C_{13}^7\). Значит, количество команд, в которых есть хотя бы одна девочка, равно:$$C_{30}^7 - C_{13}^7 =\frac{30!}{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. ◄
Сочетания с повторениями
Помимо обычных сочетаний рассматривают сочетания с повторениями .
Пусть в множестве имеется n объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был взят и записан ранее), запишем его название и снова вернём объект обратно. И так далее, пока не получим m названий.
Принципиальное отличие от размещений с повторениями заключается в том, что в данном случае элементы списка не нумеруются. Например, список "A, С, A, В" и список "А, А, В, С" считаются одинаковыми.
Сочетания с повторениями обозначаются \(\overline{C}_n^m\) и вычисляются по формуле$$\overline{C}_n^m=P_{m,~n-1}=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Действительно, каждый объект после "использования" возвращается обратно и может быть использован снова и снова.
Например, выясним сколькими способами можно купить 7 пирожных в кондитерском отделе, если в продаже 4 их сорта?
Естественно полагать, что количество пирожных каждого вида не меньше 7, и при желании можно купить только пирожные одного из них. Так как порядок в котором кладут купленные пирожные в коробку не важен, то имеем дело с сочетаниями с повторениями. Так как нужно выбрать 7 пирожных из 4 его видов, то искомое количество способов равно:$$\overline{C}_4^7=\frac{(7+4-1)!}{7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$
Ответ: 120. ◄
Бином Ньютона и биномиальные коэффициенты
Равенство$$(x+a)^n=C_n^0x^na^0+C_n^1x^{n-1}a^1+...+C_n^mx^{n-m}a^m+...+C_n^nx^0a^n$$называют биномом Ньютона или формулой Ньютона . Правая часть равенства называется биномиальным разложением в сумму , а коэффициенты \(C_n^0,~C_n^1,~...~,~C_n^n\) — биномиальными коэффициентами .
Свойства биномиальных коэффициентов:
\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^{n-m}\\ ~~~~~~~~3.~~C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\\ ~~~~~~~~4.~~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^4+~... =C_n^1+C_n^3+C_n^5+~...=2^{n-1}\\ ~~~~~~~~6.~~C_n^n+C_{n+1}^n+C_{n+2}^n+~...~+C_{n+m-1}^n=C_{n+m}^{n+1}\\ \)
Свойства биномиального разложения:
1. Число всех членов разложения на единицу больше показателя степени бинома,
то есть равно n + 1 .
2. Сумма показателей степеней x и a каждого члена разложения равна показателю степени бинома,
то есть (n - m) + m = n .
3. Общий член разложения (обозначается T n +1 ) имеет вид$$T_{n+1}=C_n^m x^{n-m}a^m,~~~~m=0,~1,~2,~...~,~n.$$
Треугольник Паскаля
Все возможные значения биномиальных коэффициентов (числа сочетаний) для каждого показателя степени бинома n можно записать в виде бесконечной треугольной таблицы. Такая таблица называется треугольником Паскаля:
| \(C_0^0\) | ||||||||||
| \(C_1^0\) | \(C_1^1\) | |||||||||
| \(C_2^0\) | \(C_2^1\) | \(C_2^2\) | ||||||||
| \(C_3^0\) | \(C_3^1\) | \(C_3^2\) | \(C_3^3\) | |||||||
| \(C_4^0\) | \(C_4^1\) | \(C_4^2\) | \(C_4^3\) | \(C_4^4\) | ||||||
| \(C_5^0\) | \(C_5^1\) | \(C_5^2\) | \(C_5^3\) | \(C_5^4\) | \(C_5^5\) |
|||||
| . . . | . . . | . . . |
В этом треугольнике крайние числа в каждой строке равны 1. Действительно, \(C_n^0=C_n^n=1\). А каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним: \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\).
Таким образом, этот треугольник предлагает ещё один (рекуррентный) способ вычисления чисел \(C_n^m\):
| n
= 0 | 1 | ||||||||||||||||
| n
= 1 | 1 | 1 | |||||||||||||||
| n
= 2 | 1 | 2 | 1 | ||||||||||||||
| n
= 3 | 1 | 3 | 3 | 1 | |||||||||||||
| n
= 4 | 1 | 4 | 6 | 4 | 1 | ||||||||||||
| n
= 5 | 1 | 5 | 10 | 10 | 5 | 1 | |||||||||||
| n
= 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||||||||
| n
= 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||||||||
| n
= 8 | 1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 |
||||||||
| ... | ... | ... | ... | ... |
КОМБИНАТОРИКА
Комбинаторика - раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В - n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.
Пример 1.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?
Решение
Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.
По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.
Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n 1 способами, второе действие n 2 способами, третье - n 3 способами и так до k-го действия, которое можно выполнить n k способами, то все k действий вместе могут быть выполнены:
способами.
Пример 2.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?
Решение
Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.
После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.
По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.
Сочетания без повторений. Сочетания с повторениями
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?
Пример 3.
Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?
Решение
Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?
.
Пример 4.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Решение
Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.
.
Размещения без повторений. Размещения с повторениями
Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Пример 5.
В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
Решение.
В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно вы б рать и разместить по m различным местам m из n предметов, с реди которых есть одинаковые?
Пример 6.
У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера- составить каталог. Сколько различных пятизначных номеров может составить мальчик?
Перестановки без повторений . Перестановки с повторениями
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Пример 7.
Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?
Решение
Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.
Пример 8.
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Решение
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"
План:
1. Элементы комбинаторики.
2. Общие правила комбинаторики.
4. Применение графов (схем) при решении комбинаторных задач.
1. Комбинаторика и ее возникновение.Комбинаторика - это область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству.
Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.
Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицы (числа способов выпадения k очков на r костях). Однако, он не учел, одна и та же сумма очков может выпасть различными способами, поэтому его таблицы содержали большое количество ошибок.
Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.
Дальнейшее развитие комбинаторики связано с именами Я. Бернулли, Г. Лейбница, Л. Эйлера. Однако, и в их работах основную роль играли приложения к различным играм.
Сегодня комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний, для составления планов производства и реализации продукции и т.д.
2. Общие правила комбинаторики.Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m +k способами.
Примеры:
1. Допустим, что в ящике находится n разноцветных шаров. Произвольным образом вынимается 1 шарик. Сколькими способами это можно сделать?
Ответ: n способами.
Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?
Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .
2. Морской семафор.В морском семафоре каждой букве алфавита соответствует определенное положение относительно тела сигнальщика двух флажков. Сколько таких сигналов может быть?
Решение: Общее число складывается из положений, когда оба флажка расположены по разные стороны от тела сигнальщика и положений, когда они расположены по одну сторону от тела сигнальщика. При подсчете числа возможных положений применяется правило суммы.
Правило произведения: Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m *k способами.
Примеры:
1. Сколько двузначных чисел существует?Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1.Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.
2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?
Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .
3. Генеральная совокупность без повторений и выборки без повторений.Генеральная совокупность без повторений - это набор некоторого конечного числа различных элементов a 1 , a 2 , a 3 , ..., a n .
Пример: Набор из n разноцветных лоскутков.
Выборкой объема k (k n ) называется группа из m элементов данной генеральной совокупности.
Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .
Размещениями из n элементов по k называются такие выборки, которые содержат по k элементов, выбранных из числа данных n элементов генеральной совокупности без повторений, и отличаются друг от друга либо составом элементов, либо порядком их расположения.
- число размещений из n по k .
Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.
Преобразовав данную формулу, имеем:
Следует помнить, что 0!=1.
Примеры:
1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?
Решение:
Комбинации
команд-победителей отличаются друг от друга составом и порядком следования
элементов, т.е. являются размещениями из 17 по 3.
2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?
Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.
Перестановками без повторений из n элементов называются размещения без повторений из n элементов по n , т.е. размещения отличаются друг от друга только порядком следования элементов.
Число перестановок.
Примеры:
1. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что они должны состоять из различных цифр?
Решение: Имеем перестановки из 5 элементов. 2. Сколькими способами можно собрать 6 разноцветных лоскутков в пеструю ленту?Решение: Имеем перестановки из 6 элементов.
Сочетаниями без повторений из n элементов по k называются такие выборки, которые содержат по k элементов, выбранных из числа данных n элементов генеральной совокупности без повторений, и отличаются друг от друга только составом элементов.
- число сочетаний из n по k
Элементы каждого из сочетаний можно расставить способами. Тогда Примеры:1. Если в полуфинале первенства по шахматам участвует 20 человек, а в финал выходят лишь трое, то сколькими способам и можно определить эту тройку?
Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.
2. Сколькими способами можно выбрать трех делегатов из десяти человек на конференцию?Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.
Конспект:
4.Применение графов (схем) при решении комбинаторных задач.
В случае, когда число возможных выборов на каждом шагу зависит от того, какие элементы были выбраны ранее, можно изобразить процесс составления комбинаций в виде «дерева». Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на первом шагу. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать выборов на втором шагу, если на первом шагу был выбран данный элемент и т.д.
Задача:
При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a 1 , a 2 , a 3 , a 4 .На место инженера- 3: b 1 , b 2 , b 3 . На место врача- 3: c 1 , c 2 , c 3 . Проведенная проверка показала, что командир a 1 психологически совместим с инженерами b 1 и b 3 и врачами c 1 и c 3 . Командир a 2 - с инженерами b 1 и b 2 . и всеми врачами. Командир a 3 - с инженерами b 1 и b 2 и врачами c 1 и c 3 . Командир a 4 -со всеми инженерами и врачом c 2 . Кроме того, инженер b 1 не совместим с врачом c 3 , b 2 - с врачом c 1 и b 3 - с врачом c 2 . Сколькими способами при этих условиях может быть составлена команда корабля?
Решение:
Составим соответствующее «дерево».
Ответ: 10 комбинаций.
Такое дерево является графом и применяется для решения комбинаторных задач.