§ 26. Комбинаторные задачи

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

Факториал натурального числа n — произведение всех натуральных чисел от 1 до n: n! = 1 · 2 · 3 · … · n. Знак «!» читают «факториал», например 4! = 24. По определению 0! = 1; это удобно для формул и не означает умножение пустого набора чисел.

Правило умножения говорит: если первый выбор можно сделать m способами, а следующий — n способами, то два последовательных выбора выполняются m · n способами. Например, к каждому варианту первого шага можно присоединить каждый вариант второго. Правило нужно, чтобы не перечислять все пары вручную.

Размещение из n элементов по k — это упорядоченный выбор k различных элементов из n. Упорядоченный означает, что перестановка выбранных элементов создаёт новый вариант: 1, 2 и 2, 1 различаются. Такое понятие используют, когда выбранные объекты получают места, роли или номера.

Сочетание из n элементов по k — выбор k различных элементов из n, при котором порядок не учитывается. Наборы {А, Б} и {Б, А} здесь одинаковы. Сочетания подходят для выбора команды или группы, если важен только состав.

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

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

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

Перестановка связана с размещением тем, что в обоих случаях порядок имеет значение. Размещение выбирает k элементов из n, а перестановка выбирает все элементы, то есть k = n. Поэтому число перестановок равно n!: первый элемент можно поставить n способами, второй — n − 1 способом и так далее.

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

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

Способы подсчёта вариантов

Сначала найдите в условии общее число доступных элементов n и число выбираемых элементов k. Затем проверьте, меняется ли результат при перестановке выбранных объектов. Таблица помогает быстро сопоставить эти признаки с нужной формулой.

Разбор задач

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

1. Напиток выбирают 4 способами.
2. Для любого выбранного напитка пирожное выбирают 3 способами.
3. Перемножаем количества: 4 · 3 = 12.

Ответ: 12 способов.

Задача 2. Сколькими способами можно расставить в ряд 5 разных книг? Все книги используются, а изменение порядка создаёт новую расстановку. Это перестановка пяти элементов.

1. На первое место можно поставить любую из 5 книг.
2. На второе место остаются 4 книги, затем 3, 2 и 1.
3. Получаем 5! = 5 · 4 · 3 · 2 · 1 = 120.

Ответ: 120 способов.

Задача 3. Из 8 учеников нужно выбрать старосту и его заместителя. Выбираются только два человека, но роли различаются, поэтому один и тот же состав в разных ролях даёт разные результаты. Подходит размещение из 8 элементов по 2.

1. Старосту можно выбрать 8 способами.
2. После этого заместителя выбирают из 7 оставшихся учеников.
3. Число вариантов равно A₈² = 8 · 7 = 56.

Ответ: 56 способов.

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

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

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

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

Ошибка: неверно подставлять k в формулу. k — число выбираемых элементов, а n — общее число доступных элементов, поэтому их нельзя менять местами. Перед вычислением выпишите отдельно, сколько объектов дано и сколько требуется выбрать.

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

Для комбинаторных задач нужны умения умножать и делить натуральные числа, читать условие и выделять последовательные этапы выбора. Эти навыки позволяют понять структуру задачи до подстановки в формулу.

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

Систематический подсчёт нужен при выборе объектов, расстановке предметов и составлении кодов. Одна и та же идея помогает заменить длинный перебор короткой формулой или правилом умножения.

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

• Правило умножения применяют к последовательным шагам выбора.
• Перестановка использует все элементы и учитывает их порядок.
• Число перестановок n элементов равно n!.
• Размещение выбирает часть элементов и учитывает порядок.
• Сочетание выбирает часть элементов, не учитывая порядок.
• Сначала выясни, важен ли порядок и выбираются ли все элементы.