§ 3. Основные формулы комбинаторики

Определения и обозначения

Правило суммы гласит: число способов выбрать один из взаимоисключающих вариантов равно сумме чисел способов для каждого варианта. Взаимоисключающие варианты не могут произойти одновременно, поэтому один и тот же способ не попадает сразу в две группы. Это правило помогает подсчитать выбор, в котором возможны разные отдельные случаи.

Правило произведения применяют, когда действие состоит из нескольких последовательных этапов: число способов равно произведению числа способов на каждом этапе. Например, можно сначала выбрать напиток, а затем десерт. Правило позволяет посчитать все полные варианты, не перечисляя их по одному.

Перестановка — упорядоченное расположение всех n элементов, а число таких расположений обозначают Pₙ и вычисляют по формуле Pₙ = n!. Знак факториала означает произведение всех натуральных чисел от 1 до n; при этом 0! = 1. Эта формула нужна, когда требуется найти число способов расставить или упорядочить весь набор.

Размещение выбирает k элементов из n и учитывает порядок, а сочетание выбирает те же k элементов без учёта порядка. Например, первые три места в соревновании — размещение, а состав команды из трёх человек — сочетание. Различие между ними определяет, какую формулу нужно применять.

Как это устроено

При последовательном выборе каждому результату первого этапа можно сопоставить все допустимые результаты следующего этапа. Поэтому для каждого первого выбора возникает столько продолжений, сколько вариантов даёт второй этап; группы продолжений не пересекаются. Если этапов несколько, этот рассуждение повторяется, и числа способов перемножаются. Независимость здесь означает, что число продолжений одинаково для каждого предыдущего выбора.

Чтобы получить формулу размещений без повторений, выберем по порядку k элементов из n. На первое место подходит n вариантов, на второе — n − 1, потому что уже использованный элемент повторить нельзя. Дальше число вариантов уменьшается на единицу, и получается произведение n(n − 1)…(n − k + 1). Запись через факториалы даёт Aₙᵏ = n!/(n−k)!, поскольку деление на (n−k)! убирает лишние множители от 1 до n−k.

Перестановка — это размещение, в котором k = n: все элементы набора используются и расставляются по местам. Подставив n вместо k в формулу размещений, получим Aₙⁿ = n!/(n−n)! = n!/0! = n!. Поскольку 0! = 1, формула упрощается до Pₙ = n!. Так видно, почему перестановки не требуют отдельного способа подсчёта.

Чтобы посчитать сочетания, сначала можно выбрать k элементов с учётом порядка, то есть посчитать размещения. Но одна и та же группа из k элементов встречается среди них k! раз: столько существует порядков её элементов. Для сочетания эти порядки считаются одним выбором, поэтому размещения делят на k!. Получаем Cₙᵏ = Aₙᵏ/k! = n!/(k!(n−k)!).

Перед применением формулы нужно выяснить, выбираются все элементы или только часть, различаются ли результаты после перестановки элементов и разрешено ли выбирать один элемент несколько раз. Если используются все элементы и порядок важен, нужны перестановки; если выбирается часть и порядок важен — размещения. Для выбора части без учёта порядка используют сочетания. При повторениях формула меняется: например, для k мест, на каждое из которых можно поставить любой из n элементов, число вариантов равно nᵏ.

Основные формулы комбинаторики

Сначала проверь, требуется ли упорядочить результат: от этого зависит, учитывать ли порядок. Затем установи, выбираются все элементы или только часть, и отдельно проверь возможность повторений. Строка таблицы должна соответствовать всем условиям задачи, а не только одному из них.

Разбор задач

Задача 1. В меню есть 4 напитка и 3 десерта. Сколько способов выбрать один напиток и один десерт? Результат состоит из двух выборов, причём любой напиток можно сочетать с любым десертом. Поэтому нужно считать пары вариантов, а не складывать количество напитков и десертов.

