Правила комбинаторики

Подсчитать общее число возможных комбинаций помогает одно из важнейших правил комбинаторики — правило умножения: если первый элемент в комбинации можно выбрать 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.