Примеры комбинаторных задач

В науке и на практике часто встречаются задачи, при решении которых нужно составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи получили название комбинаторных задач, а раздел, в котором они рассматриваются, - комбинаторикой. Методы комбинаторики применяются в физике, химии, биологии, экономике и других областях знаний.

Рассмотрим некоторые комбинаторные задачи.

Пример первый. Из группы спортсменов по гребле, в которую входят четыре человека – Андреев, Гришин, Степанов и Николаев, тренер выделяет двоих для участия в соревнованиях пар. Сколько существует вариантов выбора такой пары?

Решение. Составим сначала пары, в которые входит Андреев. Для краткости будем писать первые буквы фамилий. Получим три пары: Андреев-Гришин, Андреев-Степанов, Андреев-Николаев.

Выпишем теперь пары, в которые входит Гришин, но не входит Андреев. Таких пар две: Гришин-Степанов, Гришин-Николаев.

Далее составим пары, в которые входит Степанов, но не входят Андреев и Гришин. Такая пара одна: Степанов-Николаев.

Других вариантов составления пар нет, потому что все пары, в которые входит Николаев, уже составлены.

Итак, получили шесть пар: Андреев-Гришин, Андреев-Степанов, Андреев-Николаев, Гришин-Степанов, Гришин-Николаев, Степанов-Николаев.

Значит, всего существует шесть вариантов выбора тренером пары спортсменов по гребле из данной группы.

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

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

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

Итак, мы составили все числа, которые начинаются с цифры два. Таких чисел шесть…..

Аналогичным способом можно составить числа, которые начинаются с цифры четыре, с цифры шесть, с цифры восемь.

Полученные результаты запишем в четыре строки, в каждой из которых шесть чисел…..

Таким образом, из цифр два, четыре, шесть, восемь можно составить двадцать четыре трехзначных числа, в записи которых цифры не повторяются.

Проведенный перебор вариантов проиллюстрирован на схеме. Такую схему называют деревом возможных вариантов….

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

Мы нашли ответ на поставленный во втором примере вопрос, используя комбинаторное правило умножения.

Сформулируем это правило в общем виде.

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

Пример третий. Из города А в город Бэ ведут три дороги, из города Бэ в город Цэ - четыре дороги, из города Це до пристани – две дороги. Туристы хотят проехать из города А через город Бэ и це к пристани. Сколькими способами они могут выбрать маршрут.

Путь из А в Бэ туристы могут добраться тремя способами. Далее в каждом случае они могут проехать из Бэ в Це четырьмя способами. Таким образом, имеются три умноженное на четыре вариантов маршрута из А в Це. Так из города Це на пристань можно попасть двумя способами, то всего существует три умноженное на четыре умноженное на два, то есть двадцать четыре способа выбора туристами маршрута из города А к пристани.