В комбинаторике , то символический метод представляет собой метод подсчета комбинаторных объектов . Он использует внутреннюю структуру объектов для вывода формул для их производящих функций . Этот метод в основном связан с Филипп Фладжолет и подробно описана в Части А его книги с Седжвик , Analytic комбинаторике , в то время как остальная часть книги объясняет , как использовать комплексный анализ для того , чтобы получить асимптотические и вероятностные результаты на соответствующих производящих функций.
В течение двух столетий производящие функции появлялись через соответствующие повторения их коэффициентов (как можно увидеть в основополагающих работах Бернулли [ необходимо устранение неоднозначности ] , Эйлера , Артура Кейли , Шредера , Рамануджана , Риордана , Кнута , Контета , так далее.). Затем постепенно стало понятно, что производящие функции захватывают многие другие грани исходных дискретных комбинаторных объектов, и что это можно сделать более прямым формальным способом: рекурсивная природа некоторых комбинаторных структур преобразуется через некоторые изоморфизмы в заслуживающие внимания тождества. на соответствующие производящие функции. После работ Полны , дальнейшие успехи были , таким образом , сделать в этом духе в 1970 - х годах с родовым использованием языков для определения комбинаторных классов и их производящих функций, которые содержатся в работах Фоата и Шютценберже [1] на перестановках, Бендеры и Голдман на префабах , [2] и Джоял о комбинаторных видах . [3]
Обратите внимание, что этот символический метод перечисления не имеет отношения к «символическому методу Блиссара», который является просто еще одним старым названием теневого исчисления .
Символьный метод в комбинаторике составляет первый шаг многих анализов комбинаторных структур, которые затем могут привести к схемам быстрых вычислений, к асимптотическим свойствам и предельным законам , к случайной генерации , причем все они подходят для автоматизации с помощью компьютерной алгебры .
Классы комбинаторных структур
Рассмотрим задачу распределения объектов, заданных производящей функцией, в набор из n слотов, где группа перестановок G степени n действует на слоты, чтобы создать отношение эквивалентности конфигураций заполненных слотов, и спросить о производящей функции конфигураций с помощью вес конфигураций по отношению к этому отношению эквивалентности, где вес конфигурации - это сумма весов объектов в слотах. Сначала мы объясним, как решить эту проблему в помеченном и немаркированном случаях, и используем решение, чтобы мотивировать создание классов комбинаторных структур .
Перечисление Полиа теорема решает эту проблему в непомеченном случае. Пусть f ( z ) - обычная производящая функция (OGF) объектов, тогда OGF конфигураций задается подставляемым индексом цикла
В помеченном случае мы используем экспоненциальную производящую функцию (EGF) g ( z ) объектов и применяем теорему о помеченном перечислении , которая гласит, что EGF конфигураций задается формулой
Мы можем перечислять конфигурации заполненных слотов, используя либо ПЭТ в немаркированном случае, либо теорему о маркированном перечислении в помеченном случае. Теперь мы спрашиваем о производящей функции конфигураций, получаемых, когда имеется более одного набора слотов, с группой перестановок, действующей на каждом. Ясно, что орбиты не пересекаются, и мы можем добавить соответствующие производящие функции. Предположим, например, что мы хотим , чтобы перечислить немаркированные последовательности длиной два или три ряда объектов , содержащихся в множестве X . Есть два набора слотов: первый содержит два слота, а второй - три слота. Группа, действующая на первом наборе, есть, а на втором слоте . Мы представим это следующим формальным степенным рядом в X :
где термин используется для обозначения множества орбит относительно G и, что очевидным образом обозначает процесс распределения объектов из X с повторением в n слотов. Точно так же, рассмотрим меченого задачу создания циклов произвольной длины из набора меченых объектов X . Это дает следующую серию действий циклических групп:
Ясно, что мы можем придать смысл любой такой степенной серии факторов (орбит) относительно групп перестановок, где мы ограничиваем группы степени n классами сопряженности симметрической группы , которые образуют уникальную область факторизации. (Орбиты относительно двух групп из одного и того же класса сопряженности изоморфны.) Это мотивирует следующее определение.
Класс комбинаторных структур представляет собой формальный ряд
где («A» означает «атомы») - это набор простых чисел UFD. а также
Далее мы немного упростим наши обозначения и напишем, например,
для упомянутых выше классов.
Основная теорема Флажоле – Седжвика.
Теорема в теории символической комбинаторики Флажоле – Седжвика рассматривает проблему перечисления помеченных и немеченых комбинаторных классов посредством создания символических операторов, которые позволяют переводить уравнения, включающие комбинаторные структуры, напрямую (и автоматически) в уравнения в производящих функциях. этих структур.
Позволять - класс комбинаторных структур. OGF из где X имеет OGF и EGF из где X помечен EGF даны
а также
В отмеченном случае у нас есть дополнительное требование, чтобы X не содержал элементов нулевого размера. Иногда бывает удобно добавить один вдля обозначения наличия одной копии пустого набора. Можно придать значение обоим (наиболее распространенный пример - немаркированные наборы) и Чтобы доказать теорему, просто примените ПЭТ (теорему о перечислении Полиа) и теорему о помеченном перечислении.
Сила этой теоремы заключается в том, что она позволяет строить операторы над производящими функциями, представляющими комбинаторные классы. Таким образом, структурное уравнение между комбинаторными классами напрямую преобразуется в уравнение в соответствующих производящих функциях. Более того, в отмеченном случае из формулы видно, что мы можем заменитьатомом z и вычислить получившийся оператор, который затем может быть применен к EGF. Приступим к построению наиболее важных операторов. Читатель может пожелать сравнить с данными на странице указателя циклов .
Оператор последовательности SEQ
Этот оператор соответствует классу
и представляет собой последовательности, т. е. слоты не переставляются и имеется ровно одна пустая последовательность. У нас есть
а также
Оператор цикла CYC
Этот оператор соответствует классу
т.е. циклы, содержащие хотя бы один объект. У нас есть
или же
а также
Этот оператор вместе с оператором множества SET и их ограничениями до определенных степеней используются для вычисления статистики случайных перестановок . У этого оператора есть два полезных ограничения: на четные и нечетные циклы.
Обозначенный оператор четного цикла CYC even имеет вид
который дает
Отсюда следует, что помеченный оператор нечетного цикла CYC odd
дан кем-то
Оператор multiset / set MSET / SET
Сериал
т.е. симметричная группа применяется к прорезям. Это создает мультимножества в немаркированном случае и наборы в помеченном случае (в помеченном случае нет мультимножеств, потому что метки различают несколько экземпляров одного и того же объекта из набора, помещаемого в разные слоты). Мы включаем пустой набор как в помеченный, так и в немаркированный случай.
Случай без метки выполняется с помощью функции
чтобы
Оценка мы получаем
Для помеченного случая имеем
В помеченном случае мы обозначаем оператор как SET , а в немаркированном случае - через MSET . Это связано с тем, что в помеченном случае нет мультимножеств (метки различают составляющие составного комбинаторного класса), тогда как в немаркированном случае есть мультимножества и множества, причем последние задаются как
Процедура
Обычно начинают с нейтрального класса. , содержащий единственный объект размера 0 ( нейтральный объект , часто обозначаемый), и один или несколько атомарных классов , каждый из которых содержит один объект размера 1. Затем теоретико-множественные отношения, включающие различные простые операции, такие как непересекающиеся объединения , продукты , множества , последовательности и мультимножества, определяют более сложные классы в терминах уже определенных классов. Эти отношения могут быть рекурсивными . Изящество символической комбинаторики состоит в том, что теоретико-множественные или символические отношения переводятся непосредственно в алгебраические отношения, включающие производящие функции.
В этой статье мы будем следовать соглашению об использовании прописных букв сценария для обозначения комбинаторных классов и соответствующих простых букв для производящих функций (так что класс имеет производящую функцию ).
В символьной комбинаторике обычно используются два типа производящих функций: обычные производящие функции , используемые для комбинаторных классов немаркированных объектов, и экспоненциальные производящие функции , используемые для классов помеченных объектов.
Нетривиально показать, что производящие функции (обычные или экспоненциальные) для а также находятся а также , соответственно. Несвязное объединение также простое - для непересекающихся множеств а также , подразумевает . Отношения, соответствующие другим операциям, зависят от того, говорим ли мы о помеченных или немеченых структурах (и обычных или экспоненциальных производящих функциях).
Комбинаторная сумма
Ограничение профсоюзов несвязанными союзами является важным; однако в формальной спецификации символической комбинаторики слишком сложно отслеживать, какие множества не пересекаются. Вместо этого мы используем конструкцию, которая гарантирует отсутствие пересечения ( однако будьте осторожны; это также влияет на семантику операции ). При определении комбинаторной суммы двух множеств а также , мы отмечаем элементы каждого набора отдельным маркером, например для членов а также для членов . Комбинаторная сумма тогда равна:
Это операция, которая формально соответствует сложению.
Немаркированные конструкции
Для немаркированных структур используется обычная производящая функция (OGF). OGF последовательности определяется как
Продукт
Продукт двух комбинаторных классов а также задается путем определения размера упорядоченной пары как суммы размеров элементов в паре. Таким образом, мы имеем для а также , . Это должно быть довольно интуитивное определение. Заметим, что количество элементов вразмера п является
Используя определение OGF и некоторую элементарную алгебру, мы можем показать, что
- подразумевает
Последовательность
Построение последовательности , обозначаемое определяется как
Другими словами, последовательность - это нейтральный элемент или элемент , или упорядоченная пара, упорядоченная тройка и т. д. Это приводит к соотношению
Набор
Множество (или Powerset ) строительство , обозначается определяется как
что приводит к соотношению
где расширение
использовался для перехода от строки 4 к строке 5.
Мультимножество
Конструкция мультимножества , обозначеннаяявляется обобщением конструкции множества. В конструкции множества каждый элемент может встречаться ноль или один раз. В мультимножестве каждый элемент может появляться произвольное количество раз. Следовательно,
Это приводит к соотношению
где, как и в приведенной выше конструкции множества, разложим , поменять местами суммы и подставить вместо OGF .
Прочие элементарные конструкции
Другими важными элементарными конструкциями являются:
- построение цикла (), как и последовательности, за исключением того, что циклические вращения не считаются различными
- указывая (), в котором каждый член дополняется нейтральным (нулевым размером) указателем на один из его атомов
- подстановка (), в котором каждый атом в члене заменяется членом .
Выводы этих конструкций слишком сложны, чтобы их здесь можно было показать. Вот результаты:
Строительство | Производящая функция |
---|---|
(где - функция Эйлера ) | |
Примеры
Многие комбинаторные классы могут быть построены с использованием этих элементарных конструкций. Например, класс плоских деревьев (то есть деревьев, встроенных в плоскость, так что порядок поддеревьев имеет значение) определяется рекурсивным соотношением
Другими словами, дерево - это корневой узел размера 1 и последовательность поддеревьев. Это дает
мы решаем относительно G ( z ), умножая получить
вычитая z и решая относительно G (z) по формуле корней квадратного уравнения, получаем
Другой пример (и классическая проблема комбинаторики) - целочисленные разбиения . Сначала определите класс натуральных чисел, где размер каждого целого числа является его значением:
OGF затем
Теперь определим набор разделов в виде
OGF является
К сожалению, закрытой формы для ; однако OGF можно использовать для вывода рекуррентного отношения или, используя более продвинутые методы аналитической комбинаторики, для вычисления асимптотического поведения счетной последовательности.
Спецификация и определяемые классы
Упомянутые выше элементарные конструкции позволяют определить понятие спецификации . Эти спецификации позволяют использовать набор рекурсивных уравнений с несколькими комбинаторными классами.
Формально спецификация набора комбинаторных классов это набор уравнения , где выражение, атомы которого и 's, а операторы которых являются элементарными конструкциями, перечисленными выше.
Класс комбинаторных структур называется конструктивным или определяемым, если он допускает спецификацию.
Например, множество деревьев, у которых глубина листьев четная (соответственно нечетная), может быть определена с помощью спецификации с двумя классами а также . Эти классы должны удовлетворять уравнению а также .
Помеченные конструкции
Объект слабо помечен, если каждый из его атомов имеет неотрицательную целочисленную метку, и каждая из этих меток различна. Объект ( строго или хорошо ) помечен , если, кроме того, эти метки содержат последовательные целые числа. Примечание: некоторые комбинаторные классы лучше всего задавать как помеченные структуры или немеченые структуры, но некоторые легко допускают обе спецификации. Хорошим примером помеченных структур является класс помеченных графов .
С помеченными структурами используется экспоненциальная производящая функция (EGF). EGF последовательности определяется как
Продукт
Для помеченных структур мы должны использовать другое определение продукта, чем для немаркированных структур. Фактически, если бы мы просто использовали декартово произведение, результирующие структуры даже не были бы хорошо помечены. Вместо этого мы используем так называемый маркированный продукт , обозначенный
Для пары а также , мы хотим объединить две структуры в единую структуру. Чтобы результат был хорошо промаркирован, необходимо изменить маркировку атомов в а также . Мы ограничим наше внимание перемаркировкой, которая соответствует порядку оригинальных ярлыков. Обратите внимание, что есть еще несколько способов сделать перемаркировку; таким образом, каждая пара элементов определяет не один элемент в продукте, а набор новых элементов. Детали этой конструкции можно найти на странице теоремы о помеченном перечислении .
Чтобы помочь этому развитию, давайте определим функцию, , который принимает в качестве аргумента (возможно, слабо) помеченный объект и перемаркирует свои атомы в последовательном порядке так, чтобы хорошо обозначен. Затем мы определяем помеченный продукт для двух объектов. а также в виде
Наконец, помеченный продукт двух классов а также является
EGF можно получить, отметив, что для объектов размера а также , Существуют способы сделать перемаркировку. Таким образом, общее количество объектов размером является
Это биномиальное соотношение свертки для членов эквивалентно умножению EGF,
Последовательность
Построение последовательности определяется аналогично немаркированному случаю:
и снова, как указано выше,
Набор
В помеченных структурах набор элементов соответствует точно последовательности. Это отличается от случая без метки, где некоторые из перестановок могут совпадать. Таким образом, для, у нас есть
Цикл
Циклы также проще, чем в случае без маркировки. Цикл длины соответствует различные последовательности. Таким образом, для, у нас есть
Товар в штучной упаковке
В помеченных структурах продукт в минимальной упаковке является разновидностью оригинального продукта, который требует элемента в продукте с минимальной этикеткой. Точно так же мы также можем определить продукт в максимальной упаковке, обозначенный кактаким же образом. Тогда у нас есть
или, что эквивалентно,
Пример
Растущее дерево Кэли - это помеченное неплоское дерево с корнем, метки которого вдоль любой ветви, идущей от корня, образуют возрастающую последовательность. Тогда пусть- класс таких деревьев. Рекурсивная спецификация теперь
Прочие элементарные конструкции
Операторы CYC даже , CYC нечетное , SET даже , и SET нечетным представляют циклы четных и нечетных длины, а также множества четной и нечетной мощности.
Пример
Числа Стирлинга второго рода могут быть получены и проанализированы с помощью структурной декомпозиции
Разложение
используется для изучения беззнаковых чисел Стирлинга первого рода и при выводе статистики случайных перестановок . Подробное рассмотрение экспоненциальных производящих функций, связанных с числами Стирлинга в символической комбинаторике, можно найти на странице, посвященной числам Стирлинга и экспоненциальным производящим функциям в символьной комбинаторике .
Смотрите также
- Комбинаторные виды
Рекомендации
- ^ Foata, D .; Шютценбергер М. (1970). "Теория геометрических полиномов Эулериана". Конспект лекций по математике . 138 .
- ^ Бендер, Э.А.; Гольдман, младший (1971). «Перечислительное использование производящих функций». Индиана Univ. Математика. Дж . 20 : 753–764.
- ^ Хоял, Андре (1981). "Une théorie combinatoire des séries formelles". Adv. Математика. 42 : 1–82.
- 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).