Обычные и экспоненциальные производящие функции

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

Definition

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

Scope

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

Core questions

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

Key concepts

• Обычная производящая функция
• Экспоненциальная производящая функция
• Формальный степенной ряд
• Свертка и правило произведения
• Символический метод
• Размеченные и неразмеченные структуры

Key theories

Символический метод

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

Правило произведения для производящих функций

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

Clinical relevance

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

History

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

Key figures

• Philippe Flajolet
• Robert Sedgewick
• Richard P. Stanley

Seminal works

• flajolet2009
• stanley2011

Frequently asked questions

Когда предпочтительна экспоненциальная производящая функция?

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

Имеет ли переменная в производящей функции какое-либо значение?

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