Обсуждение:Метод производящих функций
В комбинаторике, особенно в аналитической комбинаторике, символический метод - это метод подсчета комбинаторных объектов. Он использует внутреннюю структуру объектов для получения формул их производящих функций. Этот метод в основном связан с Филиппом Флайоле и подробно описан в части A его книги с Робертом Седжвиком "Аналитическая комбинаторика"[1].
Базовые определения
Каждый комбинаторный объект состоит из атомов.
У атомов определен вес
. Вес объектов равен сумме весов составляющих его атомов.
Определение: |
Считающей последовательностью называется последовательность | , где — количество объектов веса .
Определение: |
Комбинаторным классом множество комбинаторных объектов, обладающих каким-то свойством. | называется
Непомеченные комбинаторные объекты
Введём атомы
и следующим образом:
Производящую функцию класса
обозначим , если — считающая последовательность этого класса.
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса .
Считающая последовательность: .
Производящая функция последовательности:
.
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса . .
Считающая последовательность: .
Производящая функция последовательности: .
Объединение комбинаторных классов
Определение: |
Объединением комбинаторных классов | и называется комбинаторный класс , состоящий из элементов обоих классов, причем равные объекты разных подмножеств объявляются разными.
Целью этого уточнения является возможность работать только со считающими последовательностями и производящими функциями.
Пары комбинаторных классов (декартово произведение комбинаторных классов)
Определение: |
Парой комбинаторных классов | и называется комбинаторный класс .
Утверждение: |
Последовательности комбинаторных классов
Ограниченная конструкция
Определение: |
Последовательностью | объектов из называется .
Утверждение: |
Докажем по индукции: База .
Переход.
|
Неограниченная конструкция
Определение: |
Последовательностью, или базовой последовательностью, объектов из | называется .
Утверждение: |
Геометрическая прогрессия) | (
Ограничение: (также можно встретить ). Этому есть как техническое, так и комбинаторное объяснение.
- Технически, если , то мы будем делить на отрицательное число; если , то на функцию, у которой свободный член , — что формализм производящих функций сделать не позволяет.
- Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
Примеры
- Последовательности из не менее, чем 3 объектов:
- Последовательности чётной длины:
Комбинаторный класс "Натуральные числа"
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
Считающая последовательность:
Класс "Натуральные числа" принято обозначать
.
Утверждение: |
Производящей функцией последовательности из явлется .Чтобы получить производящую функцию класса натуральных чисел, произведем сдвиг вправо по правилам работы со степенными рядами: |
Применение
— упорядоченное
Множества
Определение: |
Множества | — последовательности без повторений и порядка элементов.
Утверждение: |
Докажем по индукции по потенциальным элементам множеств .База
Переход Пусть верно для множества В множестве каждый элемент может либо присутствовать, либо отсутствовать, поэтому , докажем, что будет верно и для множества и , где . |
Пример
Мультимножества
Определение: |
Мультимножества | — последовательности с повторениями, но без порядка элементов.
Как и с
существует ограничение на : .Утверждение: |
Докажем по индукции по потенциальным элементам множеств .База
Переход Отличие от множеств в том, что здесь каждый элемент может присутствовать в любом неотрицательном количестве экземпляров, поэтому для каждого элемента беретсяПусть верно для мультимножества , докажем, что будет верно и для мультимножества и , где . |
Циклы
Ограниченная конструкция
Определение: |
Цикл | — ориентированная циклическая последовательность из объектов класса .
Неограниченная конструкция
Определение: |
Циклы | .
Утверждение: |
почему? функция Эйлера. , где — |
Помеченные объекты
Как можно заметить, для некоторых операторов, например, экспоненциальная производящая функция.
и не существует замкнутых формул, поэтому их объекты удобнее обозначать как помеченные. С помеченными объектами используетсяНапомним, что если
— считающая последовательность, то производящие функции выражаются следующим образом:Обычная | |
Экспоненциальная |
Далее под производящей функцией будет подразумеваться экспоненциальная производящая функция.
Свойства экспоненциальной производящей функции
Утверждение: |
Пусть — экспоненциальная производящая функция последовательности , тогда — экспоненциальная производящая функция последовательности |
Утверждение: |
Утверждение: |
Пусть — экспоненциальная производящая функция последовательности , тогда — экспоненциальная производящая функция последовательности |
Утверждение: |
С точки зрения комбинаторики композиция производящих функций и означает подстановку вместо каждого возможного атома в всех объектов из класса .
|
Помеченные объекты
Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки; Если вес объекта равен
, то все атомы пронумерованы различными целыми числами от до .
Определение: |
Комбинаторным объектом
| называется комбинаторный объект, состоящий из одного атома веса .
Определение: |
Комбинаторным объектом
| называется комбинаторный объект, состоящий из одного атома веса .
Объединение комбинаторных классов
Одинаковых объектов также нет, мы ставим разные метки на одинаковые объекты из разных классов, чтобы сделать их различными.
Пары комбинаторных классов (декартово произведение комбинаторных классов)
Декартово произведение, определенное для непомеченных объектов, нам не даст корректный комбинаторный объект.
Тогда пара
будет иметь вес 5, но атомы не будут иметь различные пометки от 1 до 5.
Поэтому введем оператор
, который- Перебирает все пары из и .
- В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе
, но не будет лежать
.
будет лежать
Последовательности комбинаторных классов
Ограниченная конструкция
Последовательности длины
, как и в непомеченных комбинаторных объектах, формируются следующим образом:- Cоставляются все возможные последовательности из объектов из
- Затем они всеми возможными способами их перенумеруются.
Их принято обозначать
.-тый член выражается следующим образом:
Поэтому производящая функция —
Неограниченная конструкция
Определение
и соответствующая производящая функция не изменились.Действует ограничение на
, как и на и в формализме непомеченных объектов.Пример
- Экспоненциальной производящей функцией является .
- Обычной производящей функции соответствует считающая последовательность , поэтому .
Урны
Кобинаторный класс "Урна" — множество, характеризующееся только количеством атомов в объекте, то есть элементов каждого веса —
, поэтому .Производящая функция этого класса —
.Множества
В помеченном мире
, потому что не бывает одинаковых элементов в множествах.Ограниченная конструкция
— множество из объектов (порядок не важен).
что это такое
Каждому биективно соответствует последовательностей в , потому что все объекты различны.
Неограниченная конструкция
— множества объектов (порядок не важен).
Ограничение
также действует.
— урна, где вместо атомов взяли объекты класса . напиши чуть более развернуто, а не предложениями в три слова
Циклы
Ограниченная конструкция
Утверждение: |
Циклов нулевой длины . То есть, |
Утверждение: |
Каждому циклу циклические перестановки элементов цикла). длины биективно соответствует упорядоченных последовательностей ( |
Поэтому
Значит, экспоненциальная производящая функция циклов —
.Неограниченная конструкция
См.также
- Конструирование комбинаторных объектов и их подсчёт
- Функция Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Каталана
- Генерация комбинаторных объектов в лексикографическом порядке
- Подсчет деревьев