Символьный метод (комбинаторика) - Symbolic method (combinatorics) - Wikipedia

Эта статья о методе аналитической комбинаторики. О методе теории инвариантов см. Символический метод.

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

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

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

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

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

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

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

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

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

где термин ${\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 .}$

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

куда ${\displaystyle {\mathfrak {A}}}$ («A» означает «атомы») - это набор простых чисел UFD ${\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 .}$

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

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

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

Позволять ${\displaystyle {\mathcal {C}}\in \mathbb {N} [{\mathfrak {A}}]}$ - класс комбинаторных структур. OGF ${\displaystyle F(z)}$ из ${\displaystyle {\mathcal {C}}(X)}$ куда Икс имеет OGF ${\displaystyle f(z)}$ и EGF ${\displaystyle G(z)}$ из ${\displaystyle {\mathcal {C}}(X)}$ куда Икс помечен EGF ${\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}.}$

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

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

Оператор последовательности SEQ

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

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

Оператор цикла CYC

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

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

Этот оператор вместе с оператором множества НАБОР, и их ограничения на определенные степени используются для вычисления статистика случайных перестановок. У этого оператора есть два полезных ограничения: на четные и нечетные циклы.

Обозначенный оператор четного цикла CYC_четное является

${\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_{странный}

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

Оператор multiset / set MSET/НАБОР

Сериал

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

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

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

Процедура

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

В этой статье мы будем следовать соглашению об использовании прописных букв сценария для обозначения комбинаторных классов и соответствующих простых букв для производящих функций (так что класс ${\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}}$

Товар

В товар двух комбинаторных классов ${\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}.}$

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

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

Multiset

В построение мультимножества, обозначенный ${\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}}}$

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

Прочие элементарные конструкции

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

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

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

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

Примеры

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

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

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

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

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

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

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

Формально спецификация набора комбинаторных классов ${\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}}$'s, а операторы - элементарные конструкции, перечисленные выше.

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

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

Товар в штучной упаковке

В помеченных структурах продукт в минимальной упаковке ${\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_четное, CYC_{странный},НАБОР_четное,и НАБОР_{странный}представляют циклы четной и нечетной длины, а также множества четной и нечетной мощности.

Пример

Числа Стирлинга второго рода могут быть получены и проанализированы с использованием структурной декомпозиции

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

Разложение

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

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

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

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

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

1. Бендер, E.A .; Гольдман, Дж. Р. (1971). «Перечислительное использование производящих функций». Indiana Univ. Математика. J. 20: 753–764.
2. Foata, D .; Шютценбергер М. (1970). "Геометрическая теория полиномов Эулериана". Конспект лекций по математике. 138.
3. Джоял, Андре (1981). "Une théorie combinatoire des séries formelles". Adv. Математика. 42: 1–82.

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