Подсчитать общее число возможных комбинаций помогает одно из важнейших правил комбинаторики — правило умножения: если первый элемент в комбинации можно выбрать m способами, после чего второй элемент — n способами, то общее число комбинаций из двух элементов будет m · n .
Пример 1.1. Подсчитаем количество двузначных чисел, которые можно составить из цифр 1, 2, 3. На первое место цифру можно выбрать тремя способами, после чего на второе место — тоже тремя способами. Значит, всего таких чисел по правилу умножения будет 3 · 3 = 9. Можно проверить ответ, выписав друг за другом все эти числа в порядке возрастания:
11, 12, 13;
21, 22, 23;
31, 32, 33.
В приведенном примере выбор второй цифры никак не связан с выбором первой. Но это далеко не всегда так.
Пример 1.2. Подсчитаем количество двузначных чисел, которые можно составить из цифр 1, 2, 3 так, чтобы все цифры были различны. На первое место цифру можно выбрать тремя способами, после чего на второе место — только двумя способами (ту цифру, которая на первом месте, использовать уже нельзя). Значит, всего таких чисел по правилу умножения будет 3 · 2 = 6. Вот эти числа:
12, 13;
21, 23;
31, 32.
Теперь в каждой из трех групп только по два элемента.
В данных примерах две принципиально различные схемы выбора элементов:
а) без возращения (повторений) элементов (это значит, что отбираются либо сразу все элементов, либо последовательно по одному элементу, причем каждый отобранный элемент исключается из исходного множества);
б) с возвращением (повторением) элементов (выбор осуществляется поэлементно с обязательным возвращением отобранного элемента на каждом шаге и тщательном перемешиванием исходного множества перед следующим выбором).
Но бывают задачи, в которых после выбора одного из m объектов в качестве первого элемента комбинации нельзя однозначно сказать, сколькими способами можно выбрать второй элемент — это зависит от того, какой именно объект был выбран первым. Рассмотрим такую ситуацию на примере.
Пример 1.3. Подсчитаем количество двузначных чисел, которые можно составить из цифр 1, 2, 3 так, чтобы первая цифра была меньше второй. На первое место цифру можно выбрать тремя способами, а вот на второе место после этого:
– двумя способами, если первой цифрой была выбрана 1;
– одним способом, если 2;
– нулем способов, если 3.
Приходится применять комбинаторное правило сложения: разбить все комбинации на непересекающиеся классы, подсчитать количество комбинаций в каждом классе (например, по правилу умножения), а затем сложить эти количества.
В предыдущем примере количество комбинаций равно: 2 + 1 = 3.