§ 27. Комбинаторика

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

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

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

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

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

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

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

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

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

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

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

Как выбрать правило подсчёта вариантов

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

Слова «или» и «и» помогают, но не дают готового ответа сами по себе. «И» может обозначать последовательные части результата, а «или» — случаи, которые всё равно пересекаются. Решение выбирают по смыслу условия и по тому, как устроены допустимые варианты.

Разбор задач

Выбор напитка

В меню есть 3 вида сока и 2 вида чая. Нужно выбрать ровно один напиток, поэтому одновременно сок и чай не выбираются. Случаи «сок» и «чай» непересекаются.

1. Разделим все результаты на два случая: выбран сок или выбран чай.
2. В первом случае есть 3 способа, во втором — 2 способа.
3. Применим правило сложения: 3 + 2 = 5.

Ответ: один напиток можно выбрать 5 способами. Умножение здесь не подходит, потому что второй напиток после первого выбирать не нужно.

Комплект одежды

Ученик выбирает одну из 4 футболок и одни из 3 пар брюк. Готовый результат состоит из двух частей, и сначала можно выбрать футболку, а затем брюки. Каждый вариант футболки сочетается с каждой парой брюк.

1. На первом шаге есть 4 выбора футболки.
2. Для каждого из них остаётся 3 выбора брюк.
3. По правилу умножения получаем 4 · 3 = 12 комплектов.

Ответ: можно составить 12 разных комплектов. Здесь не складывают 4 и 3, потому что в комплект должны войти оба предмета одежды.

Поездка из A в C

Из A в B ведут 3 дороги, из B в C — 2 дороги, а из A в C есть отдельная дорога. Добраться можно либо через B, либо сразу по отдельной дороге. Эти два маршрута не пересекаются как способы поездки.

1. Для поездки через B сначала выбираем одну из 3 дорог A—B, затем одну из 2 дорог B—C.
2. Число маршрутов через B равно 3 · 2 = 6.
3. К ним добавляем 1 отдельный маршрут: 6 + 1 = 7.

Ответ: из A в C можно добраться 7 способами. Сначала использовано умножение для последовательных участков пути, затем сложение для двух разных способов поездки.

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

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

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

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

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

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

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

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

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

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