Обсуждение:Метод производящих функций — различия между версиями
Zevgeniy (обсуждение | вклад) м (UI) |
|||
(не показано 26 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | В | + | В комбинаторике, особенно в аналитической комбинаторике, [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>-того коэффициента производящей функции. | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Комбинаторным классом <tex dpi="130">A</tex> называется | + | Комбинаторным классом <tex dpi="130">A</tex> называется множество комбинаторных объектов, обладающих каким-то свойством. |
}} | }} | ||
+ | |||
=Непомеченные комбинаторные объекты= | =Непомеченные комбинаторные объекты= | ||
Строка 61: | Строка 64: | ||
<tex dpi="350">C(t)=\left ( \sum_{i=0}^{\infty}a_i \cdot t^i \right ) + \left ( \sum_{i=0}^{\infty}b_i \cdot t^i \right ) = \sum_{i=0}^{\infty}(a_i + b_i)\cdot t^i =A(t)+B(t)</tex> | <tex dpi="350">C(t)=\left ( \sum_{i=0}^{\infty}a_i \cdot t^i \right ) + \left ( \sum_{i=0}^{\infty}b_i \cdot t^i \right ) = \sum_{i=0}^{\infty}(a_i + b_i)\cdot t^i =A(t)+B(t)</tex> | ||
− | ==Пары комбинаторных классов ( | + | ==Пары комбинаторных классов (декартово произведение комбинаторных классов)== |
{{Определение | {{Определение | ||
Строка 90: | Строка 93: | ||
{{Утверждение | {{Утверждение | ||
|statement=<tex dpi="350">Seq_k(A)(t)=A(t)^k</tex> | |statement=<tex dpi="350">Seq_k(A)(t)=A(t)^k</tex> | ||
− | |proof=Докажем по | + | |proof=Докажем по индукции: |
'''База <tex dpi="350">k=1</tex>'''. | '''База <tex dpi="350">k=1</tex>'''. | ||
Строка 96: | Строка 99: | ||
'''Переход'''. | '''Переход'''. | ||
− | :Пусть для <tex dpi="350">k=n</tex> верно <tex dpi="350">Seq_n(A)(t)=A(t)^n</tex>. Докажем для | + | :Пусть для <tex dpi="350">k=n</tex> верно <tex dpi="350">Seq_n(A)(t)=A(t)^n</tex>. Докажем для <tex dpi="350">k=n+1</tex>: |
− | <tex dpi="350">k=n+1</tex>: <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^{n+1}</tex>. Рассмотрим <tex dpi="350">Seq_{n+1}(A)</tex> как <tex dpi="350">Pair(Seq_n(A), A)</tex>. Тогда <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^n \cdot A(t)=A(t)^{n+1}</tex>. | + | <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^{n+1}</tex>. Рассмотрим <tex dpi="350">Seq_{n+1}(A)</tex> как <tex dpi="350">Pair(Seq_n(A), A)</tex>. Тогда <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^n \cdot A(t)=A(t)^{n+1}</tex>. |
}} | }} | ||
Строка 104: | Строка 107: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Последовательностью | + | Последовательностью объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)</tex>. |
}} | }} | ||
Строка 110: | Строка 113: | ||
{{Утверждение | {{Утверждение | ||
|statement=<tex dpi="350">Seq(A)(t)=\frac{1}{1 - A(t)}</tex> | |statement=<tex dpi="350">Seq(A)(t)=\frac{1}{1 - A(t)}</tex> | ||
− | |proof=<tex dpi="350">Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}</tex> ( | + | |proof=<tex dpi="350">Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}</tex> (Геометрическая прогрессия) |
}} | }} | ||
Строка 117: | Строка 120: | ||
* Технически, если <tex dpi="350">a_0>1</tex>, то мы будем делить на отрицательное число; если <tex dpi="350">a_0=1</tex>, то на функцию, у которой свободный член <tex dpi="350">0</tex>, {{---}} что формализм производящих функций сделать не позволяет. | * Технически, если <tex dpi="350">a_0>1</tex>, то мы будем делить на отрицательное число; если <tex dpi="350">a_0=1</tex>, то на функцию, у которой свободный член <tex dpi="350">0</tex>, {{---}} что формализм производящих функций сделать не позволяет. | ||
* Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей. | * Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей. | ||
− | |||
====Примеры==== | ====Примеры==== | ||
Строка 127: | Строка 129: | ||
** <tex dpi="350">Seq_{\vdots 2}(A)(t)=Seq(Pair(A, A))(t)=\frac{1}{1-A\left (t^2\right )}</tex> | ** <tex dpi="350">Seq_{\vdots 2}(A)(t)=Seq(Pair(A, A))(t)=\frac{1}{1-A\left (t^2\right )}</tex> | ||
− | ==Комбинаторный класс " | + | ==Комбинаторный класс "Натуральные числа"== |
Вес числа равен его значению. Каждое натуральное число встречается 1 раз. | Вес числа равен его значению. Каждое натуральное число встречается 1 раз. | ||
Строка 136: | Строка 138: | ||
Класс "Натуральные числа" принято обозначать <tex dpi="350">I</tex>. | Класс "Натуральные числа" принято обозначать <tex dpi="350">I</tex>. | ||
− | + | Считающая последовательность {{---}} | |
<tex dpi="350">c_n=\left\{\begin{matrix} | <tex dpi="350">c_n=\left\{\begin{matrix} | ||
0, n=0\\ | 0, n=0\\ | ||
Строка 153: | Строка 155: | ||
===Применение=== | ===Применение=== | ||
− | <tex dpi="350">Seq(I)</tex> {{---}} упорядоченное [[Нахождение количества разбиений числа на слагаемые|разбиение на слагаемые]]. | + | <tex dpi="350">Seq(I)</tex> {{---}} упорядоченное [[Нахождение количества разбиений числа на слагаемые|разбиение натуральных чисел на слагаемые]]. |
− | <tex dpi="350">Seq(I)(t)=\frac{1}{1-\frac{t}{1-t}}=\frac{1-t}{1-2t}=\frac{1}{1-2t}-\frac{t}{1-2t}</tex> | + | Тогда производящая функция {{---}} <tex dpi="350">Seq(I)(t)=\frac{1}{1-\frac{t}{1-t}}=\frac{1-t}{1-2t}=\frac{1}{1-2t}-\frac{t}{1-2t}</tex> |
<tex dpi="350">\left [ t^n \right ] \frac{1-t}{1-2t} = \left\{\begin{matrix} | <tex dpi="350">\left [ t^n \right ] \frac{1-t}{1-2t} = \left\{\begin{matrix} | ||
Строка 161: | Строка 163: | ||
\\ | \\ | ||
1, n = 0 | 1, n = 0 | ||
− | \end{matrix}\right.</tex> | + | \end{matrix}\right.</tex>, потому что <tex dpi="350">\frac{1}{1-2t}</tex> соответсвует ряду степеней <tex dpi="350">2</tex>, а <tex dpi="350">\frac{1}{1-2t}</tex> {{---}} ряду <tex dpi="350">2^{x-1}</tex>. |
==Множества== | ==Множества== | ||
Строка 242: | Строка 244: | ||
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | <tex dpi="350">\left (\int A(t) \right )'=A(t)</tex> | + | <tex dpi="350">\left (\int A(t) \right )'=A(t)</tex><ref>[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e&t=2131 Youtube {{---}} Помеченные объекты]</ref> |
}} | }} | ||
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | Пусть <tex dpi="350">A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">\{ a_0, a_1, ..., a_n, ... \}</tex>, тогда <tex dpi="350">\int A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">B=\{ 0, a_0, a_1, a_2, ..., a_n, ... \}</tex> | + | Пусть <tex dpi="350">A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">\{ a_0, a_1, ..., a_n, ... \}</tex>, тогда <tex dpi="350">\int A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">B=\{ 0, a_0, a_1, a_2, ..., a_n, ... \}</tex><ref>[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e&t=2131 Youtube {{---}} Помеченные объекты]</ref> |
}} | }} | ||
Строка 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> | ||
Строка 316: | Строка 318: | ||
Последовательности длины <tex dpi="350">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом: | Последовательности длины <tex dpi="350">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом: | ||
* Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex> | * Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex> | ||
− | * | + | * Перенумеруются всеми возможными способами. |
Их принято обозначать <tex dpi="350">Seq_k(A)</tex>. | Их принято обозначать <tex dpi="350">Seq_k(A)</tex>. | ||
Строка 326: | Строка 328: | ||
===Неограниченная конструкция=== | ===Неограниченная конструкция=== | ||
− | Определение <tex dpi="350">Seq(A)</tex> | + | Определение <tex dpi="350">Seq(A)</tex> не изменилось. |
+ | |||
+ | {{Утверждение | ||
+ | |statement=<tex dpi="350">Seq(A)(t)=\frac{1}{1 - A(t)}</tex> | ||
+ | |proof=<tex dpi="350">Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}</tex> (Геометрическая прогрессия) | ||
+ | }} | ||
Действует ограничение на <tex dpi="350">b_0=B(0)=0</tex>, как и на <tex dpi="350">Seq(A)</tex> и <tex dpi="350">MSet(A)</tex> в формализме непомеченных объектов. | Действует ограничение на <tex dpi="350">b_0=B(0)=0</tex>, как и на <tex dpi="350">Seq(A)</tex> и <tex dpi="350">MSet(A)</tex> в формализме непомеченных объектов. | ||
Строка 332: | Строка 339: | ||
====Пример==== | ====Пример==== | ||
− | ''' | + | '''Перестановки''' |
* <tex dpi="350">P=Seq(Z)</tex> | * <tex dpi="350">P=Seq(Z)</tex> | ||
* Экспоненциальной производящей функцией является <tex dpi="350">P(t)=\frac{1}{1-t}</tex>. | * Экспоненциальной производящей функцией является <tex dpi="350">P(t)=\frac{1}{1-t}</tex>. | ||
Строка 371: | Строка 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>. | |
− | |||
}} | }} | ||
Строка 397: | Строка 403: | ||
|definition=Циклы <tex dpi="350">A=Cycle(B)=\sum_{k=0}^{\infty}Cycle_k(B)</tex>. | |definition=Циклы <tex dpi="350">A=Cycle(B)=\sum_{k=0}^{\infty}Cycle_k(B)</tex>. | ||
}} | }} | ||
− | <tex dpi="350">Cycle(A)(t)=\sum_{k=0}^{\infty}Cycle_k(A)(t)=0+\sum_{k=1}^{\infty}\frac{A(t)^k}{k}=-ln \left (1-A(t) \right )=ln\left (\frac{1}{1-A(t)}\right )</tex> | + | <tex dpi="350">Cycle(A)(t)=\sum_{k=0}^{\infty}Cycle_k(A)(t)=0+\sum_{k=1}^{\infty}\frac{A(t)^k}{k}=-ln \left (1+\left (-A(t)\right ) \right )=-ln \left (1-A(t) \right )=ln\left (\frac{1}{1-A(t)}\right )</tex> (Разложение натурального логарифма в ряд Тейлора) |
=См.также= | =См.также= |
Текущая версия на 22:29, 20 августа 2020
В комбинаторике, особенно в аналитической комбинаторике, символьный метод - это метод подсчета комбинаторных объектов. Он использует внутреннюю структуру объектов для получения формул их производящих функций. Этот метод в основном связан с Филиппом Флайоле и подробно описан в части A его книги с Робертом Седжвиком "Аналитическая комбинаторика"[1].
Содержание
- 1 Базовые определения
- 2 Непомеченные комбинаторные объекты
- 3 Помеченные объекты
- 4 См.также
- 5 Примeчания
- 6 Источники информации
Базовые определения[править]
Каждый комбинаторный объект состоит из атомов.
У атомов определен вес
. Вес объектов равен сумме весов составляющих его атомов.
Определение: |
Считающей последовательностью называется последовательность | , где — количество объектов веса .
Обозначим как оператор взятия -того коэффициента производящей функции.
Определение: |
Комбинаторным классом | называется множество комбинаторных объектов, обладающих каким-то свойством.
Непомеченные комбинаторные объекты[править]
Введём атомы
и следующим образом:
Производящую функцию класса
обозначим , если — считающая последовательность этого класса.
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса .
Считающая последовательность: .
Производящая функция последовательности:
.
Определение: |
Комбинаторным объектом | называется комбинаторный объект, состоящий из одного атома веса . .
Считающая последовательность: .
Производящая функция последовательности:
.Объединение комбинаторных классов[править]
Определение: |
Объединением комбинаторных классов | и называется комбинаторный класс , состоящий из элементов обоих классов, причем равные объекты разных классов объявляются разными.
Целью этого уточнения является возможность работать только со считающими последовательностями и производящими функциями.
Пары комбинаторных классов (декартово произведение комбинаторных классов)[править]
Определение: |
Парой комбинаторных классов | и называется комбинаторный класс .
Утверждение: |
Последовательности комбинаторных классов[править]
Ограниченная конструкция[править]
Определение: |
Последовательностью | объектов из называется .
Утверждение: |
Докажем по индукции: База .
Переход.
|
Неограниченная конструкция[править]
Определение: |
Последовательностью объектов из | называется .
Утверждение: |
(Геометрическая прогрессия) |
Ограничение: (также можно встретить ). Этому есть как техническое, так и комбинаторное объяснение.
- Технически, если , то мы будем делить на отрицательное число; если , то на функцию, у которой свободный член , — что формализм производящих функций сделать не позволяет.
- Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
Примеры[править]
- Последовательности из не менее, чем 3 объектов:
- Последовательности чётной длины:
Комбинаторный класс "Натуральные числа"[править]
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
Считающая последовательность:
Класс "Натуральные числа" принято обозначать
. Считающая последовательность —Утверждение: |
Производящей функцией последовательности из явлется .Чтобы получить производящую функцию класса натуральных чисел, произведем сдвиг вправо по правилам работы со степенными рядами: |
Применение[править]
разбиение натуральных чисел на слагаемые.
— упорядоченноеТогда производящая функция —
, потому что соответсвует ряду степеней , а — ряду .
Множества[править]
Определение: |
Множества | — последовательности без повторений и порядка элементов.
Утверждение: |
Докажем по индукции по потенциальным элементам множеств .База
Переход Пусть верно для множества В множестве каждый элемент может либо присутствовать, либо отсутствовать, поэтому , докажем, что будет верно и для множества и , где . |
Пример[править]
Мультимножества[править]
Определение: |
Мультимножества | — последовательности с повторениями, но без порядка элементов.
Как и с
существует ограничение на : .Утверждение: |
Докажем по индукции по потенциальным элементам множеств .База
Переход Отличие от множеств в том, что здесь каждый элемент может присутствовать в любом неотрицательном количестве экземпляров, поэтому для каждого элемента беретсяПусть верно для мультимножества , докажем, что будет верно и для мультимножества и , где . |
Помеченные объекты[править]
Как можно заметить, для некоторых операторов, например, экспоненциальная производящая функция.
и не существует замкнутых формул, поэтому их объекты удобнее обозначать как помеченные. С помеченными объектами используетсяНапомним, что если
— считающая последовательность, то производящие функции выражаются следующим образом:Обычная | |
Экспоненциальная |
Далее под производящей функцией будет подразумеваться и использоваться экспоненциальная производящая функция, потому что формулы с ней более просты в работе.
Свойства экспоненциальной производящей функции[править]
Утверждение: |
Пусть — экспоненциальная производящая функция последовательности , тогда — экспоненциальная производящая функция последовательности |
Утверждение: |
Утверждение: |
Пусть [4] — экспоненциальная производящая функция последовательности , тогда — экспоненциальная производящая функция последовательности |
Утверждение: |
С точки зрения комбинаторики композиция производящих функций и означает подстановку вместо каждого возможного атома в всех объектов из класса .
|
Помеченные объекты[править]
Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки; Если вес объекта равен
, то все атомы пронумерованы различными целыми числами от до .
Определение: |
Комбинаторным объектом
| называется комбинаторный объект, состоящий из одного атома веса .
Определение: |
Комбинаторным объектом
| называется комбинаторный объект, состоящий из одного атома веса .
Объединение комбинаторных классов[править]
Одинаковых объектов также нет, мы ставим разные метки на одинаковые объекты из разных классов, чтобы сделать их различными.
Пары комбинаторных классов (декартово произведение комбинаторных классов)[править]
Декартово произведение, определенное для непомеченных объектов, нам не даст корректный комбинаторный объект.
Тогда пара
будет иметь вес 5, но атомы не будут иметь различные пометки от 1 до 5.
Поэтому введем оператор
, который- Перебирает все пары из и .
- В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе
, но не будет лежать
.
будет лежать
Последовательности комбинаторных классов[править]
Ограниченная конструкция[править]
Последовательности длины
, как и в непомеченных комбинаторных объектах, формируются следующим образом:- Cоставляются все возможные последовательности из объектов из
- Перенумеруются всеми возможными способами.
Их принято обозначать
.-тый член выражается следующим образом:
Поэтому производящая функция —
Неограниченная конструкция[править]
Определение
не изменилось.Утверждение: |
(Геометрическая прогрессия) |
Действует ограничение на
, как и на и в формализме непомеченных объектов.Пример[править]
Перестановки
- Экспоненциальной производящей функцией является .
- Обычной производящей функции соответствует считающая последовательность , поэтому .
Урны[править]
Кобинаторный класс "Урна" — множество, характеризующееся только количеством атомов в объекте, то есть элементов каждого веса —
, поэтому .Производящая функция этого класса —
.Множества[править]
В формализме помеченных объектов
, потому что не бывает одинаковых элементов в множествах.Ограниченная конструкция[править]
Определение: |
Ограниченным множеством | назовём множество из объектов (порядок не важен).
Рассмотрим и разобьем последовательности в на классы эквивалентности по признаку равенства множеств элементов в них.
Каждому биективно соответствует последовательностей в , потому что все объекты различны.
Неограниченная конструкция[править]
— множества объектов (порядок не важен).
Ограничение
также действует.
Можно рассматривать
как композицию урны и , другими словами, можно вместо атомов в урне взять объекты класса .Циклы[править]
Ограниченная конструкция[править]
Определение: |
Цикл | — ориентированная циклическая последовательность из объектов класса . Циклов нулевой длины , то есть, .
Утверждение: |
Каждому циклу циклические перестановки элементов цикла). длины биективно соответствует упорядоченных последовательностей ( |
Поэтому
Значит, экспоненциальная производящая функция циклов —
.Неограниченная конструкция[править]
Определение: |
Циклы | .
(Разложение натурального логарифма в ряд Тейлора)
См.также[править]
- Конструирование комбинаторных объектов и их подсчёт
- Функция Эйлера
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Каталана
- Генерация комбинаторных объектов в лексикографическом порядке
- Подсчет деревьев