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

Раздел комбинаторики, изучающий количество способов, которыми могут быть образованы определенные узоры.

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

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

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

Генерация функций

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

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

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

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

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

Союз

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

Пары

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

• Зейлбергер, Дорон , Перечислительная и алгебраическая комбинаторика
• Бьёрнер, Андерс и Стэнли, Ричард П. , Комбинаторный сборник
• Грэм, Рональд Л. , Гречель М. и Ловас, Ласло , ред. (1996). Справочник по комбинаторике , тома 1 и 2. Elsevier (Северная Голландия), Амстердам, и MIT Press, Кембридж, Массачусетс, ISBN  0-262-07169-X .
• Джозеф, Джордж Гевергезе (1994) [1991]. Гребень павлина: неевропейские корни математики (2-е изд.). Лондон: Penguin Books . ISBN 0-14-012529-9.
• Лоэр, Николас А. (2011). Биективная комбинаторика. CRC Press. ISBN 143984884X , ISBN 978-1439848845 .  
• Стэнли, Ричард П. (1997, 1999). Перечислительная комбинаторика, тома 1 и 2. Cambridge University Press . ISBN 0-521-55309-1 , ISBN 0-521-56069-1 .  
• Гулден, Ян П. и Джексон, Дэвид М. (2004). Комбинаторное перечисление. Dover Publications . ISBN 0486435970 . 
• Риордан, Джон (1958). Введение в комбинаторный анализ , Wiley & Sons, Нью-Йорк (переиздано).
• Риордан, Джон (1968). Комбинаторные тождества , Wiley & Sons, Нью-Йорк (переиздано).
• Wilf, Herbert S. (1994). Generatingfunctionology (2-е изд.). Бостон, Массачусетс: Academic Press. ISBN 0-12-751956-4. Збл  0831.05001.