Перечислительная комбинаторика

Перечислительная комбинаторика — это область комбинаторики , которая изучает количество способов образования определенных шаблонов. Двумя примерами задач такого типа являются подсчет комбинаций и подсчет перестановок . В более общем смысле, учитывая бесконечную коллекцию конечных множеств Si _, индексированных натуральными числами , перечислительная комбинаторика пытается описать функцию подсчета , которая подсчитывает количество объектов в Sn _n каждого для . Хотя подсчет количества элементов в множестве является довольно широкой математической задачей , многие проблемы, возникающие в приложениях, имеют сравнительно простое комбинаторное описание. Двенадцатикратный способ обеспечивает единую основу для подсчета перестановок , комбинаций и разделов .

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

Часто сложная замкнутая формула мало что дает для понимания поведения счетной функции по мере роста числа подсчитываемых объектов. простое асимптотическое В этих случаях может оказаться предпочтительным приближение. Функция $g(n)$ является асимптотическим приближением к $f(n)$ если $f(n)/g(n)\rightarrow 1$ как $n\rightarrow \infty$ . В этом случае мы пишем $f(n)\sim g(n).\,$

Генерирующие функции

Производящие функции используются для описания семейств комбинаторных объектов. Позволять ${\mathcal {F}}$ обозначим семейство объектов и пусть F ( x ) будет его производящей функцией. Затем

F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}

где $f_{n}$ обозначает количество комбинаторных объектов размера n . количество комбинаторных объектов размера n определяется коэффициентом Таким образом , $x^{n}$ . Теперь будут разработаны некоторые общие операции над семействами комбинаторных объектов и их влияние на производящую функцию. экспоненциальная производящая функция Иногда также используется . В этом случае оно будет иметь вид

F(x)=\sum _{n=0}^{\infty }f_{n}{\frac {x^{n}}{n!}}

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

Союз

Учитывая два комбинаторных семейства, ${\mathcal {F}}$ и ${\mathcal {G}}$ с производящими функциями F ( x ) и G ( x ) соответственно, непересекающееся объединение двух семейств ( ${\mathcal {F}}\cup {\mathcal {G}}$ ) имеет производящую функцию F ( x ) + G ( x ).

Пары

Для двух комбинаторных семейств, как указано выше, декартово произведение (пара) двух семейств ( ${\mathcal {F}}\times {\mathcal {G}}$ ) имеет производящую функцию F ( x ) G ( x ).

Последовательности

(Конечная) последовательность обобщает идею пары, определенную выше. Последовательности — это произвольные декартовы произведения комбинаторного объекта на самого себя. Формально:

{\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \cdots

Если выразить вышесказанное словами: пустая последовательность, или последовательность из одного элемента, или последовательность из двух элементов, или последовательность из трех элементов и т. д.Производящая функция будет такой:

1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}.

Комбинаторные структуры

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

Бинарные и плоские деревья

Бинарные и плоские деревья являются примерами неразмеченной комбинаторной структуры. нет Деревья состоят из узлов, соединенных ребрами таким образом, что циклов . Обычно существует узел, называемый корнем, у которого нет родительского узла. В плоских деревьях каждый узел может иметь произвольное количество дочерних элементов. В двоичных деревьях (частном случае плоских деревьев) каждый узел может иметь либо двух дочерних элементов, либо не иметь их ни одного. Позволять ${\mathcal {P}}$ обозначают семейство всех плоских деревьев. Тогда это семейство можно рекурсивно определить следующим образом:

{\mathcal {P}}=\{\bullet \}\times \,{\mbox{Seq}}({\mathcal {P}})

В этом случае $\{\bullet \}$ представляет семейство объектов, состоящее из одного узла. Это имеет производящую функцию x . Пусть P ( x ) обозначает производящую функцию ${\mathcal {P}}$ .Если выразить приведенное выше описание словами, то плоское дерево состоит из узла, к которому прикреплено произвольное количество поддеревьев, каждое из которых также является плоским деревом. Используя разработанную ранее операцию над семействами комбинаторных структур, это преобразуется в рекурсивную производящую функцию: