Примеры комбинаторных задач
Перебор возможных вариантов Пример 1. Из группы теннисистов, в которую входят четыре человека — Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары? Составим сначала все пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий). Получим три пары: АГ, АС, АФ. Пары, в которые входит Григорьев, но не входит Антонов: ГС, ГФ. Пары, в которые входит Сергеев, но не входят Антонов и Григорьев: СФ. Других вариантов составления пар нет, так как все пары, в которые входит Федоров, уже составлены. Итак, мы получили шесть пар: АГ, АС, АФ, ГС, ГФ, СФ. Значит, всего существует шесть вариантов выбора тренером пары теннисистов из данной группы. Способ рассуждений, которым мы воспользовались при решении задачи, называют перебором возможных вариантов. Перестановки
Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки. Пример. Пусть имеются три книги. Обозначим их буквами а, Ъ и с. Эти книги можно расставить на полке по-разному. Если первой поставить книгу а, то возможны такие расположения книг: abc, acb. Если первой поставить книгу Ь, то возможными являются такие расположения:bac, bca. И наконец, если первой поставить книгу с, то получим такие расположения:cab, cba. Каждое из этих расположений называют перестановкой из трех элементов.