§11 Элементы комбинаторики

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

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

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

Размещение — упорядоченный выбор k элементов из n различных; число размещений равно Aₙᵏ = n!/(n−k)!. Выбирают только часть элементов, а перестановка выбранных считается новым вариантом. Эта формула подходит, например, для назначения первого, второго и третьего мест.

Сочетание — выбор k элементов из n различных без учёта их порядка; число сочетаний равно Cₙᵏ = n!/(k!(n−k)!). Важен только состав группы, а не очередность перечисления людей или предметов. Формула нужна, когда из общего набора выбирают команду, комиссию или набор предметов.

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

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

Чтобы посчитать перестановки, можно поставить элементы на места по очереди. На первое место подходит любой из n элементов, на второе — любой из оставшихся n−1, затем n−2 и так далее, пока на последнее место не останется один элемент. По правилу умножения число вариантов равно n(n−1)…2 · 1, то есть n!. Факториал n! обозначает произведение всех натуральных чисел от 1 до n, поэтому он естественно появляется при расстановке всех элементов.

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

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

Выбрать способ подсчёта помогает ответ на два вопроса: берут ли все элементы и важен ли порядок? Если берут все и порядок важен, это перестановка; если берут часть и порядок важен, это размещение. Если берут часть и порядок не важен, это сочетание. Так различают формулы не по словам задачи, а по смыслу результата.

Способы подсчёта выборок из n различных элементов

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

Разбор задач

Трёхзначные коды из цифр 1, 2, 3, 4 без повторений

Условие. Нужно составить трёхзначный код из цифр 1, 2, 3, 4, причём цифры не повторяются. Порядок важен: код 123 отличается от кода 321. Выбираются три цифры из четырёх, поэтому можно применить правило умножения.

1. На первую позицию можно поставить любую из четырёх цифр: 4 варианта. Выбранная цифра уже не может появиться снова.
2. На вторую позицию остаются 3 цифры, а на третью — 2. Для каждой возможности предыдущего шага число продолжений определяется количеством оставшихся цифр.
3. Перемножаем количества вариантов: 4 · 3 · 2 = 24. Так учитывается каждый код ровно один раз.

Ответ: 24 кода. Такой выбор также можно посчитать как размещение трёх цифр из четырёх: A₄³ = 4!/(4−3)! = 24.

Расстановка пяти разных книг

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

1. На первое место можно поставить любую из 5 книг. После этого для второго места остаются 4 книги, для третьего — 3.
2. На четвёртое место можно выбрать одну из 2 оставшихся книг, а на последнее место остаётся одна. По правилу умножения число расстановок равно 5 · 4 · 3 · 2 · 1.
3. Записываем произведение через факториал: P₅ = 5! = 120. Факториал здесь учитывает все возможные очередности пяти книг.

Ответ: 120 способов. Если бы требовалось поставить в ряд только несколько книг из пяти, понадобилось бы считать размещения, а не перестановки.

Команда из восьми учеников с капитаном

Условие. Из 8 учеников нужно выбрать команду из 3 человек и назначить в ней капитана. Просто выбрать команду недостаточно: два варианта с разными капитанами считаются разными результатами. Удобно сначала выбрать состав, а затем определить капитана.

1. Выбираем трёх учеников без учёта порядка: C₈³ = 8!/(3! · 5!) = 56. Перестановка имён не создаёт новую команду.
2. В каждой команде капитаном может стать любой из трёх участников, то есть есть 3 варианта назначения. Выбор капитана выполняется после формирования команды.
3. Перемножаем: 56 · 3 = 168 вариантов команды с капитаном. То же можно увидеть как размещение: выбираются капитан и ещё два участника, причём роль капитана выделена.

Ответ: 168 способов. Умножение на 3 необходимо, потому что один и тот же состав команды может иметь трёх разных капитанов.

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

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

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

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

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

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

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

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

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