Изменения

В комбинаторике, особенно в аналитической комбинаторике, символический [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>-того коэффициента производящей функции.

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

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

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

Последовательностью ''(всех возможных длин)'' объектов из <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>). Этому есть как техническое, так и комбинаторное объяснение.

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

** <tex dpi="350">Seq_{\vdots 2}(A)(t)=Seq(Pair(A, A))(t)=\frac{1}{1-A\left (t)^2\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>

\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">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">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">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> {{---}} считающая последовательность, то производящие функции выражаются следующим образом:

<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>''(Сочетания)''<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">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>=Неограниченная конструкция===

Определение {{Утверждение|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(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_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>

==Множества=Ограниченная конструкция===

В помеченном мире {{Определение|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">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>.

Каждому циклу <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>. ===Неограниченная конструкция===