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

Комбинаторика – ветвь математики, изучающая комбинации и перестановки предметов, общие законы комбинирования и образования различных конфигураций объектов возникла в XVII в. С задачами, в которых приходится выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди расположений наилучшие люди столкнулись еще в доисторическую эпоху, выбирая наилучшие расположения охотников во время охоты, воинов во время битвы, инструментов во время работы. Определенным образом располагались украшения на одежде, узоры на керамике, перья в оперении стрелы. По мере усложнения производственных и общественных отношений все шире приходилось пользоваться общими понятиями о порядке, иерархии, группировании. В том же направлении действовало развитие ремесел и торговли.

В первом приближении можно сказать, что комбинаторика изучает способы выборки и расположения предметов, свойства различных конфигураций, которые можно образовать из элементов, причем элементами могут быть числа, точки, отрезки, шахматные фигуры и т. д. Характерной чертой комбинаторных задач является то, что в них речь идет всегда о конечном множестве элементов. Чтобы устранить влияние конкретного вида выбираемых и располагаемых предметов, надо воспользоваться общим языком теории множеств, говорить о множествах и их подмножествах (частях), об объединении нескольких множеств и их пересечении (образовании общей части).

Правило суммы.

Пример. Если множество А состоит из букв (элементов) , а множество В = , то их пересечение .Тогда, количество элементов их объединения найдется по правилу суммы:

По правилу суммы легко найти элементы некоторого множества U, не принадлежащие ни одному из подмножеств этого множества. Сначала надо найти количество элементов в объединении , а затем вычесть это число из числа элементов U.

Пример. В классе обучаются 42 ученика.

Из них 16 участвуют в секции по легкой атлетике, 24– в футбольной секции, 15 – в шахматной секции, 11 – и в секции легкой атлетики и в футбольной секции, 8 – в легкоатлетической и шахматной, 12 – в футбольной и шахматной, 6 – во всех трех секциях. Остальные увлекаются только туризмом. Сколько школьников являются туристами?

Решение. Обозначим через U множество всех учащихся, через А – членов легкоатлетической секции, В – футбольной, С – Шахматной, D – туристической. По условию задачи имеем:

причем

Тогда по формуле (5) получаем, что

и потому

Таким образом, туризмом занимаются 12 школьников.

Правило произведения

Пусть имеем несколько конечных множеств , причем .

По теореме о мощности прямого произведения множеств, число векторов , которые можно составить из элементов данных множеств, равно , так как

= .

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