§ 17. Основные правила комбинаторики

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

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

1. Определяем правило: выбирают один вариант из групп соков и компотов, значит, используем правило суммы.
2. Проверяем, что один напиток не считается одновременно соком и компотом. Группы не пересекаются.
3. Складываем числа вариантов: 4 + 3 = 7.

Ответ: 7 способами.

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

1. На первом этапе выбирают футболку — 5 вариантов.
2. Для каждой футболки на втором этапе выбирают брюки — 3 варианта.
3. Применяем правило произведения: 5 · 3 = 15.

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

Задача 3. Из города A в город B ведут 3 дороги, а из B в C — 4 дороги. Сколькими способами можно проехать из A в C через B, а затем вернуться по маршруту, отличному от выбранного для поездки туда? Под маршрутом здесь понимаем выбор дороги на каждом участке. Сначала нужно посчитать варианты пути туда, а затем — допустимые варианты обратного пути.

1. Для поездки из A в C выбирают дорогу A–B и дорогу B–C: 3 · 4 = 12 маршрутов.
2. Обратно есть 4 варианта дороги C–B и 3 варианта дороги B–A, всего 4 · 3 = 12 маршрутов.
3. Для каждого пути туда исключаем один обратный путь, который использует те же дороги в обратном направлении. Остаётся 12 − 1 = 11 вариантов возвращения.
4. Для каждого из 12 путей туда подходят 11 обратных маршрутов: 12 · 11 = 132.

Ответ: 132 способами.

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

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

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

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

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

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

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

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

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

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