Изменения

В [https://ru.wikipedia.org/wiki/Комбинаторика комбинаторике], особенно в [https://en.wikipedia.org/wiki/Analytic_Combinatorics аналитической комбинаторике], [https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) символический символьный метод] - это метод подсчета [https://neerc.ifmo.ru/wiki/index.php?title=Комбинаторные_объекты комбинаторных объектов]. Он использует внутреннюю структуру объектов для получения [https://ru.wikipedia.org/wiki/Математическая_формула формул] их [[Производящая функция|производящих функций]]. Этот метод в основном связан с [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">A</tex> называется [https://ru.wikipedia.org/wiki/Множество множество] комбинаторных объектов, обладающих каким-то свойством.

Производящую функцию класса <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="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>, состоящий из элементов обоих классов, причем равные объекты разных классов объявляются разными.

 При объединении комбинаторных классов одинаковые объекты разных классов считаются разными. Это делается так, чтобы не рассматривать внутреннюю структуру классов, а Целью этого уточнения является возможность работать только со считающими последовательностями и производящими функциями.

 ==Пары комбинаторных классов ([https://ru.wikipedia.org/wiki/Прямое_произведение декартово произведение] комбинаторных классов)==

|statement=<tex dpi="350">C(t)=A(t) \cdot B(t)</tex>|proof=Верно, потому что коэффициенты производящей функции описываются равенством выше<ref>[[Арифметические действия с формальными степенными рядами]]</ref>

|proof=Докажем по [[Математическая индукция|индукции]]:

:Пусть для <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>.

Последовательностью ''(всех возможных длин)'' объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)</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> ([https://ru.wikipedia.org/wiki/Геометрическая_прогрессия Геометрическая прогрессия])

'''Ограничение:''' <tex dpi="350">a_0=0</tex>(также можно встретить <tex dpi="350">A_0=0</tex>). Этому есть как техническое, так и комбинаторное объяснение.

* Последовательночти Последовательности из не менее , чем 3 объектов:

==Комбинаторный объект класс "[[Натуральные числа]]"==

{{Утверждение|statement=<tex dpi="350">I(t)=t \cdot Seq(Z)(t) = t \cdot \frac{1t}{1 - t} </tex>|proof=Производящей функцией последовательности из <tex dpi="350">1</tex> явлется <tex>Seq(\{1\})= \frac{t1}{1 - t}</tex>.

Чтобы получить производящую функцию класса натуральных чисел, произведем сдвиг вправо по правилам работы со степенными рядами:<tex dpi="350">Seqt \cdot I(It)= t \cdot \frac{1}{1 - t} = \frac{t}{1-t}</tex> {{---}} упорядоченное [https://ru.wikipedia.org/wiki/Разбиение_числа разбиение на слагаемые].

===Применение=== <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>

\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>.}}

{{Определение|definition=Мультимножества <tex dpi="350">MSet(A)</tex> {{---}} последовательности с повторениями, но без порядка элементов.}}

<tex dpi="350">MSet(A)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})</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">A=[http:\varnothing<//en.wikipedia.org/wiki/Cyclic_order Циклы]==tex>

<tex dpi="350">MSet(\varnothing)=\varepsilon=Ограниченная конструкция===\prod_{\alpha\in A}\varepsilon</tex>

Отличие от множеств в том, что здесь каждый элемент может присутствовать в любом неотрицательном количестве экземпляров, поэтому для каждого элемента <tex dpi="350">\alpha</tex> берется <tex dpi==Неограниченная конструкция==="350">Seq(\{\alpha\})</tex>

Пусть верно для мультимножества <tex dpi="350">A_1</tex>, докажем, что будет верно и для мультимножества и <tex dpi="350">A_1+Seq_{\geq1}(\{Определение|definition=Циклы \alpha\})</tex>, где <tex dpi="350">\alpha\in A\setminus A_1</tex><tex dpi=Cycle"350">MSet(BA_1+\{\alpha\})=MSet(A_1)+MSet(A_1)\times\{\sum_alpha\}\times Seq_{k=0\geq 1}^(\{\inftyalpha \}Cycle_k)=MSet(BA_1)\cdot Seq(\{\alpha\})</tex>.

{{Утверждение|statement=<tex dpi="350">CycleMSet(A)(t)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})(t)=\sum_prod_{n \geq 1alpha \in A} \frac{1}{1-t^{w(\phi(nalpha)}}=\prod_{n=1}^{\infty} ln \left ( \frac{1}{1-A(zt^n)} \right )^{a_n}</tex>, где <tex dpi="350">\phi(n)</tex> {{---}} [[функция Эйлера]].}}

Однако порой некоторые комбинаторные классы Как можно заметить, для некоторых операторов, например, <tex dpi="350">Set</tex> и <tex dpi="350">MSet</tex> не существует замкнутых формул, поэтому их объекты удобнее обозначать как помеченные. Например, — [https://e-maxx.ru/algo/counting_connected_graphs помеченные графы]. С помеченными объектами используется [https://en.wikipedia.org/wiki/Generating_function#Exponential_generating_function_(EGF) экспоненциальная производящая функция].

НапомнюНапомним, что если <tex dpi="350">\left \{ a_i \right \}</tex> {{---}} считающая последовательность, то производящие функции выражаются следующим образом:

<tex dpi="350">\left (\int A(t) \right )'=A(t)</tex><ref>[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e&t=2131 Youtube {{---}} Помеченные объекты]</ref>

Пусть <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>

<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">n</tex>, то все атомы пронумерованы различными целыми числами от <tex dpi="350">1</tex> до <tex dpi="350">n</tex>.

<tex dpi="130">\varepsilon=\left \{ \circ \right \}</tex>. <tex dpi="130">\varepsilon(t)=1</tex>

Напрямую декартово Декартово произведение , определенное для непомеченных объектов, нам не даст корректный комбинаторный объект.

Поэтому введем опреатор оператор <tex dpi="350">A \star 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>''([https://ru.wikipedia.org/wiki/Сочетание Сочетания])''<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">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом:* Мы составляем Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex>* Затем Перенумеруются всеми возможными способами их перенумеруем.

Обозначаются Их принято обозначать <tex dpi="350">Seq_k(A)</tex>.

<tex dpi="350">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(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>MSet(A)></tex> в мире формализме непомеченных объектов.

'''[https://ru.wikipedia.org/wiki/Перестановка Перестановки]'''

* Экспоненциальной производящей функцией является <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">a_n=1</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">MsetMSet=Set</tex>, потому что не бывает одинаковых элементов в множествах.

{{Определение|definition=Ограниченным множеством <tex dpi="350">A=Set_k(B)</tex> {{---}} назовём множество из <tex dpi="350">k </tex> объектов (порядок не важен).}}

Рассмотрим <tex dpi="350">\left \{ a_1, a_2, ..., a_k \right \} \in Set_k(B)</tex>и разобьем последовательности в <tex dpi="350">Seq_k(B)</tex> на классы эквивалентности по признаку равенства множеств элементов в них.

<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 t \right ) \right )^k}{k!}</tex>

Можно рассматривать <tex dpi="350">Set(A)</tex> {{---}} урнакак композицию урны и <tex dpi="350">A</tex>, другими словами, где можно вместо атомов взяли в урне взять объекты класса <tex dpi="350">A</tex>. 

{{УтверждениеОпределение|statementdefinition=Циклов Цикл <tex dpi="350">0A=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>.

Поэтому <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чания==

==Источники информации==