Обсуждение:Метод производящих функций — различия между версиями
Zevgeniy (обсуждение | вклад) м (typo) |
Zevgeniy (обсуждение | вклад) м (typo) |
||
Строка 345: | Строка 345: | ||
Каждому <tex dpi="350">Set_k(B)</tex> [[Отображения|биективно]] соответствует <tex dpi="350">k!</tex> последовательностей в <tex dpi="350">Seq_k(B)</tex>, потому что все объекты различны. | Каждому <tex dpi="350">Set_k(B)</tex> [[Отображения|биективно]] соответствует <tex dpi="350">k!</tex> последовательностей в <tex dpi="350">Seq_k(B)</tex>, потому что все объекты различны. | ||
− | <tex dpi="350">Set_k(B) | + | <tex dpi="350">Set_k(B)\cdot k!=Seq_k(B)</tex> |
<tex dpi="350">Set_k(B)(t)=A(t)=\frac{\left ( B \left ( s \right ) \right )^k}{k!}</tex> | <tex dpi="350">Set_k(B)(t)=A(t)=\frac{\left ( B \left ( s \right ) \right )^k}{k!}</tex> |
Версия 01:31, 25 июня 2020
В комбинаторике, особенно в аналитической комбинаторике, символический метод - это метод подсчета комбинаторных объектов. Он использует внутреннюю структуру объектов для получения формул их производящих функций. Этот метод в основном связан с Филиппом Флайоле и подробно описан в части A его книги с Робертом Седжвиком "Аналитическая комбинаторика"[1].
Содержание
- 1 Базовые определения
- 2 Непомеченные комбинаторные объекты
- 3 Помеченные объекты
- 3.1 Свойства экспоненциальной производящей функции
- 3.2 Помеченные объекты
- 3.3 Объединение комбинаторных классов
- 3.4 Пары комбинаторных классов (декартово произведение комбинаторных классов)
- 3.5 Последовательности комбинаторных классов
- 3.6 Урны
- 3.7 Множества
- 3.8 Циклы
- 3.9 См.также
- 3.10 Примeчания
- 3.11 Источники информации
Базовые определения
Каждый комбинаторный объект состоит из атомов.
У атомов определен вес
. Вес объектов равен сумме весов составляющих его атомов.
Определение: |
Считающей последовательностью называется последовательность | , где — количество объектов веса .
Определение: |
Комбинаторным классом множество комбинаторных объектов, обладающих каким-то свойством. | называется
Непомеченные комбинаторные объекты
Производящую функцию класса
обозначим .
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса .
Считающая последовательность: .
Производящая функция последовательности: .
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса . .
Считающая последовательность: .
Производящая функция последовательности: .
Объединение комбинаторных классов
Определение: |
Объединением комбинаторных классов | и называется комбинаторный класс .
При объединении комбинаторных классов одинаковые объекты разных классов считаются разными. Это делается так, чтобы не рассматривать внутреннюю структуру классов, а работать только со считающими последовательностями и производящими функциями.
Пары комбинаторных классов (декартово произведение комбинаторных классов)
Определение: |
Парой комбинаторных классов | и называется комбинаторный класс .
Утверждение: |
Верно, потому что коэффициенты производящей функции описываются равенством выше |
Последовательности комбинаторных классов
Ограниченная конструкция
Определение: |
Последовательностью | объектов из называется .
Утверждение: |
Докажем по индукции: База .
Переход.
|
Неограниченная конструкция
Определение: |
Последовательностью (всех возможных длин) объектов из | называется .
Утверждение: |
Геометрическая прогрессия) | (
Ограничение: . Этому есть как техническое, так и комбинаторное объяснение.
- Технически, если , то мы будем делить на отрицательное число; если , то на функцию, у которой свободный член , — что формализм производящих функций сделать не позволяет.
- Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
Примеры
- Последовательночти из не менее 3 объектов:
- Последовательности чётной длины:
Комбинаторный объект "Натуральные числа"
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
Считающая последовательность:
— упорядоченное
Множества
Множества
— последовательности без повторений и порядка элементов.Пример
Мультимножества
Мультимножества
— последовательности с повторениями, но без порядка элементов.Как и с
существует ограничение на : .
Циклы
Ограниченная конструкция
Определение: |
Цикл | — ориентированная циклическая последовательность из объектов класса .
Неограниченная конструкция
Определение: |
Циклы | .
Утверждение: |
, где — |
Помеченные объекты
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, — помеченные графы. С помеченными объектами используется экспоненциальная производящая функция.
Напомню, что если
— считающая последовательность, то производящие функции выражаются следующим образом:Обычная | |
Экспоненциальная |
Свойства экспоненциальной производящей функции
Утверждение: |
Пусть — экспоненциальная производящая функция последовательности , тогда — экспоненциальная производящая функция последовательности |
Утверждение: |
Утверждение: |
Пусть — экспоненциальная производящая функция последовательности , тогда — экспоненциальная производящая функция последовательности |
Утверждение: |
С точки зрения комбинаторики композиция производящих функций и означает подстановку вместо каждого возможного атома в всех объектов из класса .
|
Помеченные объекты
Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки, а именно — если вес объекта
, то все атомы пронумерованы различными целыми числами от до .
Далее под производящей функцией будет подразумеваться экспоненциальная производящая функция.
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса .
Производящая функция последовательности: .
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса . .
Производящая функция последовательности: .
Объединение комбинаторных классов
Одинаковых объектов также нет, мы ставим разные метки на одинаковые объекты из разных классов, чтобы сделать их различными.
Пары комбинаторных классов (декартово произведение комбинаторных классов)
Напрямую декартово произведение нам не даст корректный комбинаторный объект.
Тогда пара
будет иметь вес 5, но атомы не будут иметь различные пометки от 1 до 5.
Поэтому введем опреатор
, который- Перебирает все пары из и .
- В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом в классе
, но не будет
.
будет
Последовательности комбинаторных классов
Ограниченная конструкция
Последовательности длины
, как и в непомеченных комбинаторных объектах, формируются следующим образом:- Мы составляем все возможные последовательности из объектов из
- Затем всеми возможными способами их перенумеруем.
Обозначаются
.
Неограниченная конструкция
Определение
и соответствующая производящая функция не изменились.Действует ограничение на
как и и в в мире непомеченных объектов.Пример
- Обычной производящей функции соответствует считающая последовательность , поэтому .
Урны
Урна характеризуется только количеством атомов в ней, поэтому
Множества
В помеченном мире
, потому что не бывает одинаковых элементов в множествах.Ограниченная конструкция
— множество из объектов (порядок не важен).
Каждому биективно соответствует последовательностей в , потому что все объекты различны.
Неограниченная конструкция
— множества объектов (порядок не важен).
Ограничение
также действует.
— урна, где вместо атомов взяли объекты класса .
Циклы
Ограниченная конструкция
Утверждение: |
Циклов -вой длины . |
Утверждение: |
Каждому циклу циклические перестановки элементов цикла). длины биективно соответствует упорядоченных последовательностей ( |
Неограниченная конструкция
См.также
- Конструирование комбинаторных объектов и их подсчёт
- Функция Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Каталана
- Генерация комбинаторных объектов в лексикографическом порядке
- Подсчет деревьев