Символический метод (комбинаторика)

В комбинаторике символический метод — это метод подсчёта комбинаторных объектов . Он использует внутреннюю структуру объектов для вывода формул для их производящих функций . Метод в основном связан с Филиппом Флажоле и подробно описан в Части А его книги с Робертом Седжвиком «Аналитическая комбинаторика» , в то время как остальная часть книги объясняет, как использовать комплексный анализ для получения асимптотических и вероятностных результатов для соответствующих производящих функций.

В течение двух столетий производящие функции появлялись посредством соответствующих рекуррентных соотношений их коэффициентов (как можно увидеть в основополагающих работах Бернулли , Эйлера , Артура Кэли , Шредера , Рамануджана , Риордана , Кнута , Контета  [фр] и т. д.). Затем постепенно стало понятно, что производящие функции охватывают многие другие грани исходных дискретных комбинаторных объектов и что это можно сделать более прямым формальным способом: рекурсивная природа некоторых комбинаторных структур преобразуется посредством некоторых изоморфизмов в заслуживающие внимания тождества соответствующих производящих функций. После работ Полиа в 1970-х годах в этом духе были достигнуты дальнейшие успехи с использованием общих языков для спецификации комбинаторных классов и их генерирующих функций, как это было обнаружено в работах Фоаты и Шютценбергера ^[1] по перестановкам, Бендера и Голдмана по префабам ^[2] и Джояла по комбинаторным видам ^[3] .

Обратите внимание, что этот символический метод перечисления не имеет отношения к «символическому методу Блиссара», который является просто еще одним старым названием теневого исчисления .

Символический метод в комбинаторике представляет собой первый шаг многих анализов комбинаторных структур, которые затем могут привести к быстрым схемам вычислений, к асимптотическим свойствам и предельным законам , к случайной генерации , причем все они пригодны для автоматизации посредством компьютерной алгебры .

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

Рассмотрим задачу распределения объектов, заданных производящей функцией, в набор из n слотов, где группа перестановок G степени n действует на слоты, чтобы создать отношение эквивалентности заполненных конфигураций слотов, и спросим о производящей функции конфигураций по весу конфигураций относительно этого отношения эквивалентности, где вес конфигурации является суммой весов объектов в слотах. Сначала мы объясним, как решить эту задачу в маркированном и немаркированном случае, и используем решение для мотивации создания классов комбинаторных структур .

Теорема перечисления Полиа решает эту проблему в немаркированном случае. Пусть f ( z ) будет обычной производящей функцией (OGF) объектов, тогда OGF конфигураций задается подставленным индексом цикла

${\displaystyle Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n})).}$

В маркированном случае мы используем экспоненциальную производящую функцию (EGF) g ( z ) объектов и применяем теорему о маркированном перечислении , которая гласит, что EGF конфигураций определяется как

${\displaystyle {\frac {g(z)^{n}}{|G|}}.}$

Мы можем перечислить заполненные конфигурации слотов, используя либо PET в немаркированном случае, либо теорему о перечислении с метками в маркированном случае. Теперь мы спрашиваем о производящей функции конфигураций, полученных, когда имеется более одного набора слотов, с группой перестановок, действующей на каждый из них. Очевидно, что орбиты не пересекаются, и мы можем добавить соответствующие производящие функции. Предположим, например, что мы хотим перечислить немаркированные последовательности длиной два или три некоторых объектов, содержащихся в наборе X . Есть два набора слотов, первый из которых содержит два слота, а второй — три слота. Группа, действующая на первый набор, — это , а на второй слот — . Мы представляем это следующим формальным степенным рядом по X : ${\displaystyle E_{2}}$ ${\displaystyle E_{3}}$

${\displaystyle X^{2}/E_{2}\;+\;X^{3}/E_{3}}$

где термин используется для обозначения множества орбит под G и , что очевидным образом обозначает процесс распределения объектов из X с повторением в n слотов. Аналогично рассмотрим помеченную задачу создания циклов произвольной длины из множества помеченных объектов X . Это дает следующую серию действий циклических групп: ${\displaystyle X^{n}/G}$ ${\displaystyle X^{n}=X\times \cdots \times X}$

