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

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

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

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

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

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

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

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

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

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

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

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

Сначала определите устройство задачи: отдельные случаи соединены словом «или» или действия выполняются одно за другим. Если вариантов мало, надёжнее начать с перечисления. Дерево помогает проверить рассуждение, а правила позволяют быстро получить результат, когда структура задачи ясна.

Разбор задач

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

Условие: в меню есть 3 напитка. Сколькими способами можно выбрать один напиток? Нужно рассмотреть только один выбор, поэтому каждый напиток является отдельным допустимым результатом.

1. Обозначим варианты: первый напиток, второй напиток, третий напиток.
2. Перечислим их по одному и убедимся, что каждый вариант записан ровно один раз.
3. Получаем 3 результата, поэтому ответ равен 3.

Ответ: 3 способа.

Выбор вида транспорта

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

1. Разделим все варианты на две группы: поездка автобусом и поездка поездом.
2. Эти группы взаимоисключающие: один человек не выбирает одновременно оба вида транспорта.
3. Применим правило сложения: 2 + 3 = 5.

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

Составление номера

Условие: номер состоит из одной буквы, выбранной из 3, и одной цифры, выбранной из 4. Букву и цифру выбирают последовательно, поэтому один номер включает оба выбора.

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

Ответ: 12 разных номеров.

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

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

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

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

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

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

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

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

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

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