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

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

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

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

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

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

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

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

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

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

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

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

Способы решения комбинаторных задач

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

Разбор задач

Задача 1. У Маши есть две юбки и три блузки. Сколько разных комплектов из юбки и блузки она может составить? Полный комплект состоит из двух предметов, поэтому учитываем каждую пару «юбка — блузка». Можно посчитать такие пары по очереди для каждой юбки.

1. Для первой юбки подходят все три блузки, значит, с ней получится 3 комплекта.
2. Для второй юбки также подходят все три блузки, поэтому с ней получится ещё 3 комплекта.
3. Складываем группы: 3 + 3 = 6. То же вычисление по правилу умножения: 2 · 3 = 6, потому что каждой юбке соответствуют три блузки.

Ответ: 6 комплектов.

Задача 2. В кафе предлагают три первых блюда и два напитка. Сколько разных обедов можно составить, выбрав одно блюдо и один напиток? Один обед — это пара из блюда и напитка. Проверим число вариантов с помощью дерева: от каждого блюда должны отходить ветви к обоим напиткам.

1. Первое блюдо можно сочетать с двумя напитками, получаются 2 обеда.
2. Для второго блюда снова есть 2 напитка, значит, добавляются ещё 2 обеда.
3. Для третьего блюда также возможны 2 сочетания. Всего 2 + 2 + 2 = 6, или 3 · 2 = 6 по правилу умножения.

Ответ: 6 разных обедов.

Задача 3. Для кода выбирают одну букву из двух предложенных и затем одну цифру от 0 до 4. Сколько кодов можно составить, если повторения между этими выборами невозможны? Сначала выясним, влияет ли запрет повторения на число вариантов. В одном выборе используется буква, а в другом — цифра, поэтому выбранные символы принадлежат разным группам и совпасть не могут.

1. Первую букву можно выбрать двумя способами.
2. Цифры от 0 до 4 — это 0, 1, 2, 3 и 4, значит, для каждого выбора буквы есть 5 цифр.
3. Запрет повторения не сокращает число продолжений: буква и цифра не могут повторить друг друга. По правилу умножения получаем 2 · 5 = 10.

Ответ: 10 кодов.

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

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

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

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

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

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

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

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

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

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