${\displaystyle X/C_{1}\;+\;X^{2}/C_{2}\;+\;X^{3}/C_{3}\;+\;X^{4}/C_{4}\;+\cdots .}$

Очевидно, мы можем придать значение любому такому степенному ряду частных (орбит) относительно групп перестановок, где мы ограничиваем группы степени n классами сопряженности симметрической группы , которые образуют уникальную область факторизации. (Орбиты относительно двух групп из одного и того же класса сопряженности изоморфны.) Это мотивирует следующее определение. ${\displaystyle \operatorname {Cl} (S_{n})}$ ${\displaystyle S_{n}}$

Класс комбинаторных структур — это формальный ряд ${\displaystyle {\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]}$

${\displaystyle {\mathcal {C}}=\sum _{n\geq 1}\sum _{G\in \operatorname {Cl} (S_{n})}c_{G}(X^{n}/G)}$

где («А» означает «атомы») — это множество простых чисел UFD и ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle \{\operatorname {Cl} (S_{n})\}_{n\geq 1}}$ ${\displaystyle c_{G}\in \mathbb {N} .}$

Далее мы немного упростим нашу запись и запишем, например,

${\displaystyle E_{2}+E_{3}{\text{ and }}C_{1}+C_{2}+C_{3}+\cdots .}$

для классов, указанных выше.

Основная теорема Флажоле-Седжвика

Теорема в теории символической комбинаторики Флажоле–Седжвика рассматривает проблему перечисления помеченных и непомеченных комбинаторных классов посредством создания символических операторов, которые позволяют переводить уравнения, включающие комбинаторные структуры, напрямую (и автоматически) в уравнения относительно производящих функций этих структур.

Пусть будет классом комбинаторных структур. OGF , где X имеет OGF , и EGF , где X помечен EGF, задаются как ${\displaystyle {\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]}$ ${\displaystyle F(z)}$ ${\displaystyle {\mathcal {C}}(X)}$ ${\displaystyle f(z)}$ ${\displaystyle G(z)}$ ${\displaystyle {\mathcal {C}}(X)}$ ${\displaystyle g(z)}$

${\displaystyle F(z)=\sum _{n\geq 1}\sum _{G\in \operatorname {Cl} (S_{n})}c_{G}Z(G)(f(z),f(z^{2}),\ldots ,f(z^{n}))}$

и

${\displaystyle G(z)=\sum _{n\geq 1}\left(\sum _{G\in \operatorname {Cl} (S_{n})}{\frac {c_{G}}{|G|}}\right)g(z)^{n}.}$

В маркированном случае у нас есть дополнительное требование, чтобы X не содержал элементов нулевого размера. Иногда будет удобно добавить единицу к , чтобы указать на наличие одной копии пустого множества. Можно присвоить значение обоим (наиболее распространенным примером является случай немаркированных множеств) и Для доказательства теоремы просто примените PET (теорему перечисления Пойа) и маркированную теорему перечисления. ${\displaystyle G(z)}$ ${\displaystyle {\mathcal {C}}\in \mathbb {Z} [{\mathfrak {A}}]}$ ${\displaystyle {\mathcal {C}}\in \mathbb {Q} [{\mathfrak {A}}].}$

Сила этой теоремы заключается в том, что она позволяет строить операторы на производящих функциях, представляющих комбинаторные классы. Таким образом, структурное уравнение между комбинаторными классами напрямую переводится в уравнение в соответствующих производящих функциях. Более того, в отмеченном случае из формулы очевидно, что мы можем заменить на атом z и вычислить результирующий оператор, который затем может быть применен к EGF. Теперь мы приступим к построению наиболее важных операторов. Читатель может пожелать сравнить с данными на странице индекса цикла . ${\displaystyle g(z)}$

Оператор последовательности.mw-parser-output .nobold{font-weight:normal}ПОСЛЕДОВАТЕЛЬНОСТЬ

Этот оператор соответствует классу

${\displaystyle 1+E_{1}+E_{2}+E_{3}+\cdots }$

и представляет собой последовательности, т.е. слоты не переставляются и есть ровно одна пустая последовательность. Мы имеем

