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

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

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

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

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

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

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

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

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

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

Союз

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

Пары

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

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

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

{\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}})

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

P(x)=x\,{\frac {1}{1-P(x)}}

После решения для P ( x ):

P(x)={\frac {1-{\sqrt {1-4x}}}{2}}

Явная формула для количества плоских деревьев размера n теперь может быть определена путем извлечения коэффициента при x ⁿ :

{\begin{aligned}p_{n}&=[x^{n}]P(x)=[x^{n}]{\frac {1- {\sqrt {1-4x}}} {2}}\\[6pt]&=[x^{n}]{\frac {1}{2}}-[x^{n}]{\frac {1}{2}}{\sqrt { 1-4x}}\\[6pt]&=-{\frac {1}{2}}[x^{n}]\sum _{k=0}^{\infty }{{\frac {1} {2}} \choose k}(-4x)^{k}\\[6pt]&=-{\frac {1}{2}}{{\frac {1}{2}} \choose n}( -4)^{n}\\[6pt]&={\frac {1}{n}}{2n-2 \choose n-1}\end{aligned}}

Примечание. Обозначение [ x ⁿ ] f ( x ) относится к коэффициенту при x ⁿ в f ( x ). Разложение квадратного корня в ряд основано на обобщении Ньютона биномиальной теоремы . Для перехода с четвертой на пятую строку необходимы манипуляции с использованием обобщенного биномиального коэффициента .

Выражение в последней строке равно ( n − 1) ^-му каталонскому числу . Следовательно, p _n = c _{n −1} .