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

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

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

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

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

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

Рассмотрим задачу распределения объектов, заданных производящей функцией, в набор из 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!}}.