Правило умножения и сложения

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

Задача 1. Необходимо составить варианты контрольной работы, каждый из которых должен содержать три задачи. Одна задача выбирается из любого параграфа I главы сборника задач, вторая - из любого параграфа II главы, а последняя - из любого параграфа III главы. При этом следует учесть, что I и III глава содержат два параграфа, а II глава - три параграфа. Сколько видов контрольной работы можно составить исходя из этих условий, если вид работы определяется только номерами параграфов, из которых выбраны задачи?

Задачу решим двумя способами.

Способ 1. Пусть каждой задаче соответствует двузначное число, где первая цифра соответствует номеру выбранной главы, а вторая - номеру параграфа. Чтобы не допустить ошибки при подсчете, воспользуемся специальным графом, который иногда называют деревом (рис. 1).

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

Рис. 1

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

В первую клетку можно поместить либо 11, либо 12. Поэтому первую клетку можно заполнить двумя способами:

На «дереве» это обстоятельство иллюстрируется двумя ветвями, исходящими из точки О и ведущим к столбцу «Первая задача». Для каждого из двух способов заполнения первой клетки имеется три варианта заполнения второй клетки, так как вторую задачу можно выбрать тремя способами, поскольку глава II содержит три параграфа:

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

Тогда общее число способов заполнения трех клеток равно . Именно столько ветвей заканчивается в столбце «Третья задача». Таким образом, исходя из условий задачи, можно составить 12 различных видов контрольной работы.

Задача 2. В группе 30 человек. Необходимо выбрать старосту и заместителя. Сколькими способами можно это сделать?

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

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

Привило умножения. Пусть требуется выполнить одно за другим какие-то k действий. Если первое действие можно выполнить n1, способами, второе действие – n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены nl n2 n3...nk способами.

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

Задача 3. Четыре студента и четыре студентки садятся на 8 расположенных подряд стульев, причем студенты садятся на места с четными номерами, а студентки — не места с нечетными номерами. Сколькими способами это можно сделать?

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

Задача 4. Имеется 20 изделий 1-го сорта и 30 изделий 2-го сорта. Необходимо выбрать два изделия одного сорта. Сколько способов выбора двух изделий возможно в данной ситуации, если учитывается порядок выбора изделий?

Условимся первым действием считать выбор изделий 1-го сорта вторым - выбор изделий 2-го сорта. По правилу умножения два изделия 1-го сорта можно выбрать способами. Аналогично, два изделия 2-го сорта можно выбрать способами. Согласно условию задачи следует выбрать два изделия одного сорта, не важно какого. Это могут быть либо изделия 1-го сорта, либо изделия 2-го сорта. Таким образом, должно быть выполнено либо первое действие, либо второе, но не первое действие, а затем второе. Эти действия не могут быть выполнены одновременно, поскольку они взаимно исключают друг друга. Поэтому общее число способов выбора изделий одного сорта равно 380 + 870=1250.

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

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

Это правило легко распространить на любое конечное число действий.