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

Определение:

Комбинаторика - это раздел математики, который изучает, сколько различных комбинаций можно составить из заданных объектов.

Пример.

На семейном шахматном турнире Ульяна, Ярослава, Архип и Захар сыграли друг с другом только по одной партии. Сколько партий было сыграно?

Для краткости имена будем обозначать первой буквой.

Опишем состав партий, в которых принимала участие Ульяна. Получим 3 пары. Далее опишем состав партий, в которых участвовала Ярослава, но не принимала участия Ульяна. Так как пара Ульяна - Ярослава уже записана. Таким образом, получаем 2 новых пары. Запишем пары, в которые входит Архип, но не входят Ульяна и Ярослава. Получим только 1 пару. Других вариантов составления пар нет, так как все пары, куда входит Захар, уже составлены.

Итак, мы получили шесть различных пар, то есть было сыграно шесть партий.

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

Пример.

Определить, сколько различных трёхзначных чисел можно составить, используя цифры 2, 6, 8 и 9. При этом цифры в числе не должны повторяться.

Первой цифрой числа может быть любая из данных цифр. Поставим на первое место, например, цифру 2. Тогда на втором месте могут стоять цифры 6, 8 или 9. Если на втором месте стоит цифра 6, то на третьем соответственно могут быть цифры 8 или 9. Так мы получим 2 числа: 268 и 269.

Если на втором месте стоит цифра 8, то на третьем может быть 6 или 9. Также получим два числа.

И если на втором месте стоит 9, то третьей цифрой числа могут быть 6 или 8.

Аналогично можно расписать возможные варианты, если первой цифрой числа являются 6, 8 или 9.

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

Получили 24 различных трёхзначных числа.

Можно было по-другому решить задачу. Рассуждая так: первую цифру мы выбираем четырьмя способами, вторую тремя, так как после выбора первой осталось три цифры. А третью - двумя. Получаем, что общее количество искомых трёхзначных чисел равно двадцати четырём.

В данном случаи, воспользовались комбинаторным правилом умножения.

Комбинаторное правило умножения:

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

Пример.

На окружности отмечены 10 точек. Сколько можно провести незамкнутых не самопересекающихся девятизвенных линий с вершинами во всех этих точках?

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

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

Первую точку мы можем выбрать 10 способами, вторую - 9, и так до девятой точки. Ну, а десятую точку мы выбираем 1 способом, так как она остаётся одна.

Вычислим количества линий:

Пример.

У маляра в наличии три банки с красками разного цвета. Ему нужно покрасить забор, состоящий из 10 досок так, чтобы любые две соседние доски были разных цветов, и при этом были использованы краски всех трёх цветов. Сколькими способами он может выполнить поручение?

При выборе цвета для первой доски у нас будет три варианта. Тогда вторую доску мы сможем окрасить в один из двух оставшихся цветов. И так далее.

Тогда, пользуясь комбинаторным правилом умножения, получим, что для определения количества способов выполнения поручения, необходимо вычислить значение выражения: