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

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

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

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

Производящие функции

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

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

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

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

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

Союз

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

Пары

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

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

Последовательность обобщает идею пары, как определено выше. Последовательности произвольные Декартовы произведения комбинаторного объекта с самим собой. Формально:

${\displaystyle {\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 }$

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

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

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

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

Двоичные и плоские деревья

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

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

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

${\displaystyle P(x)=x{\frac {1}{1-P(x)}}}$

После решения для п(Икс):

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

Явная формула для количества плоских деревьев размером п теперь можно определить, извлекая коэффициент при Икс^п.

${\displaystyle {\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}}}$

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

Выражение в последней строке равно (п − 1)^th Каталонский номер. Следовательно, п_п = c_п−1.

Смотрите также

• Алгебраическая комбинаторика
• Асимптотическая комбинаторика
• Лемма Бернсайда
• Комбинаторный взрыв
• Комбинаторная теория игр
• Комбинаторные принципы
• Комбинаторные виды
• Принцип включения-исключения
• Метод выделенного элемента
• Перечислимая теорема Полиа
• Теория сита

Рекомендации

• Зейлбергер, Дорон, Перечислительная и алгебраическая комбинаторика
• Бьёрнер, Андерс и Стэнли, Ричард П., Комбинаторный сборник
• Грэм, Рональд Л., Грётшель М., и Ловас, Ласло, ред. (1996). Справочник по комбинаторике, Тома 1 и 2. Elsevier (Северная Голландия), Амстердам, и 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.
• Комбинаторный анализ - статья в Британская энциклопедия, одиннадцатое издание
• Риордан, Джон (1958). Введение в комбинаторный анализ, Wiley & Sons, Нью-Йорк (переиздано).
• Риордан, Джон (1968). Комбинаторные идентичности, Wiley & Sons, Нью-Йорк (переиздано).
• Уилф, Герберт С. (1994). Генерацияфункционологии (2-е изд.). Бостон, Массачусетс: Academic Press. ISBN  0-12-751956-4. Zbl  0831.05001.