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

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

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

Часто сложная замкнутая формула дает мало информации о поведении счетной функции при увеличении числа подсчитываемых объектов. В этих случаях может оказаться предпочтительным простое асимптотическое приближение. Функция представляет собой асимптотическое приближение к if as . В этом случае мы пишем ${\ Displaystyle г (п)}$ ${\ displaystyle f (n)}$ $f(n)/g(n)\rightarrow 1$ $n\rightarrow \infty$ $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}}\cup {\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} .

См. Также [ править ]

Ссылки [ править ]

Зейльбергер, Дорон , перечислительная и алгебраическая комбинаторика
Бьёрнер, Андерс и Стэнли, Ричард П. , Комбинаторный сборник
Graham, Ronald L. , Grötschel M. , and Lovász, László , eds. (1996). Справочник по комбинаторике , тома 1 и 2. Эльзевир (Северная Голландия), Амстердам, и MIT Press, Кембридж, Массачусетс, ISBN 0-262-07169-X .
Джозеф, Джордж Гевергезе (1994) [1991]. Гребень павлина: неевропейские корни математики (2-е изд.). Лондон: Книги Пингвинов . ISBN 0-14-012529-9.
Лоер, Николас А. (2011). Биективная комбинаторика . CRC Press . ISBN 143984884X , ISBN 978-1439848845 .
Стэнли, Ричард П. (1997, 1999). Перечислительная комбинаторика , тома 1 и 2 . Издательство Кембриджского университета . ISBN 0-521-55309-1 , ISBN 0-521-56069-1 .
Гулден, Ян П. и Джексон, Дэвид М. (2004). Комбинаторное перечисление . Dover Publications . ISBN 0486435970 .
Комбинаторный анализ - статья в Encyclopædia Britannica Eleventh Edition
Риордан, Джон (1958). Введение в комбинаторный анализ , Wiley & Sons, Нью-Йорк (переиздано).
Риордан, Джон (1968). Комбинаторные идентичности , Wiley & Sons, Нью-Йорк (переиздано).
Уилф, Герберт С. (1994). Генерирующаяфункционология (2-е изд.). Бостон, Массачусетс: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001 .