Обсуждение:Метод производящих функций — различия между версиями
Zevgeniy (обсуждение | вклад) м (UI) |
|||
(не показано 8 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | В комбинаторике, особенно в аналитической комбинаторике, [https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) | + | В комбинаторике, особенно в аналитической комбинаторике, [https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) символьный метод] - это метод подсчета [https://neerc.ifmo.ru/wiki/index.php?title=Комбинаторные_объекты комбинаторных объектов]. Он использует внутреннюю структуру объектов для получения формул их [[Производящая функция|производящих функций]]. Этот метод в основном связан с [https://en.wikipedia.org/wiki/Philippe_Flajolet Филиппом Флайоле] и подробно описан в части A его книги с [https://ru.wikipedia.org/wiki/Седжвик,_Роберт Робертом Седжвиком] "Аналитическая комбинаторика"<ref>[https://en.wikipedia.org/wiki/Analytic_Combinatorics "Аналитическая комбинаторика"]</ref>. |
Строка 12: | Строка 12: | ||
Считающей последовательностью называется последовательность <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}</tex>, где <tex dpi="130">a_i</tex> {{---}} количество объектов веса <tex dpi="130">i</tex>. | Считающей последовательностью называется последовательность <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}</tex>, где <tex dpi="130">a_i</tex> {{---}} количество объектов веса <tex dpi="130">i</tex>. | ||
}} | }} | ||
+ | |||
+ | Обозначим <tex dpi="350">[t_n]</tex> как оператор взятия <tex dpi="350">n</tex>-того коэффициента производящей функции. | ||
{{Определение | {{Определение | ||
Строка 105: | Строка 107: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Последовательностью | + | Последовательностью объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)</tex>. |
}} | }} | ||
Строка 306: | Строка 308: | ||
# В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе <tex dpi="350">A \star B</tex> будет лежать <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:3-4-5.png|50px]]<tex dpi="350">)</tex>, но не будет лежать <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:3-5-4.png|50px]]<tex dpi="350">)</tex>. | # В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе <tex dpi="350">A \star B</tex> будет лежать <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:3-4-5.png|50px]]<tex dpi="350">)</tex>, но не будет лежать <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:3-5-4.png|50px]]<tex dpi="350">)</tex>. | ||
− | <tex dpi="350">c_n=\sum_{k=0}^na_kb_{n-k}\binom{n}{k} | + | <tex dpi="350">c_n=\sum_{k=0}^na_kb_{n-k}\binom{n}{k}=\sum_{k=0}^na_kb_{n-k}\frac{n!}{k!(n-k)!}=n! \cdot \sum_{k=0}^n\frac{a_k}{k!}\frac{b_{n-k}}{(n-k)!}</tex> |
<tex dpi="350">C(t)=A(t) \cdot B(t)</tex> | <tex dpi="350">C(t)=A(t) \cdot B(t)</tex> | ||
Строка 376: | Строка 378: | ||
Можно рассматривать <tex dpi="350">Set(A)</tex> как композицию урны и <tex dpi="350">A</tex>, другими словами, можно вместо атомов в урне взять объекты класса <tex dpi="350">A</tex>. | Можно рассматривать <tex dpi="350">Set(A)</tex> как композицию урны и <tex dpi="350">A</tex>, другими словами, можно вместо атомов в урне взять объекты класса <tex dpi="350">A</tex>. | ||
− | == | + | ==Циклы== |
===Ограниченная конструкция=== | ===Ограниченная конструкция=== | ||
{{Определение | {{Определение | ||
− | |definition=Цикл <tex dpi="350">A=Cycle_k(B)</tex> {{---}} ориентированная циклическая последовательность из <tex dpi="350">k</tex> объектов класса <tex dpi="350">B</tex>. | + | |definition= |
− | + | Цикл <tex dpi="350">A=Cycle_k(B)</tex> {{---}} ориентированная циклическая последовательность из <tex dpi="350">k</tex> объектов класса <tex dpi="350">B</tex>. | |
− | + | Циклов нулевой длины <tex dpi="350">0</tex>, то есть, <tex dpi="350">c_0=0</tex>. | |
− | |||
}} | }} | ||
Текущая версия на 22:29, 20 августа 2020
В комбинаторике, особенно в аналитической комбинаторике, символьный метод - это метод подсчета комбинаторных объектов. Он использует внутреннюю структуру объектов для получения формул их производящих функций. Этот метод в основном связан с Филиппом Флайоле и подробно описан в части A его книги с Робертом Седжвиком "Аналитическая комбинаторика"[1].
Содержание
- 1 Базовые определения
- 2 Непомеченные комбинаторные объекты
- 3 Помеченные объекты
- 4 См.также
- 5 Примeчания
- 6 Источники информации
Базовые определения
Каждый комбинаторный объект состоит из атомов.
У атомов определен вес
. Вес объектов равен сумме весов составляющих его атомов.
Определение: |
Считающей последовательностью называется последовательность | , где — количество объектов веса .
Обозначим как оператор взятия -того коэффициента производящей функции.
Определение: |
Комбинаторным классом | называется множество комбинаторных объектов, обладающих каким-то свойством.
Непомеченные комбинаторные объекты
Введём атомы
и следующим образом:
Производящую функцию класса
обозначим , если — считающая последовательность этого класса.
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса .
Считающая последовательность: .
Производящая функция последовательности:
.
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса . .
Считающая последовательность: .
Производящая функция последовательности:
.Объединение комбинаторных классов
Определение: |
Объединением комбинаторных классов | и называется комбинаторный класс , состоящий из элементов обоих классов, причем равные объекты разных классов объявляются разными.
Целью этого уточнения является возможность работать только со считающими последовательностями и производящими функциями.
Пары комбинаторных классов (декартово произведение комбинаторных классов)
Определение: |
Парой комбинаторных классов | и называется комбинаторный класс .
Утверждение: |
Последовательности комбинаторных классов
Ограниченная конструкция
Определение: |
Последовательностью | объектов из называется .
Утверждение: |
Докажем по индукции: База .
Переход.
|
Неограниченная конструкция
Определение: |
Последовательностью объектов из | называется .
Утверждение: |
(Геометрическая прогрессия) |
Ограничение: (также можно встретить ). Этому есть как техническое, так и комбинаторное объяснение.
- Технически, если , то мы будем делить на отрицательное число; если , то на функцию, у которой свободный член , — что формализм производящих функций сделать не позволяет.
- Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
Примеры
- Последовательности из не менее, чем 3 объектов:
- Последовательности чётной длины:
Комбинаторный класс "Натуральные числа"
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
Считающая последовательность:
Класс "Натуральные числа" принято обозначать
. Считающая последовательность —Утверждение: |
Производящей функцией последовательности из явлется .Чтобы получить производящую функцию класса натуральных чисел, произведем сдвиг вправо по правилам работы со степенными рядами: |
Применение
разбиение натуральных чисел на слагаемые.
— упорядоченноеТогда производящая функция —
, потому что соответсвует ряду степеней , а — ряду .
Множества
Определение: |
Множества | — последовательности без повторений и порядка элементов.
Утверждение: |
Докажем по индукции по потенциальным элементам множеств .База
Переход Пусть верно для множества В множестве каждый элемент может либо присутствовать, либо отсутствовать, поэтому , докажем, что будет верно и для множества и , где . |
Пример
Мультимножества
Определение: |
Мультимножества | — последовательности с повторениями, но без порядка элементов.
Как и с
существует ограничение на : .Утверждение: |
Докажем по индукции по потенциальным элементам множеств .База
Переход Отличие от множеств в том, что здесь каждый элемент может присутствовать в любом неотрицательном количестве экземпляров, поэтому для каждого элемента беретсяПусть верно для мультимножества , докажем, что будет верно и для мультимножества и , где . |
Помеченные объекты
Как можно заметить, для некоторых операторов, например, экспоненциальная производящая функция.
и не существует замкнутых формул, поэтому их объекты удобнее обозначать как помеченные. С помеченными объектами используетсяНапомним, что если
— считающая последовательность, то производящие функции выражаются следующим образом:Обычная | |
Экспоненциальная |
Далее под производящей функцией будет подразумеваться и использоваться экспоненциальная производящая функция, потому что формулы с ней более просты в работе.
Свойства экспоненциальной производящей функции
Утверждение: |
Пусть — экспоненциальная производящая функция последовательности , тогда — экспоненциальная производящая функция последовательности |
Утверждение: |
Утверждение: |
Пусть [4] — экспоненциальная производящая функция последовательности , тогда — экспоненциальная производящая функция последовательности |
Утверждение: |
С точки зрения комбинаторики композиция производящих функций и означает подстановку вместо каждого возможного атома в всех объектов из класса .
|
Помеченные объекты
Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки; Если вес объекта равен
, то все атомы пронумерованы различными целыми числами от до .
Определение: |
Комбинаторным объектом
| называется комбинаторный объект, состоящий из одного атома веса .
Определение: |
Комбинаторным объектом
| называется комбинаторный объект, состоящий из одного атома веса .
Объединение комбинаторных классов
Одинаковых объектов также нет, мы ставим разные метки на одинаковые объекты из разных классов, чтобы сделать их различными.
Пары комбинаторных классов (декартово произведение комбинаторных классов)
Декартово произведение, определенное для непомеченных объектов, нам не даст корректный комбинаторный объект.
Тогда пара
будет иметь вес 5, но атомы не будут иметь различные пометки от 1 до 5.
Поэтому введем оператор
, который- Перебирает все пары из и .
- В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе
, но не будет лежать
.
будет лежать
Последовательности комбинаторных классов
Ограниченная конструкция
Последовательности длины
, как и в непомеченных комбинаторных объектах, формируются следующим образом:- Cоставляются все возможные последовательности из объектов из
- Перенумеруются всеми возможными способами.
Их принято обозначать
.-тый член выражается следующим образом:
Поэтому производящая функция —
Неограниченная конструкция
Определение
не изменилось.Утверждение: |
(Геометрическая прогрессия) |
Действует ограничение на
, как и на и в формализме непомеченных объектов.Пример
Перестановки
- Экспоненциальной производящей функцией является .
- Обычной производящей функции соответствует считающая последовательность , поэтому .
Урны
Кобинаторный класс "Урна" — множество, характеризующееся только количеством атомов в объекте, то есть элементов каждого веса —
, поэтому .Производящая функция этого класса —
.Множества
В формализме помеченных объектов
, потому что не бывает одинаковых элементов в множествах.Ограниченная конструкция
Определение: |
Ограниченным множеством | назовём множество из объектов (порядок не важен).
Рассмотрим и разобьем последовательности в на классы эквивалентности по признаку равенства множеств элементов в них.
Каждому биективно соответствует последовательностей в , потому что все объекты различны.
Неограниченная конструкция
— множества объектов (порядок не важен).
Ограничение
также действует.
Можно рассматривать
как композицию урны и , другими словами, можно вместо атомов в урне взять объекты класса .Циклы
Ограниченная конструкция
Определение: |
Цикл | — ориентированная циклическая последовательность из объектов класса . Циклов нулевой длины , то есть, .
Утверждение: |
Каждому циклу циклические перестановки элементов цикла). длины биективно соответствует упорядоченных последовательностей ( |
Поэтому
Значит, экспоненциальная производящая функция циклов —
.Неограниченная конструкция
Определение: |
Циклы | .
(Разложение натурального логарифма в ряд Тейлора)
См.также
- Конструирование комбинаторных объектов и их подсчёт
- Функция Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Каталана
- Генерация комбинаторных объектов в лексикографическом порядке
- Подсчет деревьев