Элементы Комбинаторики

Задача 3.

Три друга – Антон, Борис и Виктор – приобрели два билета на футбольный матч на 1-е и 2-е места первого ряда стадиона. Сколько у друзей есть вариантов (способов) занять эти места на стадионе? Записать все эти варианты.

► Для удобства перечисления всех возможных вариантов рассаживания друзей на 1-е и 2-е места будем вместо полных имен мальчиков записывать лишь их первые буквы. При этом запись АБ будет означать, что на первом месте сидит Антон, а на втором – Борис. Способ составления комбинаций будет следующим:

АБ АВ БВ

БА ВА ВБ

Ответ: 6 способов

перестановки

Множество из   n   элементов меняют местами. Главное в этом деле - порядок элементов.

Число перестановок можно посчитать по формуле:

Рn = n!  ,   где   n! = 1 · 2 · 3 · ... · n

Задача 4.

Антону, Борису и Виктору повезло, и они купили 3 билета на футбол на 1, 2 и 3 –е места первого ряда стадиона. Сколькими способами могут занять мальчики эти места.

► Число способов будет таким же, как и задаче 3 из размещений:

АБ АВ БВ

БА ВА ВБ

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

АБВ АВБ БВА

БАВ ВАБ ВБА

Ответ: 6 способов

Задача 5.

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

► 1) способ составления трехзначных чисел из 3 различных цифр аналогичен способу записи троек букв в предыдущей задаче:

123 213 312

132 231 321

Получили 6 чисел.

2) Перебор вариантов можно организовать следующим образом. Выпишем все числа, начинающиеся с цифры 1 в порядке их возрастания; затем – начинающиеся с цифры 2; после чего – начинающиеся с цифры 3:

111 112 113 211 212 213 311 312 313

121 122 123 221 222 223 321 322 323

131 132 133 231 232 233 331 332 333

Получим 27 чисел.

Ответ: 1) 6; 2) 27

Нередко подсчет вариантов облегчают графы.

Так называемые геометрические фигуры, состоящие из точек (их называют вершинами) и соединяющих их отрезков (называемых ребрами графа).

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

Для удобства иллюстрации условия задачи с помощью графа его вершины-точки могут быть заменены, например, кругами или прямоугольниками, а ребра-отрезки – любыми линиями.

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

Задача 6.

Антону, Борису и Виктору повезло, и они купили 3 билета на футбол на 1, 2 и 3 –е места первого ряда стадиона. Сколькими способами могут занять мальчики эти места.

► На 1-е место может сесть любой из троих друзей, на 2-е – любой из двоих оставшихся, а на 3-е – последний. Сказанное изобразим с помощью дерева, помещая в вершины графа первые буквы имен друзей А, Б и В.

I I I место

I место

I I место

упорядоченные тройки друзей

А Б В

А

В

Б

А В Б

В

Б

Б

способы

В

А

Б А В

В

А

Б В А

В

Б

А

В А Б

Б

А

В Б А

Ответ: 6 способов

Задача 7.

Маше на день рождения подарили три букета цветов: из роз (Р), астр (А) и гвоздик (Г). В доме было две вазы: хрустальная (Х) и керамическая (К). Маша пробовала устанавливать каждый букет в каждую вазу. Перечислить все полученные сочетания букета с вазой.

► Нарисуем граф-дерево:

полученные сочетания

цветы

ваза

розы

Х - Р

хрустальная ваза

Х - А

астры

гвоздики

Х - Г

варианты

К - Р

розы

керамическая ваза

К - А

астры

К - Г

гвоздики

Ответ: 6 сочетаний