АЛГЕБРА И НАЧАЛА АНАЛИЗА

Раздел IV. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ, НАЧАЛА ТЕОРИИ ВЕРОЯТНОСТЕЙ И ЭЛЕМЕНТЫ СТАТИСТИКИ

§1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ.

1. Правило суммы и правило произведения

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

Сначала рассмотрим правило суммы:

если некоторый элемент А можно выбрать m способами, а элемент В - r способами (причем любой выбор элемента А отличается от выбора элемента В), то выбрать А или В можно m + r способами.

Пример 1. В ящике находится 7 белых и 4 черных шарика. Тогда выбрать один шарик: белую или черную можно 7 + 4 = 11 способами.

Понятно, что правило суммы можно распространить на три и более элементов.

Сформулируем правило произведения:

если некоторый элемент А можно выбрать m способами, а после каждого такого выбора другой элемент В можно выбрать (независимо от выбора элемента А) - r способами, то пару объектов А и В можно выбрать mr способами.

Пример 2. В школьной столовой выбор из 3 первых и 5 вторых блюд. Тогда обед из первого и второго блюда можно выбрать 3 ∙ 5 = 15 способами.

Правило распространяется на произведения три и более элементов.

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

Решения.

1) Имеем 5 способов для сотен числа (рис. 129). После того, как место сотен заполнено (например, цифрой 1), для десятков остается 4 способа. Рассуждая далее, для единиц - 3 способа. Итак, имеем: «5 способов, и после каждого из них - 4, и после каждого из них - 3 способа». По правилу произведения имеем 5 ∙ 4 ∙ 3 = 60 чисел.

2) Если цифры в числе повторяются, то на каждое из трех мест есть по 5 вариантов заполнения (рис. 130), и тогда всех чисел будет 5 ∙ 5 ∙ 5 = 125.

Пример 4. Сколько четных чотирицифрових чисел можно составить из цифр 6; 7; 8; 9, если в числе цифры не повторяются?

Решения. Четное четырехзначное число можно получить, если последней цифрой будет 6 или 8. Чисел, у которых последняя цифра 6 будет С ∙ 2 ∙ 1 = 6 (рис. 131), чисел, у которых последняя цифра 8 будет также 6. По правилу суммы всего четных чисел, удовлетворяющих условию, будет 6 + 6 = 12.