"Алгебра (в 3 частях)", Петерсон Л.Г., Агаханов Н.Х., Петрович А.Ю., Подлипский О.К., Рогатова М.В., Трушин Б.В.
Комбинаторика помогает считать количество возможных вариантов, не перебирая их по одному. В параграфе используются правило сложения и правило умножения, а также факториал, перестановки, размещения и сочетания. Главное — определить, выбираются ли все элементы, важен ли порядок и разрешены ли повторения. Эти знания применяются при составлении кодов, выборе команд, расстановке предметов и подсчёте исходов случайных опытов.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Факториал числа n — произведение всех натуральных чисел от 1 до n: n! = 1 · 2 · 3 · … · n. Знак «!» читают «факториал», причём 0! = 1. Факториалы сокращают запись формул и помогают быстро считать число упорядоченных вариантов.
Перестановка — это упорядочивание всех n различных элементов. Если на первое место поставить любой из n элементов, на второе — один из n − 1 оставшихся и так далее, получится n · (n − 1) · … · 1 = n!. Поэтому число перестановок обозначают Pₙ и вычисляют как Pₙ = n!.
Размещение — выбор k элементов из n с учётом порядка. Обозначение Aₙᵏ показывает: из n элементов выбирают k, и разные последовательности считаются разными. Размещения нужны, например, когда выбирают призёров по местам или назначают людей на разные должности.
Сочетание — выбор k элементов из n без учёта порядка. Обозначение Cₙᵏ означает выбор k элементов из n, причём перестановка выбранных элементов не создаёт новую группу. Сочетания применяют при формировании команды или выборе набора предметов.
Правило сложения используют, когда возможны несколько способов выбора, но одновременно происходит только один из них. Например, добраться до места можно автобусом или поездом: маршрут одним видом транспорта исключает маршрут другим. Если у первого способа a вариантов, а у второго b, всего получается a + b вариантов.
Правило умножения подходит для последовательных действий, потому что каждому варианту первого шага можно сопоставить каждый допустимый вариант второго. Если первый шаг имеет a вариантов, а второй — b вариантов для каждого из них, всего будет a · b вариантов. При трёх и более шагах перемножают количество вариантов всех шагов.
Перестановки, размещения и сочетания различаются двумя вопросами: берём ли мы все элементы и имеет ли значение их порядок. Если используются все элементы и их расставляют, это перестановка. Если берут только часть, порядок важен для размещения, а не важен для сочетания.
Чтобы получить число размещений, выбирают элементы по очереди без повторений. На первое место можно поставить n элементов, на второе — n − 1, затем n − 2 и так далее, пока не будут заполнены k мест. По правилу умножения Aₙᵏ = n · (n − 1) · … · (n − k + 1) = n!/(n − k)!.
Сочетание можно получить из размещения, если убрать различия, вызванные только порядком. Каждая группа из k элементов встречается в размещениях k! раз, потому что её элементы можно переставить k! способами. Поэтому Cₙᵏ = Aₙᵏ/k! = n!/(k!(n − k)!).
Пользуйтесь таблицей после того, как определите, что именно выбирается и важен ли порядок. Если берутся все элементы, выбирайте перестановки; если только часть — размещения или сочетания. Формула должна соответствовать смыслу задачи, а не только знакомым числам.
| Вид выбора | Что выбирается | Учитывается ли порядок | Формула | Пример смысла |
|---|---|---|---|---|
| Перестановки | Все n элементов | Да | Pₙ = n! | Сколькими способами расставить n различных книг |
| Размещения | k элементов из n | Да | Aₙᵏ = n!/(n − k)! | Сколькими способами выбрать и расставить призёров |
| Сочетания | k элементов из n | Нет | Cₙᵏ = n!/(k!(n − k)!) | Сколькими способами выбрать команду |
Составим код из цифр 1, 2, 3, 4 без повторений. Порядок цифр важен, потому что коды 123 и 321 различны, но используются только три из четырёх цифр. Значит, это размещения, или последовательный выбор цифр для трёх позиций.
Ответ: 24 различных кода.
Пять различных книг нужно расставить на полке, поэтому используются все элементы и порядок имеет значение. Это перестановка пяти элементов. Число способов равно P₅ = 5!.
Ответ: 120 способов.
Из 10 учеников сначала назначают председателя, заместителя и секретаря, а затем выбирают двух дежурных. Должности различаются, поэтому первые три назначения образуют размещение A₁₀³. Дежурные образуют обычную группу, поэтому после назначений используется сочетание C₇².
Ответ: 15 120 способов.
Сочетания используют вместо размещений, когда порядок имеет значение. Так происходит, если ученик видит слово «выбрать» и не замечает, что выбранные люди получают разные места или должности. Проверьте себя вопросом: изменится ли результат, если поменять выбранные элементы местами?
Размещения используют вместо сочетаний, когда порядок внутри группы не важен. Например, команда из Пети и Маши та же самая, что команда из Маши и Пети. Если перестановка не создаёт новый результат, нужна формула сочетаний.
Иногда в подсчёте разрешают повторно выбрать уже использованный элемент, хотя в условии сказано «без повторений». Тогда число вариантов следующего шага завышается. После каждого выбора пересчитывайте, сколько элементов действительно осталось.
Ошибки возникают и при вычислении факториала: 0! принимают за 0 или неверно сокращают дробь. Помните, что 0! = 1, а n! содержит все множители от 1 до n. Полезно сначала выписать факториалы и сократить одинаковые множители, а затем считать.
До изучения комбинаторики нужны правило умножения, натуральные числа и умение раскрывать факториалы. Без этих навыков трудно получить формулу размещения или проверить вычисления. Повторите умножение и сокращение дробей, если формулы кажутся громоздкими.
Комбинаторика тесно связана с вероятностью. Чтобы найти вероятность события, часто сначала считают общее число исходов и число благоприятных исходов с помощью сочетаний или размещений. Чем точнее определён набор исходов, тем надёжнее результат.
Комбинаторные формулы встречаются в задачах о кодах, маршрутах, командах, расписаниях и выборах. В каждой такой задаче нужно перевести условие на язык последовательных действий или групп. Затем выбирают правило сложения, умножения либо одну из трёх конструкций.
Как понять, применять правило сложения или правило умножения?
Правило сложения используют, когда выбирают один из несовместимых вариантов: например, поездку автобусом или поездом. Правило умножения применяют для последовательных действий, когда результат состоит из нескольких шагов.
Чем размещение отличается от сочетания?
В размещении порядок выбранных элементов имеет значение: выбор ABC отличается от ACB. В сочетании порядок не учитывается, поэтому эти две группы считаются одной.
Почему в формуле сочетаний порядок не учитывается?
Одну и ту же группу из k элементов размещения считают k! раз — по одному разу для каждого порядка. Поэтому число размещений делят на k!, удаляя лишний учёт перестановок внутри группы.
Что делать, если элементы могут повторяться?
Нужно использовать отдельный подсчёт с повторениями: после выбора элемента число доступных вариантов не уменьшается. Например, для кода длины k из n цифр при разрешённых повторениях получается nᵏ вариантов.
Почему 0! принимают равным 1?
Число 0! задают равным 1, чтобы формулы с факториалами работали и при выборе всех элементов. Кроме того, существует ровно один способ ничего не выбрать — оставить пустой набор.
§ 1. Элементы комбинаторики