${\displaystyle F(z)=1+\sum _{n\geq 1}Z(E_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=1+\sum _{n\geq 1}f(z)^{n}={\frac {1}{1-f(z)}}}$

и

${\displaystyle G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|E_{n}|}}\right)g(z)^{n}={\frac {1}{1-g(z)}}.}$

Оператор циклаЦИК

Этот оператор соответствует классу

${\displaystyle C_{1}+C_{2}+C_{3}+\cdots }$

т.е. циклы, содержащие хотя бы один объект. У нас есть

${\displaystyle F(z)=\sum _{n\geq 1}Z(C_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))=\sum _{n\geq 1}{\frac {1}{n}}\sum _{d\mid n}\varphi (d)f(z^{d})^{n/d}}$

или

${\displaystyle F(z)=\sum _{k\geq 1}\varphi (k)\sum _{m\geq 1}{\frac {1}{km}}f(z^{k})^{m}=\sum _{k\geq 1}{\frac {\varphi (k)}{k}}\log {\frac {1}{1-f(z^{k})}}}$

и

${\displaystyle G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{n}|}}\right)g(z)^{n}=\log {\frac {1}{1-g(z)}}.}$

Этот оператор, вместе с оператором множеств SET и их ограничениями на определенные степени, используются для вычисления статистики случайных перестановок . Существует два полезных ограничения этого оператора, а именно на четные и нечетные циклы.

Помеченный оператор четного цикла CYC _even есть

${\displaystyle C_{2}+C_{4}+C_{6}+\cdots }$

что дает

${\displaystyle G(z)=\sum _{n\geq 1}\left({\frac {1}{|C_{2n}|}}\right)g(z)^{2n}={\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}.}$

Это подразумевает, что помеченный нечетный оператор цикла CYC _odd

${\displaystyle C_{1}+C_{3}+C_{5}+\cdots }$

дается

${\displaystyle G(z)=\log {\frac {1}{1-g(z)}}-{\frac {1}{2}}\log {\frac {1}{1-g(z)^{2}}}={\frac {1}{2}}\log {\frac {1+g(z)}{1-g(z)}}.}$

Оператор мультимножества/множестваМСЕТ / НАБОР

Сериал - это

${\displaystyle 1+S_{1}+S_{2}+S_{3}+\cdots }$

т. е. симметричная группа применяется к слотам. Это создает мультимножества в немаркированном случае и наборы в маркированном случае (в маркированном случае мультимножеств нет, поскольку метки отличают несколько экземпляров одного и того же объекта от набора, помещаемого в разные слоты). Мы включаем пустой набор как в маркированный, так и в немаркированный случай.

Немаркированный случай выполняется с помощью функции

${\displaystyle M(f(z),y)=\sum _{n\geq 0}y^{n}Z(S_{n})(f(z),f(z^{2}),\ldots ,f(z^{n}))}$

так что

${\displaystyle {\mathfrak {M}}(f(z))=M(f(z),1).}$

Оценивая получаем ${\displaystyle M(f(z),1)}$

${\displaystyle F(z)=\exp \left(\sum _{\ell \geq 1}{\frac {f(z^{\ell })}{\ell }}\right).}$

Для отмеченного случая имеем

${\displaystyle G(z)=1+\sum _{n\geq 1}\left({\frac {1}{|S_{n}|}}\right)g(z)^{n}=\sum _{n\geq 0}{\frac {g(z)^{n}}{n!}}=\exp g(z).}$

В маркированном случае мы обозначаем оператор как SET , а в немаркированном случае как MSET . Это происходит потому, что в маркированном случае нет мультимножеств (метки различают составляющие составного комбинаторного класса), тогда как в немаркированном случае есть мультимножества и множества, причем последние задаются как

${\displaystyle F(z)=\exp \left(\sum _{\ell \geq 1}(-1)^{\ell -1}{\frac {f(z^{\ell })}{\ell }}\right).}$

Процедура

