Введение
Область комбинаторики, изучающая количество способов формирования определенных закономерностей. Перечислительная комбинаторика – это область комбинаторики, которая занимается определением количества способов, которыми могут быть сформированы определенные структуры. Два примера задач такого типа – подсчет сочетаний и подсчет перестановок. В более общем виде, для бесконечного набора конечных множеств Si, индексированных натуральными числами, перечислительная комбинаторика стремится описать функцию подсчета, которая определяет количество объектов в Sn для каждого n. Хотя подсчет количества элементов в множестве является достаточно общей математической задачей, многие задачи, возникающие в приложениях, имеют относительно простое комбинаторное описание. Метод двенадцати способов предоставляет единую основу для подсчета перестановок, сочетаний и разбиений. Самые простые такие функции – это замкнутые формулы, которые можно выразить как композицию элементарных функций, таких как факториалы, степени и так далее. Например, как показано ниже, число различных возможных упорядочиваний колоды из n карт равно f(n) = n!. Задача нахождения замкнутой формулы известна как алгебраическое перечисление и часто включает в себя вывод рекуррентного соотношения или производящей функции и использование их для получения желаемой замкнутой формы. Часто сложная замкнутая формула дает мало информации о поведении функции подсчета при увеличении числа подсчитываемых объектов. В этих случаях предпочтительнее использовать простое асимптотическое приближение. Функция является асимптотическим приближением к , если , в этом случае мы записываем
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions. The simplest such functions are closed formulas, which can be expressed as a composition of elementary functions such as factorials, powers, and so on. For instance, as shown below, the number of different possible orderings of a deck of n cards is f(n) = n!. The problem of finding a closed formula is known as algebraic enumeration, and frequently involves deriving a recurrence relation or generating function and using this to arrive at the desired closed form. Often, a complicated closed formula yields little insight into the behavior of the counting function as the number of counted objects grows. In these cases, a simple asymptotic approximation may be preferable. A function is an asymptotic approximation to if as In this case, we write
Функции генерации
Функции генерации используются для описания семейств комбинаторных объектов. Пусть обозначает семейство объектов, а F(x) – его генерирующую функцию. Тогда
где обозначает количество комбинаторных объектов размера n. Следовательно, количество комбинаторных объектов размера n определяется коэффициентом при x^n в разложении F(x). Теперь будут рассмотрены некоторые общие операции над семействами комбинаторных объектов и их влияние на генерирующую функцию. Также иногда используется экспоненциальная генерирующая функция. В этом случае она имеет вид
После определения генерирующая функция предоставляет информацию, полученную предыдущими методами. Кроме того, различные естественные операции над генерирующими функциями, такие как сложение, умножение, дифференцирование и т.д., имеют комбинаторный смысл; это позволяет распространять результаты из одной комбинаторной задачи для решения других.
Союз
При заданных двух комбинаторных семействах и с генерирующими функциями F(x) и G(x) соответственно, дизъюнктное объединение этих двух семейств имеет генерирующую функцию F(x) + G(x).
Пары
Для двух комбинаторных семейств, как описано выше, декартово произведение (пара) этих семейств имеет порождающую функцию F(x)G(x).
Комбинаторные структуры
Вышеуказанные операции теперь могут быть использованы для перечисления распространенных комбинаторных объектов, включая деревья (двоичные и плоские), пути Дика и циклы. Комбинаторная структура состоит из атомов. Например, для деревьев атомами будут узлы. Атомы, составляющие объект, могут быть маркированными или немаркированными. Немаркированные атомы неразличимы друг для друга, тогда как маркированные атомы различны. Следовательно, для комбинаторного объекта, состоящего из маркированных атомов, можно создать новый объект, просто поменяв местами два или более атомов.