Принцип умножения

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

Принцип умножения. Если элемент А можно выбрать из некоторого множества m способами и если после каждого такого выбора элемент B можно выбрать n способами, то пара элементов (А,В) в указанном порядке может быть выбрана (mn) способами.

Пример 1.1. Из пункта А в пункт В ведут 3 дороги, а из пункта В в пункт С – 4 дороги. Сколькими способами можно совершить поездку из А в С через В?

Решение. В пункте А есть 3 способа выбора дороги в пункт В, а в пункте В есть 4 способа попасть в пункт С. Согласно принципу умножения, существует 34=12 способов попасть из пункта А в пункт С.

Принцип умножения легко обобщается на случай выбора трех и более элементов.

Пример 1.2. Сколько четырехзначных чисел можно составить из цифр 1, 2, 3, 4 и 5, если: а) цифры не повторяются; б) повторение допустимо; в) числа должны быть нечетные и без повторения.

Решение. а) Первую цифру можно выбирать 5-ю способами. Так как в числе цифры не повторяются, то вторую цифру уже можно выбрать из четырех оставшихся 4-мя способами. Далее получаем, что третью цифру можно выбрать 3-мя способами и четвертую – двумя. Таким образом, число возможных четырехзначных чисел равно N=5432=120.

б) Так как повторения допустимы, то каждую цифру можно выбирать каждый раз из 5 имеющихся цифр, т.е. пятью способами. Тогда число возможных чисел равно N=5555=5⁴=625.

в) У нечетного числа последняя цифра нечетная, т.е. в данном случае может быть либо 1, либо 3, либо 5. Поэтому на это место можно поставить любую из этих трех чисел. После этого на оставшиеся места можно поставить: четыре цифры, три цифры и две цифры, ибо никакие из пяти цифр нельзя использовать более одного раза. Таким образом, N=3432=72.

Упражнения

1.1. Имеется 5 видов конвертов без марок и 4 вида марки. Сколькими способами можно выбрать конверт и марку для посылки письма?

Ответ: .

1.2. На вершину горы ведут пять дорог. Сколькими способами турист может подняться на гору и потом спуститься с неё? Решите ту же задачу при дополнительном условии, что подъём и спуск происходят по разным дорогам.

Ответ: ;.

1.3. При составлении одного варианта письменной контрольной работы по математике преподаватель располагает 4 задачами по геометрии, 8 – по алгебре и 3 – по тригонометрии. Сколькими способами можно составить этот вариант, если в него должно войти по одной задаче из перечисленных разделов?

Ответ: .

1.4. Из двух полуфинальных групп, каждая их которых содержит по 6 команд, в финал выходит по одной команде. Сколько может быть различных вариантов участников финального матча?

Ответ: .

1.5. В книге из 20 страниц на каких-либо трех страницах надо поместить по одной разной иллюстрации. Сколькими способами это можно сделать?

Ответ: .

1.6. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Ответ: .

1.7. Сколькими способами Чип и Дейл могут поделить между собой 5 разных орешков?

Ответ: .

1.8. На складе имеются 6 ящиков с различными фруктами и 3 ящика с различными овощами. Сколькими способами можно каждой из двух овощных палаток выдать по одному ящику с фруктами и овощами?

Ответ: .