Обычно начинают с нейтрального класса , содержащего один объект размера 0 ( нейтральный объект , часто обозначаемый как ), и одного или нескольких атомарных классов , каждый из которых содержит один объект размера 1. Затем теоретико-множественные отношения, включающие различные простые операции, такие как непересекающиеся объединения , произведения , множества , последовательности и мультимножества, определяют более сложные классы в терминах уже определенных классов. Эти отношения могут быть рекурсивными . Элегантность символической комбинаторики заключается в том, что теоретико-множественные или символические отношения напрямую переводятся в алгебраические отношения, включающие производящие функции. ${\displaystyle {\mathcal {E}}}$ ${\displaystyle \epsilon }$ ${\displaystyle {\mathcal {Z}}}$

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

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

Тривиально показать, что производящие функции (обычные или показательные) для и являются и , соответственно. Непересекающееся объединение также просто — для непересекающихся множеств и , подразумевает . Отношения, соответствующие другим операциям, зависят от того, говорим ли мы о помеченных или не помеченных структурах (и об обычных или показательных производящих функциях). ${\displaystyle {\mathcal {E}}}$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle E(z)=1}$ ${\displaystyle Z(z)=z}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {A}}={\mathcal {B}}\cup {\mathcal {C}}}$ ${\displaystyle A(z)=B(z)+C(z)}$

Комбинаторная сумма

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

${\displaystyle {\mathcal {A}}+{\mathcal {B}}=({\mathcal {A}}\times \{\circ \})\cup ({\mathcal {B}}\times \{\bullet \})}$

Это операция, которая формально соответствует сложению.

Немаркированные структуры

С немаркированными структурами используется обычная генерирующая функция (OGF). OGF последовательности определяется как ${\displaystyle A_{n}}$

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}x^{n}}$

Продукт

Произведение двух комбинаторных классов и задается путем определения размера упорядоченной пары как суммы размеров элементов в паре. Таким образом, для и , . Это должно быть довольно интуитивное определение. Теперь заметим, что количество элементов в размера n равно ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle a\in {\mathcal {A}}}$ ${\displaystyle b\in {\mathcal {B}}}$ ${\displaystyle |(a,b)|=|a|+|b|}$ ${\displaystyle {\mathcal {A}}\times {\mathcal {B}}}$

${\displaystyle \sum _{k=0}^{n}A_{k}B_{n-k}.}$

Используя определение ОГФ и некоторую элементарную алгебру, мы можем показать, что

${\displaystyle {\mathcal {A}}={\mathcal {B}}\times {\mathcal {C}}}$подразумевает ${\displaystyle A(z)=B(z)\cdot C(z).}$

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

Последовательность построения , обозначенная как, определяется как ${\displaystyle {\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}}$

${\displaystyle {\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\times {\mathcal {B}})+({\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}})+\cdots .}$

Другими словами, последовательность является нейтральным элементом, или элементом , или упорядоченной парой, упорядоченной тройкой и т. д. Это приводит к соотношению ${\displaystyle {\mathcal {B}}}$

${\displaystyle A(z)=1+B(z)+B(z)^{2}+B(z)^{3}+\cdots ={\frac {1}{1-B(z)}}.}$

Набор

Конструкция множества (или powerset ) , обозначаемая как, определяется как ${\displaystyle {\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}}$

${\displaystyle {\mathfrak {P}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}({\mathcal {E}}+\{\beta \}),}$

что приводит к соотношению

${\displaystyle {\begin{aligned}A(z)&{}=\prod _{\beta \in {\mathcal {B}}}(1+z^{|\beta |})\\&{}=\prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\\&{}=\exp \left(\ln \prod _{n=1}^{\infty }(1+z^{n})^{B_{n}}\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }B_{n}\ln(1+z^{n})\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }B_{n}\cdot \sum _{k=1}^{\infty }{\frac {(-1)^{k-1}z^{nk}}{k}}\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}}{k}}\cdot \sum _{n=1}^{\infty }B_{n}z^{nk}\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}B(z^{k})}{k}}\right),\end{aligned}}}$

где расширение

${\displaystyle \ln(1+u)=\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}u^{k}}{k}}}$

использовался для перехода с линии 4 на линию 5.

Мультисет

