Виды комбинаторных задач

В комбинаторике решаются следующие основные типы задач:

1. Существует ли конструкция, которую можно построить из элементов данного множества по заданным правилам?

2. Как выглядит описание структуры всех комбинаторных объектов, обладающих заданными свойствами?

3. Как построить пример комбинаторного объекта, имеющего заданные свойства?

4. Как построить все комбинаторные объекты с заданными свойствами?

5. Сколько существует различных комбинаторных объектов, обладающих заданными свойствами?

Для получения ответов на перечисленные вопросы используются специфические приемы представления и обработки комбинаторных объектов. Такая специфика определяется тем, что комбинаторные объекты, как правило, являются конечными и могут быть полностью представлены. Конечными или счетными оказываются и конкретные множества таких объектов.

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

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

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