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

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

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

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

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

${ Displaystyle Z (G) (е (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} / ГРАММ)}$

куда ${ 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 {и}} 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 + сумма _ {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) = сумма _ {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) = сумма _ {к 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 М (е (г), у) = сумма _ {п GEQ 0} у ^ {п} Z (S_ {п}) (е (г), е (г ^ {2}), ldots, f (z ^ {n}))}$

так что

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

Оценка ${ Displaystyle М (е (г), 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) = ехр влево ( сумма _ { 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 А (г)}$).

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

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

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

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

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

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

С немаркированными структурами обычная производящая функция (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}} + { бета }),}$

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

${ Displaystyle { begin {align} 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 {align}}}$

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

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

где, как и в приведенной выше конструкции множества, разложим ${ Displaystyle пер (1-я ^ {п})}$, поменять местами суммы и подставить вместо 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 фи (к)}$ это Функция Эйлера )
${ Displaystyle { mathcal {A}} = Theta { mathcal {B}}}$	${ Displaystyle А (г) = г { гидроразрыва {d} {dz}} В (г)}$
${ Displaystyle { mathcal {A}} = { mathcal {B}} circ { mathcal {C}}}$	${ Displaystyle А (г) = В (С (г))}$

Примеры

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

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

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

${ Displaystyle G (z) = { гидроразрыва {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}} _ {я}}$'s, а операторы - элементарные конструкции, перечисленные выше.

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

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

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

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

С помеченными структурами экспоненциальная производящая функция (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 ( альфа)}$ хорошо обозначен. Затем мы определяем маркированный продукт для двух объектов. ${ displaystyle alpha}$ и ${ displaystyle beta}$ в качестве

${ displaystyle alpha star beta = {( alpha ', beta'): ( alpha ', beta') { text {хорошо помечен,}} 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}}} ( альфа звезда бета).}$

EGF можно получить, отметив, что для объектов размера ${ displaystyle k}$ и ${ displaystyle n-k}$, Существуют ${ displaystyle {n select 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 А (г) = { гидроразрыва {1} {1-В (г)}}}$

Набор

В помеченных структурах набор ${ 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}}))}$

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

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

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

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

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