Комбинаторика

Лейбницем В 1666 году Лейбниц опубликовал «Рассуждения о комбинаторном искусстве».
Комбинаторику он понимал, как составляющую любого исследования, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое).

Леонард Эйлер рассматривал задачи о разбиении чисел, о построении магических и латинских квадратов.

в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты.
Сочинение Я. Бернулли превзошло работы его предшественников систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью, как учебно-справочное издание.

Термин «тактика» ввёл в математику английский математик Джеймс Джозеф Сильвестр в 1861 году.
Сильвестр определял тактику как раздел математики, изучающий расположение элементов друг относительно друга.

n или k < n).
Эти соединения отличаются друг от друга только самими элементами.

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

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

►По имеющимся двум билетам на матч могут пойти:
1) либо Антон и Борис;
2) либо Антон и Виктор;
3) либо Борис и Виктор.
Ответ: Три варианта.

Задача 1.

можно приготовить, если в каждый из них должны входить в равных долях 2 различных вида овощей? Записать все сочетания овощей в составленных салатах.

П О
П Л
О Л

►Расположим данные овощи по порядку: П, О, Л. Запишем все сочетания овощей в салатах. Будем брать поочередно каждый овощ (кроме последнего) и добавлять к нему по одному только из последующих, поскольку порядок выбора не важен

Ответ: 3 вида салатов

Задача 2.

n или k < n) создают соединения, которые отличаются друг от друга элементами или порядком их расположения.

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

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

АБ АВ БВ
БА ВА ВБ

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

Задача 3.

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

3 · ... · n

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

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

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

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

Задача 4.

АБ АВ БВ
БА ВА ВБ

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

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

АБВ АВБ БВА
БАВ ВАБ ВБА

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

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

Задача 5.

►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 чисел.

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

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

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

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

Задача 6.

В

А В Б

Б А В

Б В А

В А Б

В Б А

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

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