Изменения

Перейти к: навигация, поиск

Обсуждение:Метод производящих функций

7475 байт добавлено, 22:29, 20 августа 2020
Нет описания правки
В комбинаторике, особенно в аналитической комбинаторике, символический [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>.
 ==Базовые определения=Непомеченные комбинаторные объекты=
Каждый комбинаторный объект состоит из атомов.
У атомов определен вес <tex dpi="130">w</tex>. Вес объектов равен сумме весов составляющих его атомов.
{{Определение|definition=Считающей последовательностью называется последовательность <tex dpi="130">w(\bullet)left \{ a_0, a_1, ..., a_n \right \}</tex>, где <tex dpi=1"130">a_i</tex> {{---}} количество объектов веса <tex dpi="130">i</tex>.}}
Обозначим <tex dpi="130350">w(\circ)[t_n]</tex> как оператор взятия <tex dpi=0"350">n</tex>-того коэффициента производящей функции.
{{Определение
|definition=
Считающей последовательностью называется последовательность Комбинаторным классом <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}A</tex>называется множество комбинаторных объектов, где <tex dpi="130">a_i</tex> {{--обладающих каким-}} количество объектов веса <tex dpi="130">i</tex>то свойством.
}}
=Непомеченные комбинаторные объекты= Введём атомы <tex dpi="350">\bullet</tex> и <tex dpi="350">\circ</tex> следующим образом: <tex dpi="130">w(\bullet)=1</tex> <tex dpi="130">w(\circ)=0</tex> Производящую функцию класса <tex dpi="130">A</tex> обозначим <tex dpi="130">A(t)=\sum_{i=0}^{\infty }a_i t^i</tex>, если <tex dpi="350">\{a_i\}</tex> {{---}} считающая последовательность этого класса.
{{Определение
Считающая последовательность: <tex dpi="130">\left \{ 0, 1, 0, ..., 0 \right \}</tex>.
 
Производящая функция последовательности: <tex dpi="130">Z(t)=t</tex>.
Считающая последовательность: <tex dpi="130">\left \{ 1, 0, ..., 0 \right \}</tex>.
 
Производящая функция последовательности: <tex dpi="130">\varepsilon(t)=1</tex>.
 
{{Определение
|definition=
Комбинаторным классом <tex dpi="130">A</tex> называется множество комбинаторных объектов, обладающих каким-то свойством.
}}
==Объединение комбинаторных классов==
{{Определение
|definition=
Объединением комбинаторных классов <tex dpi="350">A</tex> и <tex dpi="350">B</tex> называется комбинаторный класс <tex dpi="350">C=A \cup B=A+B=\left \{ c \mid c \in A \vee c \in B \right \}</tex>, состоящий из элементов обоих классов, причем равные объекты разных классов объявляются разными.
}}
 При объединении комбинаторных классов одинаковые объекты разных классов считаются разными. Это делается так, чтобы не рассматривать внутреннюю структуру классов, а Целью этого уточнения является возможность работать только со считающими последовательностями и производящими функциями.
<tex dpi="350">c_n=a_n+b_n</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>
 
==Пары комбинаторных классов (декартово произведение комбинаторных классов)==
{{Утверждение
|statement=<tex dpi="350">C(t)=A(t) \cdot B(t)</tex>|proof=Верно, потому что коэффициенты производящей функции описываются равенством выше<ref>[[Арифметические действия с формальными степенными рядами]]</ref>
}}
==Последовательности комбинаторных классов==
 
===Ограниченная конструкция===
{{Определение
'''Переход'''.
:Пусть для <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">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>.
}}
===Неограниченная конструкция===
{{Определение
|definition=
Последовательностью ''(всех возможных длин)'' объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)</tex>.
}}
'''Ограничение:''' <tex dpi="350">a_0=0</tex>(также можно встретить <tex dpi="350">A_0=0</tex>). Этому есть как техническое, так и комбинаторное объяснение.
* Технически, если <tex dpi="350">a_0>1</tex>, то мы будем делить на отрицательное число; если <tex dpi="350">a_0=1</tex>, то на функцию, у которой свободный член <tex dpi="350">0</tex>, {{---}} что формализм производящих функций сделать не позволяет.
* Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
 
<tex dpi="350">A(0)=0</tex>
 
====Примеры====
* Последовательночти Последовательности из не менее , чем 3 объектов:
** <tex dpi="350">Seq_{\geq 3}=Pair(Seq_3(A), Seq(A))=Seq(A)-Seq_0(A)-Seq_1(A)-Seq_2(A)</tex>
** <tex dpi="350">Seq_{\geq 3}(t)=Pair(Seq_3(A), Seq(A))(t)=A(t)^3 \cdot \frac{1}{1-A(t)}=\frac{A(t)^3}{1-A(t)}=(Seq(A)-Seq_0(A)-Seq_1(A)-Seq_2(A))(t)=\frac{1}{1-A(t)}-0-A(t)-A(t)^2</tex>
* Последовательности чётной длины:
** <tex dpi="350">Seq_{\vdots 2}(A)=Seq(Pair(A, A))</tex>
** <tex dpi="350">Seq_{\vdots 2}(A)(t)=Seq(Pair(A, A))(t)=\frac{1}{1-A\left (t)^2\right )}</tex>
 ==Комбинаторный объект класс "Натуральные числа"==
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
<tex dpi="350">w(n)=n</tex>
Класс "Натуральные числа" принято обозначать <tex dpi="350">I</tex>.
Считающая последовательность {{---}}
<tex dpi="350">c_n=\left\{\begin{matrix}
0, n=0\\
\end{matrix}\right.</tex>
{{Утверждение|statement=<tex dpi="350">I(t)=\frac{t \cdot }{1 - t}</tex>|proof=Производящей функцией последовательности из <tex dpi="350">1</tex> явлется <tex>Seq(Z\{1\})=\frac{1}{1-t}</tex>. Чтобы получить производящую функцию класса натуральных чисел, произведем сдвиг вправо по правилам работы со степенными рядами:<tex dpi="350">t \cdot I(t) = t \cdot \frac{1}{1 - t} = \frac{t}{1 - t}</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">\left [ t^n \right ] \frac{1-t}{1-2t} = \left\{\begin{matrix}
\\
1, n = 0
\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>.
==Множества==
{{Определение|definition=Множества <tex dpi="350">Set(A)</tex> {{---}} последовательности без повторений и порядка элементов.}}{{Утверждение|statement=<tex dpi="350">Set(A)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )</tex>|proof=Докажем по индукции по потенциальным элементам множеств <tex dpi="350">A</tex>. '''База''' <tex dpi="350">A=\varnothing</tex> <tex dpi="350">Set(\varnothing)=\varepsilon=\prod_{\alpha\in A}\varepsilon</tex> '''Переход''' Пусть верно для множества <tex dpi="350">A_1</tex>, докажем, что будет верно и для множества и <tex dpi="350">A_1+\{\alpha\}</tex>, где <tex dpi="350">\alpha\in A\setminus A_1</tex>В множестве каждый элемент может либо присутствовать, либо отсутствовать, поэтому <tex dpi="350">Set(A_1+\{\alpha\})=Set(A_1)+Set(A_1)\times\{\alpha\}=Set(A_1)(\varepsilon + \alpha)</tex>.}}
====Пример====
* <tex dpi="350">A = \left \{ \alpha, \beta, \gamma \right \}</tex>
* <tex dpi="350">Set(A) = \left \{ \varnothing, \left \{ \alpha \right \}, \left \{ \beta\right \}, \left \{ \gamma \right \}, \left \{ \alpha, \beta\right \}, \left \{ \alpha, \gamma \right \}, \left \{ \beta, \gamma \right \}, \left \{ \alpha, \beta, \gamma \right \} \right \}</tex>
 
<tex dpi="350">Set(A)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )</tex>
<tex dpi="350">Set(A)(t)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )(t)=\prod_{\alpha \in A}(1+t^{w(\alpha)})=\prod_{n=0}^{\infty}(1+t^n)^{a_n}</tex>
==Мультимножества==
{{Определение|definition=Мультимножества <tex dpi="350">MSet(A)</tex> {{---}} последовательности с повторениями, но без порядка элементов.}}Как и с <tex dpi="350">Seq(A)</tex> существует ограничение на <tex dpi="350">A</tex>: <tex dpi="350">a_0=A(0)=0</tex>.{{Утверждение|statement=<tex dpi="350">MSet(A)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})</tex>|proof=Докажем по индукции по потенциальным элементам множеств <tex dpi="350">A</tex>. '''База''' <tex dpi="350">A=\varnothing</tex> <tex dpi="350">MSet(\varnothing)=\varepsilon=\prod_{\alpha\in A}\varepsilon</tex>
Как и с <tex dpi="350">Seq(A)</tex> существует ограничение на <tex dpi="350">A</tex>: <tex dpi="350">a_0=A(0)=0</tex>.'''Переход'''
Отличие от множеств в том, что здесь каждый элемент может присутствовать в любом неотрицательном количестве экземпляров, поэтому для каждого элемента <tex dpi="350">MSet\alpha</tex> берется <tex dpi="350">Seq(A\{\alpha\})</tex> Пусть верно для мультимножества <tex dpi="350">A_1</tex>, докажем, что будет верно и для мультимножества и <tex dpi="350">A_1+Seq_{\geq1}(\prod_{\alpha\})</tex>, где <tex dpi="350">\alpha \in A\setminus A_1</tex><tex dpi="350">MSet(A_1+\{\alpha\}Seq)=MSet(A_1)+MSet(A_1)\times\{\left alpha\}\times Seq_{\geq 1}(\{ \alpha \right })=MSet(A_1)\cdot Seq(\{\alpha\})</tex>.}}
<tex dpi="350">MSet(A)(t)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})(t)=\prod_{\alpha \in A}\frac{1}{1-t^{w(\alpha)}}=\prod_{n=1}^{\infty}\left(\frac{1}{1-t^n}\right)^{a_n}</tex>
 
