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

Перечислительная комбинаторика — это область комбинаторики , которая изучает количество способов формирования определенных шаблонов. Двумя примерами задач такого типа являются подсчет комбинаций и подсчет перестановок . В более общем смысле, учитывая бесконечную коллекцию конечных множеств 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}}$. Если выразить приведенное выше описание словами, то плоское дерево состоит из узла, к которому прикреплено произвольное количество поддеревьев, каждое из которых также является плоским деревом. Используя разработанную ранее операцию над семействами комбинаторных структур, это преобразуется в рекурсивную производящую функцию:

$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 ^н в ж ( х ). Разложение квадратного корня в ряд основано на обобщении Ньютона биномиальной теоремы . Для перехода с четвертой на пятую строку манипуляции с использованием обобщенного биномиального коэффициента необходимы .

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

См. также

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

Ссылки

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