Конструкция мультимножества , обозначенная как является обобщением конструкции множества. В конструкции множества каждый элемент может встречаться ноль или один раз. В мультимножестве каждый элемент может встречаться произвольное количество раз. Следовательно, ${\displaystyle {\mathcal {A}}={\mathfrak {M}}\{{\mathcal {B}}\}}$

${\displaystyle {\mathfrak {M}}\{{\mathcal {B}}\}=\prod _{\beta \in {\mathcal {B}}}{\mathfrak {G}}\{\beta \}.}$

Это приводит к соотношению

${\displaystyle {\begin{aligned}A(z)&{}=\prod _{\beta \in {\mathcal {B}}}(1-z^{|\beta |})^{-1}\\&{}=\prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\\&{}=\exp \left(\ln \prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\right)\\&{}=\exp \left(\sum _{n=1}^{\infty }-B_{n}\ln(1-z^{n})\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {B(z^{k})}{k}}\right),\end{aligned}}}$

где, аналогично приведенной выше конструкции множества, мы расширяем , меняем местами суммы и заменяем OGF на . ${\displaystyle \ln(1-z^{n})}$ ${\displaystyle {\mathcal {B}}}$

Другие элементарные конструкции

Другими важными элементарными конструкциями являются:

• конструкция цикла ( ) , подобная последовательностям, за исключением того, что циклические вращения не считаются отдельными ${\displaystyle {\mathfrak {C}}\{{\mathcal {B}}\}}$
• указывая ( ), в котором каждый член B дополняется нейтральным (нулевого размера) указателем на один из его атомов ${\displaystyle \Theta {\mathcal {B}}}$
• замещение ( ), при котором каждый атом в элементе B заменяется элементом C . ${\displaystyle {\mathcal {B}}\circ {\mathcal {C}}}$

Выводы для этих конструкций слишком сложны, чтобы показать их здесь. Вот результаты:

Примеры

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

${\displaystyle {\mathcal {G}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {G}}\}.}$

Другими словами, дерево — это корневой узел размера 1 и последовательность поддеревьев. Это дает

${\displaystyle G(z)={\frac {z}{1-G(z)}}}$

мы решаем для G ( z ) путем умножения , чтобы получить ${\displaystyle 1-G(z)}$

${\displaystyle G(z)-G(z)^{2}=z}$

вычитание z и решение для G(z) с использованием квадратной формулы дает

${\displaystyle G(z)={\frac {1-{\sqrt {1-4z}}}{2}}.}$

Другой пример (и классическая комбинаторная задача) — целочисленные разбиения . Сначала определим класс положительных целых чисел , где размер каждого целого числа — это его значение: ${\displaystyle {\mathcal {I}}}$

${\displaystyle {\mathcal {I}}={\mathcal {Z}}\times \operatorname {SEQ} \{{\mathcal {Z}}\}}$

Тогда OGF равен ${\displaystyle {\mathcal {I}}}$

${\displaystyle I(z)={\frac {z}{1-z}}.}$

Теперь определим набор разделов как ${\displaystyle {\mathcal {P}}}$

${\displaystyle {\mathcal {P}}=\operatorname {MSET} \{{\mathcal {I}}\}.}$

OGF — это ${\displaystyle {\mathcal {P}}}$

${\displaystyle P(z)=\exp \left(I(z)+{\frac {1}{2}}I(z^{2})+{\frac {1}{3}}I(z^{3})+\cdots \right).}$

К сожалению, замкнутой формы для не существует ; однако, ОГФ можно использовать для вывода рекуррентного соотношения или, используя более продвинутые методы аналитической комбинаторики, вычислить асимптотическое поведение последовательности подсчета. ${\displaystyle P(z)}$

Спецификация и определяемые классы

Упомянутые выше элементарные конструкции позволяют нам определить понятие спецификации . Эта спецификация позволяет нам использовать набор рекурсивных уравнений с несколькими комбинаторными классами.

