Изменения

В [https://ru.wikipedia.org/wiki/Комбинаторика комбинаторике], особенно в аналитической комбинаторике, [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">A</tex> называется [https://ru.wikipedia.org/wiki/Множество множество] комбинаторных объектов, обладающих каким-то свойством.

Объединением комбинаторных классов <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/Прямое_произведение декартово произведение] комбинаторных классов)==

|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">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>.

|proof=Докажем по индукции по потенциальным элементам множеств<tex dpi="350">A</tex>. '''База'''

'''База <tex dpi="350">A=\varemptyvarnothing</tex>''' <tex dpi="350">Set(\varnothing)=\varepsilon=\product_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__1A_1</tex>В множестве каждый элемент может либо присутствовать, либо отсутствовать, поэтому <tex dpi="350">Set(A_1+\{\alpha\})=Set(A_1+\{\alpha\})+Set(A_1+\{\alpha\})\times\{\alpha\}=Set(A_1+\{\alpha\})(\varepsilon + \alpha)</tex>.

'''вывод общей формулы?'''{{Определение|definition=Мультимножества <tex dpi="350">MSet(A)</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}varnothing</tex>

<tex dpi="350">MSet(\varnothing)=[http://en.wikipedia.org/wiki\varepsilon=\prod_{\alpha\in A}\varepsilon</Cyclic_order Циклы]==tex>

===Ограниченная конструкция=== {{Определение|definition=Цикл <tex dpi="350">A=Cycle_k(B)</tex> {{---}} ориентированная циклическая последовательность из <tex dpi="350">k</tex> объектов класса <tex dpi="350">B</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="130">\varepsilon=\left \{ \circ \right \}</tex>. <tex dpi="130">\varepsilon(t)=1</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>

* Мы составляем Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">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>MSet(A)></tex> в мире формализме непомеченных объектов. '''опечатки, формулировки'''

'''[https://ru.wikipedia.org/wiki/Перестановка Перестановки]''' '''вроде тоже можно дать ссылку на нирк'''

* Экспоненциальной производящей функцией является <tex dpi="350">P(t)=\frac{1}{1-t}</tex>.

'''что такое урна'''Кобинаторный класс "Урна характеризуется " {{---}} множество, характеризующееся только количеством атомов в нейобъекте, поэтому то есть элементов каждого веса {{---}} <tex dpi="350">a_n=1</tex> , поэтому <tex dpi="350">edf(t)=\sum_{na_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">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(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чания==

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