"Алгебра и начала математического анализа (базовый и углубленный уровень) (в 2 частях), изд-во «Мнемозина»", Мордкович А.Г.
Правило умножения помогает подсчитать число способов, если выбор состоит из нескольких последовательных этапов: число вариантов на каждом шаге перемножают. На его основе находят число перестановок — способов расположить все различные элементы, когда порядок важен. Число перестановок n элементов записывают как n!, то есть произведение натуральных чисел от 1 до n; отдельно принимают 0! = 1. Эти понятия нужны для решения комбинаторных задач и дальнейшего изучения вероятности.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Правило умножения: если действие состоит из нескольких последовательных этапов и каждый вариант предыдущего этапа можно сочетать с каждым вариантом следующего, общее число способов равно произведению числа вариантов на каждом этапе. Например, при выборе блюда и напитка сначала выбирают блюдо, затем напиток. Правило позволяет подсчитать все пары, не перечисляя их по одной.
Перестановка — упорядоченное расположение всех элементов данного множества; перестановки различаются порядком элементов. Например, ABC и BAC — разные перестановки одних и тех же букв. Это понятие используют, когда нужно найти число способов расставить или расположить все заданные объекты.
Факториал числа n — произведение всех натуральных чисел от 1 до n; его обозначают n!, причём 0! = 1. Например, 4! = 1 · 2 · 3 · 4 = 24. Факториал кратко записывает произведение, которое возникает при подсчёте перестановок.
Несколько этапов выбора удобно представить деревом: от начальной точки отходят ветви первого шага, от каждой из них — ветви следующего. Каждая конечная ветвь соответствует одному полному варианту действий. Если на первом этапе есть 3 возможности, а из каждой на втором доступны 2, конечных ветвей будет 3 · 2 = 6: на каждую возможность первого шага приходится по две продолженные ветви.
Умножение подходит, когда мы составляем один результат из последовательных частей, а допустимые продолжения учтены для каждого выбора. Если после любого выбора первого этапа остаются те же 4 варианта второго, то при 3 первых вариантах всего будет 3 · 4 сочетания. Когда число вариантов зависит от предыдущего выбора, нельзя без проверки перемножить два числа, описывающих этапы в целом. Нужно посчитать продолжения отдельно для каждого случая, а затем сложить полученные количества.
Чтобы найти число перестановок n различных элементов, мысленно заполняют места по очереди. На первое место можно поставить любой из n элементов, поэтому вариантов n; после этого на второе остаётся n − 1 элемент. Для третьего остаётся n − 2, и так далее, пока последнему месту не будет соответствовать единственный оставшийся элемент. По правилу умножения число расстановок равно произведению n · (n − 1) · … · 1.
Это произведение записывают как n!, потому что факториал объединяет все множители от 1 до n в короткое обозначение. Например, для четырёх разных объектов получается 4 · 3 · 2 · 1 = 4! = 24. При вычислении факториала важно не пропустить ни одного множителя и остановиться на 1. Значение 0! принимают равным 1, чтобы определения и формулы, связанные с факториалами, работали согласованно.
Задачу можно распознать как задачу на перестановки, если требуется разместить все заданные элементы, каждый ровно один раз. При этом изменение порядка должно создавать новый результат: места в очереди, например, имеют значение. Если же часть элементов не используется или порядок не меняет результат, обычная формула n! для такой задачи не подходит. Поэтому прежде чем считать, проверьте, что именно считается отдельным вариантом.
| Понятие | Что подсчитываем | Способ записи или подсчёта | Когда применять |
|---|---|---|---|
| Правило умножения | Число способов выполнить последовательные этапы | Перемножить число вариантов на каждом этапе | Каждый выбор на одном этапе можно продолжить допустимыми выборами следующих этапов |
| Перестановка n элементов | Число упорядочений всех n различных элементов | n · (n − 1) · … · 1 | Нужно расположить все элементы, и порядок важен |
| Факториал | Произведение натуральных чисел от 1 до n | n! = 1 · 2 · … · n; 0! = 1 | Нужно кратко записать произведение убывающих натуральных чисел |
Сначала определите, что именно требуется посчитать: последовательные этапы или упорядочения всех элементов. Затем проверьте, подходят ли условия применения правила умножения и имеет ли значение порядок. Запись с факториалом удобна для перестановок, но сама по себе не заменяет проверку смысла задачи.
В каждой задаче сначала выясним, из каких выборов складывается результат, а затем подберём способ подсчёта. Для ясности запишем решение по шагам и в конце сформулируем ответ. Так легче проверить, не забыли ли мы какой-либо этап или ограничение.
Условие: в столовой предлагают 3 первых блюда и 4 напитка. Сколько вариантов обеда можно составить, выбрав по одному блюду и напитку? Один обед включает оба выбора, значит, нужно учесть все пары. Каждый из напитков можно взять с любым из первых блюд.
Ответ: 12 вариантов обеда.
Условие: сколькими способами можно расставить в ряд 5 разных книг? Нужно расположить все книги, причём перестановка двух книг меняет порядок на полке. Поэтому считаем варианты заполнения пяти мест, не повторяя уже поставленные книги.
Ответ: 120 способов.
Условие: сколькими способами можно расположить в ряд 6 учеников, если два определённых ученика должны стоять рядом? Считать их места независимо нельзя: условие требует, чтобы они образовали соседнюю пару. Поэтому временно объединим этих учеников в один блок, сохранив возможность поменять их местами внутри него.
Ответ: 240 способов.
Ошибка: складывать числа вариантов этапов вместо умножения. Сложение привлекает тем, что тоже объединяет несколько чисел, но оно считает выбор одного из взаимоисключающих вариантов, а не полный результат из нескольких шагов. Проверьте себя: нужно ли выполнить все этапы, чтобы получить один вариант? Если да, обычно требуется умножение.
Ошибка: применять правило умножения, не проверив зависимость этапов. Так бывает, когда число продолжений кажется постоянным, хотя предыдущий выбор меняет доступные возможности. Для проверки перечислите варианты первого шага и посмотрите, сколько продолжений есть у каждого; если числа отличаются, считайте случаи отдельно.
Ошибка: считать перестановки, когда порядок не влияет на результат. Формула n! различает расположения по порядку, поэтому она завышает ответ, если, например, перестановка выбранных объектов не создаёт нового результата. Спросите себя, будут ли два набора с теми же элементами, но в другом порядке считаться разными.
Ошибка: забывать, что перестановка использует все элементы ровно по одному, или считать, что 0! равно нулю. Первая ошибка приводит к неверному числу множителей, вторая — к нарушению принятого определения факториала. Перед вычислением проверьте, что элементы не повторяются и все заняты, а для нуля используйте значение 0! = 1.
Для работы с правилом умножения достаточно уметь умножать натуральные числа и понимать, как составляется упорядоченный набор из последовательных выборов. Представление результата как списка этапов помогает увидеть, что именно нужно перемножать. Эти навыки пригодятся в дальнейших разделах комбинаторики: при изучении размещений и сочетаний важно различать, выбираются ли все элементы и имеет ли значение порядок.
Факториалы и правило умножения также применяются в задачах о вероятности случайных событий. Сначала с их помощью находят число возможных исходов, а затем сравнивают его с числом исходов, подходящих условию. Поэтому точный подсчёт вариантов становится основой для вычисления вероятности.
Чем правило умножения отличается от сложения числа вариантов?
Умножение используют, когда нужно выполнить несколько этапов выбора один за другим. Сложение подходит, когда выбирают один из взаимоисключающих вариантов, то есть выполняют только один из нескольких возможных выборов.
Можно ли применять правило умножения, если число вариантов на следующем шаге зависит от предыдущего выбора?
Можно, если учесть число допустимых продолжений для каждого предыдущего выбора. Если оно различается, разбейте варианты на случаи и подсчитайте их отдельно, а затем сложите результаты.
Что именно считается перестановкой?
Перестановка — это упорядоченное расположение всех элементов данного множества, причём каждый элемент используется ровно один раз. Если порядок элементов изменился, получилась другая перестановка.
Почему число перестановок равно n!, а не n · n?
Для первого места есть n вариантов, но после его заполнения для второго остаётся n − 1 элемент, для третьего — n − 2. Поэтому число вариантов перемножается как n · (n − 1) · … · 1, а не как n · n.
Почему 0! принимают равным 1?
Это соглашение согласуется с общими правилами вычислений с факториалами и позволяет записывать формулы единообразно. Кроме того, пустое множество можно упорядочить ровно одним способом — ничего не размещать.
§ 47. Правило умножения. Комбинаторные задачи. Перестановки и факториалы