Формально спецификация для набора комбинаторных классов представляет собой набор уравнений , где — выражение, атомами которого являются и , а операторами — перечисленные выше элементарные конструкции. ${\displaystyle ({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$ ${\displaystyle r}$ ${\displaystyle {\mathcal {A}}_{i}=\Phi _{i}({\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r})}$ ${\displaystyle \Phi _{i}}$ ${\displaystyle {\mathcal {E}},{\mathcal {Z}}}$ ${\displaystyle {\mathcal {A}}_{i}}$

Класс комбинаторных структур называется конструируемым или специфицируемым, если он допускает спецификацию.

Например, множество деревьев, глубина листьев которых четная (соответственно, нечетная), можно определить с помощью спецификации с двумя классами и . Эти классы должны удовлетворять уравнению и . ${\displaystyle {\mathcal {A}}_{\text{even}}}$ ${\displaystyle {\mathcal {A}}_{\text{odd}}}$ ${\displaystyle {\mathcal {A}}_{\text{odd}}={\mathcal {Z}}\times \operatorname {Seq} _{\geq 1}{\mathcal {A}}_{\text{even}}}$ ${\displaystyle {\mathcal {A}}_{\text{even}}={\mathcal {Z}}\times \operatorname {Seq} {\mathcal {A}}_{\text{odd}}}$

Маркированные структуры

Объект слабо помечен, если каждый из его атомов имеет неотрицательную целочисленную метку, и каждая из этих меток различна. Объект ( сильно или хорошо ) помечен , если, кроме того, эти метки включают в себя последовательные целые числа . Примечание: некоторые комбинаторные классы лучше всего определять как помеченные структуры или непомеченные структуры, но некоторые легко допускают обе спецификации. Хорошим примером помеченных структур является класс помеченных графов . ${\displaystyle [1\ldots n]}$

С маркированными структурами используется экспоненциальная производящая функция (EGF). EGF последовательности определяется как ${\displaystyle A_{n}}$

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}.}$

Продукт

Для маркированных структур мы должны использовать другое определение для продукта, чем для немаркированных структур. Фактически, если бы мы просто использовали декартово произведение, полученные структуры даже не были бы хорошо маркированы. Вместо этого мы используем так называемый маркированный продукт , обозначаемый ${\displaystyle {\mathcal {A}}\star {\mathcal {B}}.}$

Для пары и мы хотим объединить две структуры в одну. Для того чтобы результат был хорошо маркирован, это требует некоторой перемаркировки атомов в и . Мы ограничим наше внимание перемаркировками, которые соответствуют порядку исходных меток. Обратите внимание, что все еще существует несколько способов сделать перемаркировку; таким образом, каждая пара членов определяет не одного члена в произведении, а набор новых членов. Подробности этой конструкции можно найти на странице Теорема о перечислении с метками . ${\displaystyle \beta \in {\mathcal {B}}}$ ${\displaystyle \gamma \in {\mathcal {C}}}$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$

Чтобы помочь этому развитию, давайте определим функцию , которая берет в качестве аргумента (возможно, слабо) помеченный объект и перемаркирует его атомы в согласованном порядке, так что он хорошо помечен. Затем мы определяем помеченный продукт для двух объектов и как ${\displaystyle \rho }$ ${\displaystyle \alpha }$ ${\displaystyle \rho (\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$

${\displaystyle \alpha \star \beta =\{(\alpha ',\beta '):(\alpha ',\beta '){\text{ is well-labelled, }}\rho (\alpha ')=\alpha ,\rho (\beta ')=\beta \}.}$

Наконец, помеченный продукт двух классов и есть ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

${\displaystyle {\mathcal {A}}\star {\mathcal {B}}=\bigcup _{\alpha \in {\mathcal {A}},\beta \in {\mathcal {B}}}(\alpha \star \beta ).}$

EGF можно вывести, заметив, что для объектов размером и существуют способы перемаркировки. Таким образом, общее количество объектов размером равно ${\displaystyle k}$ ${\displaystyle n-k}$ ${\displaystyle {n \choose k}}$ ${\displaystyle n}$

${\displaystyle \sum _{k=0}^{n}{n \choose k}A_{k}B_{n-k}.}$

Это биномиальное соотношение свертки для членов эквивалентно умножению EGF,

${\displaystyle A(z)\cdot B(z).}$

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

Построение последовательности определяется аналогично немаркированному случаю: ${\displaystyle {\mathcal {A}}={\mathfrak {G}}\{{\mathcal {B}}\}}$

${\displaystyle {\mathfrak {G}}\{{\mathcal {B}}\}={\mathcal {E}}+{\mathcal {B}}+({\mathcal {B}}\star {\mathcal {B}})+({\mathcal {B}}\star {\mathcal {B}}\star {\mathcal {B}})+\cdots }$

и снова, как и выше,

${\displaystyle A(z)={\frac {1}{1-B(z)}}}$

Набор

В маркированных структурах набор элементов соответствует точно последовательностям. Это отличается от немаркированного случая, где некоторые перестановки могут совпадать. Таким образом , для мы имеем ${\displaystyle k}$ ${\displaystyle k!}$ ${\displaystyle {\mathcal {A}}={\mathfrak {P}}\{{\mathcal {B}}\}}$

${\displaystyle A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k!}}=\exp(B(z))}$

Цикл

Циклы также проще, чем в случае без меток. Цикл длины соответствует различным последовательностям. Таким образом, для , мы имеем ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle {\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}}$

