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

Правило произведения

Сформулируем правило произведения, которое также называют принципом умножения.

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

Пример 9.1.1. Используя правило произведения, решим задачу из введения к главе. Определим, сколько существует двузначных чисел, цифры которых различны и нечетны.

Чтобы составить двузначное число, можно последовательно выполнить следующие два действия: выбрать цифру десятков, а затем выбрать цифру единиц. Первое действие можно выполнить пятью способами, так как имеется 5 нечетных цифр {1,3,5,7,9}, а второе действие - четырьмя способами, так как можно взять любую нечетную цифру, которая не равна выбранной цифре при первом действии. Имеем 5-4=20 способов выполнить указанные действия, значит, существует 20 требуемых в задаче чисел.

Заметим, что можно изменить порядок действий: вначале выбрать цифру единиц, затем цифру десятков. Это никак не повлияет на ответ. •

Правило произведения можно сформулировать на языке множеств. Пусть множество Л содержит п элементов, а множество В имеет к элементов. Тогда можно составить пк упорядоченных пар (а.Ь), в которых первый элемент выбирается из множества А, а второй элемент - из множества В.

Отсюда вытекает, что число элементов прямого произведения множеств А и В вычисляется по формуле А*В = |4|-|/?|.

Суть правила произведения нс изменится, если требуется выполнить более двух действий.

Пример 9.1.2. Даны множество букв А = {яДс}, множество цифр В = {2,3,4,5} и множество знаков С ={+,-}. Сколькими способами можно составить комбинацию вида: буква, цифра, знак?

Так как букву можно выбрать тремя способами, цифру - четырьмя способами, а знак - двумя способами, то последовательно выбрать букву, цифру и знак можно 34-2=24 способами. Выпишите в явном виде все такие комбинации. •

Пример 9.1.3. Сколько существует двузначных чисел, первая цифра (цифра десятков) которых меньше 4, а вторая цифра нечетна и отлична от первой?

Первую цифру можно выбрать тремя способами (из цифр 1, 2, 3). После этою вторую цифру можно выбрать пятью способами (из цифр 1, 3, 5, 7, 9), но лишь при условии, что при первом действии была выбрана цифра 2. Если же изначально была выбрана, например, цифра 1, то вторую цифру можно выбрать только четырьмя способами (цифру 1 уже использовать нельзя). Итак, мы не можем однозначно сказать, сколькими способами можно выполнить второе действие. Поэтому правило произведения здесь непосредственно применить нельзя. •

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >