Изменения
Нет описания правки
В комбинаторике, особенно в аналитической комбинаторике, [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(\circ)=0</tex>. Вес объектов равен сумме весов составляющих его атомов.
{{Определение
}}
Обозначим <tex dpi="350">[t_n]</tex> как оператор взятия <tex dpi="350">n</tex>-того коэффициента производящей функции. {{Определение|definition=Комбинаторным классом <tex dpi="130">A</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="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 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
====Примеры====* Последовательности из не менее, чем 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">\left \{ 0, 1, ..., 1 \right \}</tex> <tex dpi="350">w(n)=n</tex> Класс "Натуральные числа" принято обозначать <tex dpi="350">I</tex>.Считающая последовательность {{---}}<tex dpi="350">c_n=\left\{\begin{matrix}0, n=0\\ 1, n>0\end{matrix}\right.</tex> {{Утверждение|statement=<tex dpi="350">I(t)=\frac{t}{1 - t}</tex>|proof=Производящей функцией последовательности из <tex dpi="350">1</tex> явлется <tex>Seq(\{1\})=\frac{1}{1-t}</tex>.
Чтобы получить производящую функцию класса натуральных чисел, произведем сдвиг вправо по правилам работы со степенными рядами:
<tex dpi="350">t \cdot I(t) = t \cdot \frac{1}{1 - t} = \frac{t}{1-t}</tex>
}}
{| class="wikitable"|-| Обычная || <tex dpi="350">ogf(t) = \sum_{i=0}^{\infty}a_it^i</tex>|---| Экспоненциальная || <tex dpi="350">egf(t) = \sum_{i=0}^{\infty}\frac{a_it^i}{n!}</tex>|}
Далее под производящей функцией будет подразумеваться и использоваться экспоненциальная производящая функция, потому что формулы с ней более просты в работе.
{{Утверждение
|statement=
Пусть <tex dpi="150350">Seq(A)(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">\frac{1a_0, a_1, ..., a_n, ... \}{1-</tex>, тогда <tex dpi="350">A'(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">B=\{ a_1, a_2, ..., a_n, ... \}</tex>.
|proof=
<tex dpi="350">B(t)=\sum_{n=0}^{\infty}\frac{a_{i+1}t^n}{n!}=\sum_{n=0}^{\infty}\frac{a_{i+1}t^n(n+1)}{(n+1)!}=A'(t)</tex>
}}
{{Утверждение
|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(t)^n\cdot a_n}{n!}</tex>
<tex dpi="130"350">S_c_n=\sum_{k=0} ^na_k\sum_{t_1+t_2+...+t_k= 1n}\binom{n}{t_1, t_2, ..., t_n}\cdot b_{t_1} b_{t_2}\cdot...\cdot b_{t_n}</tex>, так как есть единственный способ составить пустую последовательность.}}
}}
==Объединение комбинаторных классов==
<tex dpi="350">c_n=a_n+b_n</tex> <tex dpi="350">C(t)=\left ( \sum_{i=0}^{\infty}\frac{a_i \cdot t^i}{i!} \right ) + \left ( \sum_{i=0}^{\infty}\frac{b_i \cdot t^i}{i!} \right ) = \sum_{i=0}^{\infty}\frac{(a_i + b_i)\cdot t^i}{i!}=A(t)+B(t)</tex> ==Пары комбинаторных классов (декартово произведение комбинаторных классов)== Декартово произведение, определенное для непомеченных объектов, нам не даст корректный комбинаторный объект. Пусть <tex dpi="350">A= \{</tex> [[Файл:1-2.png|50px]] <tex dpi="350">\}</tex>,<tex dpi="350">B= \{</tex> [[Файл:1-2-3.png| class50px]] <tex dpi="wikitable350" >\}</tex>. Тогда пара <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:1-align2-3.png|50px]]<tex dpi="350">)</tex> будет иметь вес 5, но атомы не будут иметь различные пометки от 1 до 5. Поэтому введем оператор <tex dpi="350">A \star B</tex>, который# Перебирает все пары из <tex dpi="350">A</tex> и <tex dpi="center350" >B</tex>. !# В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе <tex dpi="350">A \star B</tex> будет лежать <tex dpi="130350">Seq(A</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="130350">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!}\dfracfrac{1b_{n-k}}{1(n-k)!}</tex> <tex dpi="350">C(t)=A(zt) \cdot B(t)}</tex>|-align==Последовательности комбинаторных классов== ===Ограниченная конструкция=== Последовательности длины <tex dpi="350">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом: * Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="center350">A</tex>* Перенумеруются всеми возможными способами. !Их принято обозначать <tex dpi="130350">PSetSeq_k(A)</tex>||. <tex dpi="350">n</tex>-тый член выражается следующим образом: <tex dpi="130350">b_n=\sum_{t_1+t_2+...+t_k=n}\binom{n}{t_1}\prodcdot\limits_binom{n -t_1}{t_2}\cdot...\cdot\binom{t_k}{t_k}\geqslant 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+...+zt_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}^{A_k}\frac{a_{t_i}}{t_i!}</tex> Поэтому производящая функция {{n---}}<tex dpi="350">B(t)=\expleft ( A\left (-t\sumright ) \limits_right )^k</tex> ===Неограниченная конструкция=== Определение <tex dpi="350">Seq(A)</tex> не изменилось. {{k Утверждение|statement=<tex dpi="350">Seq(A)(t)=\geqslant frac{1}{1- A(t)}</tex>|proof=<tex dpi="350">Seq(A)(t)=\dfracsum_{i=0}^{\infty}Seq_i(A)(-1t)=\sum_{i=0}^{k\infty}A(zt)^i=\frac{1}{k1 - A(t)}</tex> (Геометрическая прогрессия)}{k} Действует ограничение на <tex dpi="350">b_0=B(0)=0</tex>|-align, как и на <tex dpi="center350" !>Seq(A)</tex> и <tex dpi="130350">MSet(A)</tex>||в формализме непомеченных объектов. ====Пример==== '''Перестановки'''* <tex dpi="350">P=Seq(Z)</tex>* Экспоненциальной производящей функцией является <tex dpi="130350">P(t)=\prodfrac{1}{1-t}</tex>.* Обычной производящей функции <tex dpi="350">\limits_frac{1}{n 1-t}</tex> соответствует считающая последовательность <tex dpi="350">\left \geqslant { 1, 1, ..., 1\right \}</tex>, поэтому <tex dpi="350">[t_n]\dfracfrac{1}{(1-z^t}=1</tex>.* <tex dpi="350">p_n=n!\cdot[t_n]p(t)=n!</tex> ==Урны==Кобинаторный класс "Урна" {{n---}})^множество, характеризующееся только количеством атомов в объекте, то есть элементов каждого веса {A_{n---}}<tex dpi="350">1</tex>, поэтому <tex dpi="350">a_n=1</tex>. Производящая функция этого класса {{---}}<tex dpi="350">edf(t)=\exp(sum_{n=0}^{\suminfty}\limits_frac{k 1\geqslant 1cdot t^n}{n!}=\dfracsum_{A(zn=0}^{k\infty})\frac{t^n}{kn!})=e^t</tex>. ==Множества== |-alignВ формализме помеченных объектов <tex dpi="center350">MSet=Set</tex>, потому что не бывает одинаковых элементов в множествах. !===Ограниченная конструкция=== {{Определение|definition=Ограниченным множеством <tex dpi="130350">PairA=Set_k(A,B)</tex>||назовём множество из <tex dpi="130350">Ak</tex> объектов (zпорядок не важен).}} Рассмотрим <tex dpi="350">\left \{ a_1, a_2, ..., a_k \right \} \in Set_k(B)</tex> и разобьем последовательности в <tex dpi="350">Seq_k(zB)</tex>на классы эквивалентности по признаку равенства множеств элементов в них. Каждому <tex dpi="350">Set_k(B)</tex> [[Отображения|-alignбиективно]] соответствует <tex dpi="center350" >k!</tex> последовательностей в <tex dpi="130350">CycleSeq_k(AB)</tex>||, потому что все объекты различны. <tex dpi="130350">Set_k(B)\sumcdot k!=Seq_k(B)</tex> <tex dpi="350">Set_k(B)(t)=A(t)=\limits_frac{n \geqslant 1left ( B \left ( t \right ) \right )^k}{k!}</tex> ===Неограниченная конструкция=== <tex dpi="350">A=Set(B)=\dfracsum_{k=0}^{\phiinfty}Set_k(nb)</tex> {{---}} множества объектов (порядок не важен). Ограничение <tex dpi="350">b_0=B(0)=0</tex> также действует. <tex dpi="350">Set(A)(t)=\sum_{nk=0}^{\lninfty}\dfracfrac{A(t)^k}{1k!}=e^{1 - A(z^nt)}</tex> Можно рассматривать <tex dpi="350">Set(A)</tex> как композицию урны и <tex dpi="350">A</tex>, другими словами, где можно вместо атомов в урне взять объекты класса <tex dpi="130350">\phiA</tex>. ==Циклы== ===Ограниченная конструкция=== {{Определение|definition=Цикл <tex dpi="350">A=Cycle_k(nB)</tex> {{---}} [[Функция_Эйлера | функция Эйлера]]ориентированная циклическая последовательность из <tex dpi="350">k</tex> объектов класса <tex dpi="350">B</tex>. Циклов нулевой длины <tex dpi="350">0</tex>, то есть, <tex dpi="350">c_0=0</tex>.|}}