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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Позвольте быть класс комбинаторных структур. ОГФ из где Х имеет ОГФ и ЭФР из где Х помечен 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 не содержал элементов нулевого размера. Иногда бывает удобно добавить один, чтобы указать на наличие одной копии пустого набора. Можно присвоить значение обоим (наиболее распространенный пример - случай немаркированных множеств) и. Чтобы доказать теорему, просто примените ПЭТ (теорему о перечислении Полиа) и теорему о маркированном перечислении. ${\ Displaystyle G (z)}$${\ Displaystyle {\ mathcal {C}} \ in \ mathbb {Z} [{\ mathfrak {A}}]}$${\ displaystyle {\ mathcal {C}} \ in \ mathbb {Q} [{\ mathfrak {A}}].}$

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

Оператор последовательности 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) = \ сумма _ {п \ 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)}}.}$

Этот оператор вместе с оператором множества 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)}}.}.}$

Оператор мультимножества / набора MSET / SET

Сериал

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

В помеченном случае мы обозначаем оператор как 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 А (г)}$

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

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

Продукт

Продукт из двух комбинаторных классов и задаются путем определения размера упорядоченной пары как сумма размеров элементов в паре. Таким образом , мы имеем для и , . Это должно быть довольно интуитивное определение. Теперь отметим, что количество элементов размера 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_ {nk}.}$

Используя определение 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.

Мультимножество

Мультимножеством конструкция , обозначенная является обобщением множества строительства. В конструкции множества каждый элемент может встречаться ноль или один раз. В мультимножестве каждый элемент может появляться произвольное количество раз. Следовательно, ${\ 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}}}$

где, аналогично приведенной выше конструкции набора, мы расширяем, меняем местами суммы и заменяем OGF of . ${\ Displaystyle \ пер (1-я ^ {п})}$${\ 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)}}}$

мы решаем для 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}} \}.}$

ОГФ из IS ${\ displaystyle {\ mathcal {P}}}$

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

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

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

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

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

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

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

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

Это биномиальное соотношение свертки для членов эквивалентно умножению 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 _{нечетное} , SET _даже , и SET _{нечетным} представляют циклы четных и нечетных длины, а также множества четной и нечетной мощности.

Пример

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

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

Разложение

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

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

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

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

использованная литература

• François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire des structure arborescentes , LaCIM, Montréal (1994). Английская версия: Комбинаторные виды и древовидные структуры , Cambridge University Press (1998).
• Филипп Флажолет и Роберт Седжвик, Аналитическая комбинаторика , Cambridge University Press (2009). (доступно в Интернете: http://algo.inria.fr/flajolet/Publications/book.pdf )
• Миха Хофри, Анализ алгоритмов: вычислительные методы и математические инструменты , Oxford University Press (1995).