${\displaystyle A(z)=\sum _{k=0}^{\infty }{\frac {B(z)^{k}}{k}}=\ln \left({\frac {1}{1-B(z)}}\right).}$

Коробочный продукт

В маркированных структурах min-boxed product является вариацией исходного product, которая требует элемент в product с минимальной меткой. Аналогично, мы также можем определить max-boxed product, обозначенный как , тем же способом. Тогда мы имеем, ${\displaystyle {\mathcal {A}}_{\min }={\mathcal {B}}^{\square }\star {\mathcal {C}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}_{\max }={\mathcal {B}}^{\blacksquare }\star {\mathcal {C}}}$

${\displaystyle A_{\min }(z)=A_{\max }(z)=\int _{0}^{z}B'(t)C(t)\,dt.}$

или эквивалентно,

${\displaystyle A_{\min }'(t)=A_{\max }'(t)=B'(t)C(t).}$

Пример

Возрастающее дерево Кэли — это помеченное неплоское и корневое дерево, метки которого вдоль любой ветви, исходящей из корня, образуют возрастающую последовательность. Тогда пусть будет классом таких деревьев. Рекурсивная спецификация теперь ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}={\mathcal {Z}}^{\square }\star \operatorname {SET} ({\mathcal {L}}).}$

Другие элементарные конструкции

Операторы CYC _even , CYC _odd , SET _even и SET _odd представляют циклы четной и нечетной длины, а также множества четной и нечетной мощности .

Пример

Числа Стерлинга второго рода можно вывести и проанализировать с помощью структурного разложения

${\displaystyle \operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).}$

Разложение

${\displaystyle \operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))}$

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

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

• Комбинаторные виды

Ссылки

1. Фоата, Доминик ; Шютценбергер, Марсель-П. (1970). Теория геометрии полиномов Эйлера . Конспект лекций по математике. Том. 138. arXiv : math/0508232 . дои : 10.1007/BFb0060799 . ISBN 978-3-540-04927-2. {{cite book}}: |journal=проигнорировано ( помощь )
2. Бендер, Эдвард А.; Голдман, Джей Р. (1971). «Использование производящих функций в перечислительных целях». Indiana University Mathematics Journal . 20 (8): 753–764. doi : 10.1512/iumj.1971.20.20060 .
3. Джоял, Андре (1981). «Комбинированная теория серий форм». Достижения в математике . 42 : 1–82. дои : 10.1016/0001-8708(81)90052-9.

• Франсуа Бержерон, Жильбер Лабель, Пьер Леру, Теория особенных и комбинационных структур древесных пород , LaCIM, Монреаль (1994). Английская версия: Комбинаторные виды и древовидные структуры , Издательство Кембриджского университета (1998).
• Филипп Флажоле и Роберт Седжвик, Аналитическая комбинаторика , Cambridge University Press (2009). (доступно онлайн: http://algo.inria.fr/flajolet/Publications/book.pdf)
• Миха Хофри, Анализ алгоритмов: вычислительные методы и математические инструменты , Oxford University Press (1995).