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

Эта статья о методе аналитической комбинаторики. Чтобы узнать о методе теории инвариантов, см. Символический метод .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фундаментальная теорема Флажоле – Седжвика.

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

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

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

и

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

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

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

Оператор последовательности ПОСЛЕДОВАТЕЛЬНОСТЬ

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

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

и представляет последовательности, т.е. слоты не переставляются и существует ровно одна пустая последовательность. У нас есть

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

и

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

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

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

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

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

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

или

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

и

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

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

Помеченный оператор четного цикла CYC _Even равен

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

что дает

$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 _{нечетный}

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

дается

$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)}}.$

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

Серия

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

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

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

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

так что

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

Оценка $M(f(z),1)$ мы получаем

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

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

$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 . Это связано с тем, что в помеченном случае нет мультимножеств (метки различают составляющие составного комбинаторного класса), тогда как в непомеченном случае есть мультимножества и множества, причем последние задаются формулой

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

Процедура

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

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

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

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

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

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

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

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

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

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

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

Продукт

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

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

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

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

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

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

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

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

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

Набор

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

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

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

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

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

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

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

Мультисет

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

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

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

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

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

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

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

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

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

Строительство	Генерирующая функция
${\mathcal {A}}={\mathfrak {C}}\{{\mathcal {B}}\}$	$A(z)=\sum _{k=1}^{\infty }{\frac {\phi (k)}{k}}\ln {\frac {1}{1-B(z^{k})}}$ (где $\phi (k)$ — Эйлера функция
${\mathcal {A}}=\Theta {\mathcal {B}}$	$A(z)=z{\frac {d}{dz}}B(z)$
${\mathcal {A}}={\mathcal {B}}\circ {\mathcal {C}}$	$A(z)=B(C(z))$

Примеры

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

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

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

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

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

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

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

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

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

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

OGF ${\mathcal {I}}$ тогда

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

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

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

OGF ${\mathcal {P}}$ является

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

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

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

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

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

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

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

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

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

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

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

Продукт

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

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

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

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

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

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

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

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

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

$A(z)\cdot B(z).$

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

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

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

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

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

Набор

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

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

Цикл

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

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

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

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

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

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

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

Пример

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

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

Операторы CYC _даже ,CYC _{странный} ,НАСТРОЙКА _даже , и SET _{нечетный} представляют циклы четной и нечетной длины, а также множества четной и нечетной мощности.

Пример

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

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

Разложение

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

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

См. также

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

Ссылки

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