=Помеченные объекты=
Однако порой некоторые комбинаторные классы Как можно заметить, для некоторых операторов, например, <tex dpi="350">Set</tex> и <tex dpi="350">MSet</tex> не существует замкнутых формул, поэтому их объекты удобнее обозначать как помеченные. Например, — помеченные графы. С помеченными объектами используется [https://en.wikipedia.org/wiki/Generating_function#Exponential_generating_function_(EGF) экспоненциальная производящая функция].
НапомнюНапомним, что если <tex dpi="350">\left \{ a_i \right \}</tex> {{---}} считающая последовательность, то производящие функции выражаются следующим образом:
{| class="wikitable"
|}
Далее под производящей функцией будет подразумеваться и использоваться экспоненциальная производящая функция, потому что формулы с ней более просты в работе.
==Свойства экспоненциальной производящей функции==
{{Утверждение
|statement=
<tex dpi="350">\left (\int A(t) \right )'=A(t)</tex><ref>[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e&t=2131 Youtube {{---}} Помеченные объекты]</ref>
}}
{{Утверждение
|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><ref>[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e&t=2131 Youtube {{---}} Помеченные объекты]</ref>
}}
|statement=С точки зрения комбинаторики композиция производящих функций <tex dpi="350">A</tex> и <tex dpi="350">B</tex> означает подстановку вместо каждого возможного атома в <tex dpi="350">A</tex> всех объектов из класса <tex dpi="350">B</tex>.
<tex dpi="350">A \left ( B \left ( t \right ) \right )=\sum_{n=0}^{\infty}\frac{B(st)^n\cdot a_n}{n!}</tex>
<tex dpi="350">c_n=\sum_{k=0}^na_k\sum_{t_1+t_2+...+t_k=n}\binom{n}{t_1, t_2, ..., t_n}\cdot b_{t_1} b_{t_2}\cdot...\cdot b_{t_n}</tex>
==Помеченные объекты==
Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки, а именно {{---}} если ; Если вес объекта равен <tex dpi="350">n</tex>, то все атомы пронумерованы различными целыми числами от <tex dpi="350">1</tex> до <tex dpi="350">n</tex>.
<tex dpi="130">w(①)=1</tex>
<tex dpi="130">w(\circ)=0</tex>
 
Далее под производящей функцией будет подразумеваться экспоненциальная производящая функция.
{{Определение
<tex dpi="130">Z=\left \{ ① \right \}</tex>
 
<tex dpi="130">Z(t)=t</tex>
}}
 
Производящая функция последовательности: <tex dpi="130">Z(t)=t</tex>.
 
{{Определение
|definition=
Комбинаторным объектом <tex dpi="130">\varepsilon</tex> называется комбинаторный объект, состоящий из одного атома веса <tex dpi="130">0</tex>.
<tex dpi="130">\varepsilon=\left \{ \circ \right \}</tex>. <tex dpi="130">\varepsilon(t)=1</tex>
}}
 
Производящая функция последовательности: <tex dpi="130">\varepsilon(t)=1</tex>.
 
==Объединение комбинаторных классов==
==Пары комбинаторных классов (декартово произведение комбинаторных классов)==
Напрямую декартово Декартово произведение , определенное для непомеченных объектов, нам не даст корректный комбинаторный объект.
Пусть <tex dpi="350">A= \{</tex> [[Файл:1-2.png|50px]] <tex dpi="350">\}</tex>,
Тогда пара <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:1-2-3.png|50px]]<tex dpi="350">)</tex> будет иметь вес 5, но атомы не будут иметь различные пометки от 1 до 5.
Поэтому введем опреатор оператор <tex dpi="350">A \star B</tex>, который
# Перебирает все пары из <tex dpi="350">A</tex> и <tex dpi="350">B</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>''(Сочетания)''<tex dpi="350">=\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">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом:* Мы составляем Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex>* Затем Перенумеруются всеми возможными способами их перенумеруем.
Действует ограничение на Их принято обозначать <tex dpi="350">b_0=B(0)=0</tex> как и <tex dpi="350">SeqSeq_k(A)</tex> и в <tex dpi="350"Mset(A)></tex> в мире непомеченных объектов.
Обозначаются <tex dpi="350">Seq_k(A)n</tex>-тый член выражается следующим образом: <tex dpi="350">b_n=\sum_{t_1+t_2+...+t_k=n}\binom{n}{t_1}\cdot\binom{n-t_1}{t_2}\cdot...\cdot\binom{t_k}{t_k}\cdot\prod_{i=1}^{k}a_{t_i}=\sum_{t_1+t_2+...+t_k=n}\binom{n}{t_1, t_2,...,t_k}\cdot\prod_{i=1}^{k}a_{t_i}=\sum_{t_1+t_2+...+t_k=n}\frac{n!}{t_1! \cdot t_2! \cdot ... \cdot t_k!}\cdot\prod_{i=1}^{k}a_{t_i}=n!\sum_{t_1+t_2+...+t_k=n}\prod_{i=1}^{k}\frac{a_{t_i}}{t_i!}</tex>
Поэтому производящая функция {{---}} <tex dpi="350">b_n=\sum_{t_1+t_2+...+t_k=n}\binom{n}{t_1}\cdot\binom{n-t_1}{t_2}\cdot...\cdot\binom{t_k}{t_k}\cdot\prod_{i=1}^{k}a_{t_i}=\sum_{t_1+t_2+...+t_k=n}\binom{n}{t_1, t_2,...,t_k}\cdot\prod_{iB(t)=1}^{k}a_{t_i}=\sum_{t_1+t_2+...+t_k=n}\frac{n!}{t_1! \cdot t_2! \cdot ... \cdot t_k!}\cdotleft ( A\prod_{i=1}^{k}a_{t_i}=n!left (t\sum_{t_1+t_2+...+t_k=n}right ) \prod_{i=1}right )^{k}\frac{a_{t_i}}{t_i!}</tex>
<tex dpi="350">B(t)=\left ( A\left (t\right ) \right )^k</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">P=Seq(Z)</tex>
* Экспоненциальной производящей функцией является <tex dpi="350">P(t)=\frac{1}{1-t}</tex>.* Обычной производящей функции <tex dpi="350">\frac{1}{1-t}</tex> соответствует считающая последовательность <tex dpi="350">\left \{ 1, 1, ..., 1\right \}</tex>, поэтому <tex dpi="350">[s_nt_n]\frac{1}{1-t}=1</tex>.* <tex dpi="350">p_n=n!\cdot[s_nt_n]p(st)=n!</tex> 
==Урны==
Кобинаторный класс "Урна" {{---}} множество, характеризующееся только количеством атомов в объекте, то есть элементов каждого веса {{---}} <tex dpi="350">1</tex>, поэтому <tex dpi="350">a_n=1</tex>.
Урна характеризуется только количеством атомов в ней, поэтому Производящая функция этого класса {{---}} <tex dpi="350">a_nedf(t)=\sum_{n=0}^{\infty}\frac{1\cdot t^n}{n!}=\sum_{n=0}^{\infty}\frac{t^n}{n!}=e^t</tex>.
<tex dpi="350">edf(t)=\sum_{nМножества=0}^{\infty}\frac{1\cdot t^n}{n!}=\sum_{n=0}^{\infty}\frac{t^n}{n!}=e^t</tex>
В формализме помеченных объектов <tex dpi="350">MSet=Set</tex>, потому что не бывает одинаковых элементов в множествах.
==Множества=Ограниченная конструкция===
В помеченном мире {{Определение|definition=Ограниченным множеством <tex dpi="350">MsetA=SetSet_k(B)</tex> назовём множество из <tex dpi="350">k</tex>, потому что объектов (порядок не бывает одинаковых элементов в множествахважен).}}
Рассмотрим <tex dpi="350">A=\left \{ a_1, a_2, ..., a_k \right \} \in Set_k(B)</tex> {{---}} множество из k объектов и разобьем последовательности в <tex dpi="350">Seq_k(порядок не важенB)</tex> на классы эквивалентности по признаку равенства множеств элементов в них.
Каждому <tex dpi="350">\left \{ a_1, a_2, ..., a_k \right \} \in 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">\cdot k!</tex> последовательностей в <tex dpi="350">Seq_k(B)</tex>, потому что все объекты различны.
<tex dpi="350">Set_k(B)*k!=Seq_k(B)</tex> <tex dpi="350">Set_k(B)(t)=A(t)=\frac{\left ( B \left ( s t \right ) \right )^k}{k!}</tex>
===Неограниченная конструкция===
<tex dpi="350">A=Set(B)=\sum_{k=0}^{\infty}Set_k(b)</tex> {{---}} множества объектов (порядок не важен).
<tex dpi="350">Set(A)(t)=\sum_{k=0}^{\infty}\frac{A(t)^k}{k!}=e^{A(t)}</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>.}}
{{Утверждение|statement=Циклов <tex dpi="350">0</tex>-вой нулевой длины <tex dpi="350">0</tex>. , то есть, <tex dpi="350">c_0=0</tex>.
}}
{{Утверждение
|statement=
Каждому циклу <tex dpi="350">(b_1, b_2, ..., b_k)</tex> длины <tex dpi="350">k</tex> биективно соответствует <tex dpi="350">k</tex> упорядоченных последовательностей ([https://en.wikipedia.org/wiki/Cyclic_permutation циклические перестановки ] элементов цикла).
}}
Поэтому <tex dpi="350">Seq_k(A) = k\cdot Cycle_k(A)</tex>
Значит, экспоненциальная производящая функция циклов {{---}} <tex dpi="350">Cycle_k(A)(t)=\frac{Seq_k(A)(t)}{k}=\frac{A(t)^k}{k}</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+\left (-A(t)\right ) \right )=-ln \left (1-A(t) \right )=ln\left (\frac{1}{1-A(t)}\right )</tex> (Разложение натурального логарифма в ряд Тейлора)
 
=См.также=
*[[Конструирование комбинаторных объектов и их подсчёт]]
*[[Функция Эйлера]]
*[[Лемма Бёрнсайда и Теорема Пойа]]
*[[Задача об ожерельях]]
*[[Числа Каталана]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Подсчет деревьев]]
 
=Примeчания=
<references/>
 
=Источники информации=
*[https://youtu.be/J2L-vdytqC0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e Artem Vasilyev {{---}} Descrete maths lectures, unmarked objects]
*[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e Artem Vasilyev {{---}} Descrete maths lectures, marked objects]
*[https://neerc.ifmo.ru/wiki/index.php?title=Конструирование_комбинаторных_объектов_и_их_подсчёт Викиконспекты {{---}} Конструирование комбинаторных объектов и их подсчёт]
*[https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) Wikipedia {{---}} Symbolic method]
<tex dpi="350">Cycle(A)(t)=\sum_{k=0}^{\infty}Cycle_k(B)(t)=0+\sum_{k=1}^{\infty}\frac{B(t)^k}{k}=-ln(1-t)=ln\left (\frac{1}{1-t}\right )</tex>[[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]
Анонимный участник

Навигация