КОМБИНАТОРНОЕ ПРАВИЛО УМНОЖЕНИЯ

КОМБИНАТОРНОЕ ПРАВИЛО УМНОЖЕНИЯ

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

Например, из Минска до Гомеля можно добраться самолетом, поездом, автобусом или теплоходом. Сколько существует способов попасть из Минска в Лоев?

Решение. Для любого из четырех возможных способов перемещения из Минска в Гомель можно выбрать любой из двух способов продолжения пути. Поэтому число вариантов попадания из Гомеля в Лоев – 4·2=8.

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

Если объект А может быть выбран m различными способами, причем после каждого такого выбора объект B можно выбрать n различными способами, то выбор «сначала А, а потом B» можно осуществить m·n способами.

Более общим способом, если A₁ может быть выбран m₁ различными способами, причем после каждого выбора объекта А₁ объект А₂ может быть выбран m_k различными способами, то выбор «сначала A₁, потом A₂, А₃, …A_k-1, A_k» можно осуществить m₁·m₂…m_k.

Алгоритм решение задачи на языке Паскаль:

uses crt;

var a: ARRAY [1..100] of integer;

    i, n, k: integer;

 begin

 readln(n);

 for i:=1 to n do readln(a[i]);

 for i:=1 to n do k:=k+a[i];

 writeln(k);

 end.