ЭЛЕМЕНТЫКОМБИНАТОРИКИ
ОСНОВНЫЕ ПОНЯТИЯ
Комбинаторика занимается изучением свойств конечных конструкций или объектов, составленных по определенным правилам из элементов счетных множеств. Такие объекты будем называть комбинаторными объектами.
Рассмотрим несколько примеров:
1) последовательности десятичных цифр, образующих правильные записи, представляющие натуральные числа. В этом случае рассматриваемые конструкции собираются в виде записей, составленных из символов десятичных цифр, в которых допускается многократное вхождение одних и тех же символов;
2) правильные записи математических выражений, составленных с помощью математических символов;
3) разнообразные комбинации цветов (букеты) также представляют собой примеры конструкций (заметим, что в данном случае правила составления букетов могут быть достаточно сложными и даже трудно объяснимыми);
4) радиоустройства, конструируемые как соединения различных радиодеталей, также можно рассматривать как комбинаторные объекты;
5) мозаики, составляемые из геометрических фигур заданной формы.
К постановкам задач изучения комбинаторных объектов приводят различные практические потребности в разнообразных областях деятельности.
Например, рассмотрим задачу нахождения вида полинома, получаемого после раскрытия скобок в выражении (x + y) k.
Понятно, что этот полином представляет собой сумму вида: 
Здесь a m , n - коэффициент при произведении переменных x m y n.
Для нахождения значения произвольного коэффициента a m , n достаточно определить, сколькими разными способами в последовательности из k перемножаемых выражений (x + y) можно выделить m таких, из которых в составляемое произведение входит x. При этом из остальных m - k выражений x + y произведения (x + y)k выбирается y.
Рассмотрим еще один пример. Пусть в продаже имеются 15 видов игрушечных автомобилей, из которых составляются подарки, содержащие по три разных автомобиля.
Сколько детей может присутствовать на новогоднем празднике так, чтобы каждый ребенок получил подарок, отличный от подарков для других детей.
Нетрудно видеть, что приведенная задача равносильна задаче нахождения числа трехэлементных подмножеств множества, состоящего из 15 элементов.
ВИДЫКОМБИНАТОРНЫХ ЗАДАЧ
В комбинаторике решаются следующие основные типы задач:
1. Существует ли конструкция, которую можно построить из элементов данного множества по заданным правилам?
2. Как выглядит описание структуры всех комбинаторных объектов, обладающих заданными свойствами?
3. Как построить пример комбинаторного объекта, имеющего заданные свойства?
4. Как построить все комбинаторные объекты с заданными свойствами?
5. Сколько существует различных комбинаторных объектов, обладающих заданными свойствами?
Для получения ответов на перечисленные вопросы используются специфические приемы представления и обработки комбинаторных объектов. Такая специфика определяется тем, что комбинаторные объекты, как правило, являются конечными и могут быть полностью представлены. Конечными или счетными оказываются и конкретные множества таких объектов.
По сравнению с традиционными объектами математики комбинаторные объекты могут иметь более сложную структуру и поэтому оказываются сложными для изучения. Для таких объектов характерно отсутствие непрерывности свойств, проявляющееся в возможности значительного изменения свойств уже при незначительных изменениях в самих объектах.
В настоящем пособии в основном будут рассматриваться задачи, связанные с построением комбинаторных описаний объектов, обладающих заданными свойствами. Кроме того, будет рассмотрена задача определения числа таких объектов. Решение этих задач делает возможным принципиальное решение и других задач. Например, знание структуры описаний объектов из класса, в котором содержатся необходимые объекты, позволяет организовать перебор всех возможных объектов с целью нахождения подходящих. При этом знание количества объектов заданной структуры позволяет оценить возможную продолжительность перебора.
Арифметические выражения и конструкции, позволяющие определять количество комбинаторных объектов с заданными свойствами, называются комбинаторными формулами.