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

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

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

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

Составим сначала все пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий). Получим три пары:

АГ, АС, АФ.

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

ГС, ГФ.

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

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

Итак, мы получили шесть пар:

АГ, АС, АФ,
ГС, ГФ,
СФ.

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

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

Пример 2. Сколько трехзначных чисел можно составить из цифр 1, 3, 5, 7, используя в записи числа каждую из них не более одного раза?

Чтобы ответить на вопрос задачи, выпишем все такие числа. Пусть на первом месте стоит цифра 1. На втором месте может быть записана любая из цифр 3, 5, 7. Запишем, например, на втором месте цифру 3. Тогда в качестве третьей цифры можно взять 5 или 7. Получим два числа 135 и 137. Если на втором месте записать цифру 5, то в качестве третьей цифры можно взять цифру 3 или 7. В этом случае получим числа 153 и 157. Если же, наконец, на втором месте записать цифру 7, то получим числа 173 и 175.

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

135, 137, 153, 157, 173, 175.

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

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

135, 137, 153, 157, 173, 175,
315, 317, 351, 357, 371, 375,
513, 517, 531, 537, 571, 573,
713, 715, 731, 735, 751, 753.

Таким образом, из цифр 1, 3, 5, 7 можно составить 24 трехзначных числа, в записи которых цифры не повторяются.

Продолжение >>>