1. Определим этапы: сначала выбирается напиток, для этого есть 4 варианта.
2. Затем выбирается десерт; для каждого напитка доступны все 3 десерта.
3. По правилу произведения число пар равно 4 · 3 = 12.

Ответ: 12 способов. Например, каждому из четырёх напитков соответствуют три различные пары с десертами.

Задача 2. Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5 без повторений? В числе есть три позиции, и перестановка цифр меняет само число, значит, порядок важен. Выбираются только три цифры из пяти, а повторно использовать цифру нельзя. Это размещения без повторений.

1. Для первой позиции есть 5 вариантов: любую цифру из набора.
2. Для второй позиции остаются 4 цифры, для третьей — 3.
3. Умножаем числа вариантов: 5 · 4 · 3 = 60, что совпадает с A₅³ = 5!/(5−3)!.

Ответ: 60 трёхзначных чисел. Ноль в наборе отсутствует, поэтому ограничений на первую цифру дополнительно проверять не нужно.

Задача 3. Из 10 учеников нужно выбрать троих для участия в олимпиаде. Сколькими способами это можно сделать? Команда определяется только тем, кто в неё вошёл: порядок называния участников ничего не меняет. Значит, нужно найти число сочетаний из 10 элементов по 3.

1. Сначала представим выбор упорядоченным: на первое место можно поставить любого из 10 учеников, на второе — одного из 9 оставшихся, на третье — одного из 8.
2. Размещений получается 10 · 9 · 8 = 720. Но каждая команда посчитана 3! = 6 раз — по числу порядков трёх выбранных учеников.
3. Делим 720 на 6: C₁₀³ = 10!/(3! · 7!) = 120.

Ответ: 120 способов. Перестановки участников не создают новых команд, поэтому размещения нужно разделить на число порядков внутри каждой тройки.

Типичные ошибки

Использовать сочетания, когда порядок важен, — значит считать разные порядки одного набора одним способом. Так бывает, если смотреть только на состав набора и не учитывать роли или места. Проверь, изменится ли результат при перестановке элементов: для кода, места в соревновании или последовательности изменится, значит, нужны размещения или перестановки.

Использовать размещения, когда порядок не важен, — значит несколько раз посчитать один и тот же набор. Ошибку допускают, когда ориентируются на выбор нескольких элементов, но не задают вопрос о порядке. Проверь, различаются ли результаты «А, затем Б» и «Б, затем А»; если нет, используй сочетания.

При вычислениях иногда забывают, что 0! = 1, и считают его равным нулю или оставляют выражение без упрощения. Это приводит к неверному результату, например при подстановке k = n в формулу размещений. Подставь значения в формулу и вспомни: произведение пустого набора множителей принимают равным единице.

Формулы для выбора без повторений нельзя применять, если один и тот же элемент разрешено брать несколько раз. Эту ошибку допускают, когда замечают, что порядок важен, но не проверяют условия повторного выбора. Проследи, уменьшается ли число вариантов на следующем месте: если каждый раз доступны все n элементов, повторы разрешены и для k мест используется nᵏ.

Связь с другими темами

Для освоения комбинаторики нужны умножение чисел, понимание последовательного выбора и факториал. Правила суммы и произведения помогают описывать составные события и разбирать алгоритмы, в которых есть разные случаи и этапы. Комбинаторные формулы применяют при вычислении вероятностей: сначала считают подходящие исходы и все возможные исходы. Числа сочетаний также входят в формулу бинома Ньютона, которая позволяет раскрывать степень двучлена.

Что запомнить

• При последовательном выборе вариантов числа способов перемножают.
• Перестановки учитывают порядок и используют все элементы.
• Размещения учитывают порядок и выбирают часть элементов.
• Сочетания выбирают часть элементов без учёта порядка.
• Pₙ = n!, Aₙᵏ = n!/(n−k)!, Cₙᵏ = n!/(k!(n−k)!).
• Перед выбором формулы проверь, важен ли порядок и разрешены ли повторения.