Изменения

В комбинаторике, особенно в аналитической комбинаторике, [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>.=Базовые определения==

У атомов определен вес <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="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(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>.

Последовательностью ''(всех возможных длин)'' объектов из <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)=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> ==Комбинаторный класс "Натуральные числа"== Вес числа равен его значению. Каждое натуральное число встречается 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>}} ===Применение===

<tex dpi="350">Seq(I)</tex> {{----}} упорядоченное [[Нахождение количества разбиений числа на слагаемые|разбиение натуральных чисел на слагаемые]].

Такие большие группы часто анализируют с помощью <tex dpi="350">\left [[Производящая функция|производящих функций]t^n \right ]\frac{1-t}{1-2t} = \left\{\begin{matrix}2 ^ n - 2 ^ {n - 1} = 2 ^ {n - 1}, n > 0\\ 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=Множества <reftex dpi="350">[[wikipedia:Symbolic method Set(combinatoricsA) | Wikipedia </tex> {{---}} Symbolic method]]последовательности без повторений и порядка элементов.}}{{Утверждение|statement=<tex dpi="350">Set(A)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )</tex>|proof=Докажем по индукции по потенциальным элементам множеств <tex dpi="350">A</reftex>. Он использует внутреннюю структуру объектов  '''База''' <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)(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">\alpha</tex> берется <tex dpi="350">Seq(\{\alpha\})</tex> Пусть верно для мультимножества <tex dpi="350">A_1</tex>, считаетсядокажем, что нет объектов нулевого весабудет верно и для мультимножества и <tex dpi="350">A_1+Seq_{\geq1}(\{\alpha\})</tex>, где <tex dpi="350">\alpha\in A\setminus A_1</tex><tex dpi="350">MSet(A_1+\{\alpha\})=MSet(A_1)+MSet(A_1)\times\{\alpha\}\times Seq_{\geq 1}(\{\alpha \})=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"|-| Обычная || <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>|} Далее под производящей функцией будет подразумеваться и использоваться экспоненциальная производящая функция, потому что формулы с ней более просты в работе. ==Свойства экспоненциальной производящей функции==

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

<tex dpi="130350">n</tex>-тый член выражается следующим образом: <tex dpi="350">S_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}{0t_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="130"">n = 1</tex>'''. :<tex dpi="130"">S_{1}Неограниченная конструкция=w_{1} S_{0}=w_{1}</tex>, что верно, так как единственный способ составить последовательность веса <tex dpi="130"">1</tex> {{---}} это взять любой элемент веса <tex dpi="130"">1</tex>.

'''Переход'''. :Пусть для Определение <tex dpi="130"350">j < nSeq(A)</tex> верноне изменилось. Докажем для  {{Утверждение|statement=<tex dpi="130"350">nSeq(A)(t)=\frac{1}{1 - A(t)}</tex>. Возьмем произвольный элемент из |proof=<tex dpi="130"350">Seq(A</tex> веса <tex dpi)(t)="130"">\sum_{i =0}^{\leqslant n</tex>, и допишем его к последовательности элементов веса <tex dpiinfty}Seq_i(A)(t)="130"">n-\sum_{i</tex>. Образуется новая последовательность веса <tex dpi="130"">n</tex>. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса <tex dpi0}^{\infty}A(t)^i="130"">n\frac{1}{1 - A(t)}</tex> и ни к какой последовательности меньшего веса мы не добавляем один и тот же элемент дважды.(Геометрическая прогрессия)

{| class'''Перестановки'''* <tex dpi="wikitable350" >P=Seq(Z)</tex>|* Экспоненциальной производящей функцией является <tex dpi="350">P(t)=\frac{1}{1-alignt}</tex>.* Обычной производящей функции <tex dpi="center350" !>\frac{1}{1-t}</tex> соответствует считающая последовательность <tex dpi="130350">Seq(A)\left \{ 1, 1, ..., 1\right \}</tex>||, поэтому <tex dpi="130350">[t_n]\dfracfrac{1}{1-At}=1</tex>.* <tex dpi="350">p_n=n!\cdot[t_n]p(zt)}=n!</tex>|==Урны==Кобинаторный класс "Урна" {{---}} множество, характеризующееся только количеством атомов в объекте, то есть элементов каждого веса {{---align}} <tex dpi="center350" !>1</tex>, поэтому <tex dpi="130350">PSet(A)a_n=1</tex>||. Производящая функция этого класса {{---}} <tex dpi="130350">edf(t)=\prod\limits_sum_{n =0}^{\geqslant 1infty}(\frac{1+z\cdot t^{n})^{A_{n}!}=\exp(-\sum\limits_sum_{n=0}^{k \geqslant 1infty}\dfracfrac{(-1)t^n}{kn!}A(z=e^{k})}{k})t</tex>.|-align==Множества== В формализме помеченных объектов <tex dpi="center350">MSet=Set</tex>, потому что не бывает одинаковых элементов в множествах. ===Ограниченная конструкция=== {{Определение !|definition=Ограниченным множеством <tex dpi="130350">MSetA=Set_k(AB)</tex>||назовём множество из <tex dpi="130350">\prod\limits_{n \geqslant 1}\dfrac{1}{k</tex> объектов (1-z^{n}порядок не важен)^{A_{n}.}} Рассмотрим <tex dpi="350">\exp(left \sum{ a_1, a_2, ..., a_k \limits_{k right \geqslant 1}\dfrac{Ain Set_k(z^{k}B)}{k}</tex> и разобьем последовательности в <tex dpi="350">Seq_k(B)</tex>на классы эквивалентности по признаку равенства множеств элементов в них. Каждому <tex dpi="350">Set_k(B)</tex> [[Отображения|-alignбиективно]] соответствует <tex dpi="center350" >k!</tex> последовательностей в <tex dpi="130350">PairSeq_k(AB)</tex>,потому что все объекты различны. <tex dpi="350">Set_k(B)\cdot k!=Seq_k(B)</tex>|| <tex dpi="130350">Set_k(B)(t)=A(zt)=\frac{\left ( B\left (zt \right ) \right )^k}{k!}</tex>|-align===Неограниченная конструкция=== <tex dpi="center350">A=Set(B)=\sum_{k=0}^{\infty}Set_k(b)</tex> {{---}} множества объектов (порядок не важен). !Ограничение <tex dpi="130350">Cycleb_0=B(A0)=0</tex>||также действует. <tex dpi="130350">Set(A)(t)=\sum\limits_sum_{k=0}^{n \geqslant 1infty}\dfracfrac{\phiA(nt)^k}{nk!}\ln\dfrac=e^{1}{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>.|}}

Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, {{---}} помеченные графыУтверждение|statement=Каждому циклу <tex dpi="350">(b_1, b_2, ... С помеченными объектами используется экспоненциальная производящая функция , b_k)</tex> длины <tex dpi="350">k</tex> биективно соответствует <tex dpi="350">k<ref/tex>упорядоченных последовательностей ([[https://en.wikipedia:exponential generating function | Wikipedia {{---.org/wiki/Cyclic_permutation циклические перестановки] элементов цикла).}} Exponential generating function]]</ref>. В данном случае для некоторых рассмотренных классов используются следующие производящие функции:

{| class="wikitable" |-align="center" !<tex dpi="130">Seq(A)</tex>||<tex dpi="130">\dfrac{1}{1-A(z)}</tex>|-align="center" !Поэтому <tex dpi="130350">PsetSeq_k(A)</tex>||<tex dpi="130">k\exp(A(z))</tex>|-align="center" !<tex dpi="130">Pair(A,B)</tex>||<tex dpi="130">A(z)B(z)</tex>|-align="center" !<tex dpi="130">Cyclecdot Cycle_k(A)</tex>||<tex dpi="130">\ln\dfrac{1}{1-A(z)}</tex>.|}

===Ограниченные конструкции===Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (напримерЗначит, экспоненциальная производящая функция циклов {{---}} <tex dpi="130350">Seq_Cycle_k(A)(t)=\frac{k}Seq_k(A)</tex> (t)}{k}=\frac{---A(t)^k}{k} <tex dpi="130">k</tex> компонентов).

Непосредственной формулой для производящих функций является диагональ <tex dpi="130">\Delta</tex> декартова произведения <ref>[[wikipedia:Cartesian product | Wikipedia {{---}} Декартово произведение]]</ref> <tex dpi="130">A \times A</tex>, определяемая как <tex dpi="130">B \equiv \Delta(A \times A) : \{(a, a) \mid a \in A\}</tex>. Тогда имеет место соотношение <tex dpiНеограниченная конструкция=="130">B(z)=A(z^{2})</tex>.

Диагональная конструкция позволяет получить доступ к классу всех неупорядоченных пар из различных элементов из {{Определение|definition=Циклы <tex dpi="130350">A</tex>, то есть к <tex dpi="130">P Cycle(B)=\sum_{k= PSet_0}^{2\infty}Cycle_k(AB)</tex>. Прямое выражение выполняется следующим способом: неупорядоченная пара }}<tex dpi="130350">\langle \alpha, \beta \rangle </tex> связана с двумя упорядоченными парами <tex dpiCycle(A)(t)="130">(\langle \alpha, \beta \rangle </tex> и <tex dpisum_{k="130">0}^{\langle \beta, \alpha \rangle infty}Cycle_k(A)(t)</tex>, кроме тех случаев, когда <tex dpi="130">0+\alpha sum_{k= 1}^{\infty}\beta</tex>, то есть когда пара лежит на диагонали декартова произведения. Другими словами, <tex dpi="130">PSet_frac{2}A(At) + PSet_^k}{2k}=-ln \left (1+\left (-A(t)\right ) \right ) + =-ln \Deltaleft (1-A (t) \times Aright ) =ln\left (\cong frac{1}{1-A (t)}\times Aright )</tex>.(Разложение натурального логарифма в ряд Тейлора)

Это, в свою очередь, означает что <tex dpi="130">2P(z) + A(z^{2}) = A(z)^{2}</tex>См. Таким образом можно выразить <tex dpiтакже="130">PSet_{2}(A)</tex>. Аналогично для <tex dpi="130">Seq_{2}(A)</tex>, <tex dpi="130">MSet_{2}(A)</tex> *[[Конструирование комбинаторных объектов и их подсчёт]]*[[Функция Эйлера]]*[[Лемма Бёрнсайда и <tex dpi="130">Cycle_{2}(A)</tex>:Теорема Пойа]]*[[Задача об ожерельях]]*[[Числа Каталана]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]*[[Подсчет деревьев]]

{| class="wikitable" |-align="center" !<tex dpi="130">Seq_{2}(A)</tex>||<tex dpi="130>A(z)^{2}</tex>|-align="center" !<tex dpi="130">PSet_{2}(A)</tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}-\dfrac{A(z^{2})}{2}</tex>|-align="center" !<tex dpi="130">MSet_{2}(A)</tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}</tex>|-alignПримeчания="center" !<tex dpi="130">Cycle_{2}(A)<references/tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}</tex>|}

Аналогичные рассуждения можно провести и для больших <tex dpi="130">k<Источники информации=*[https:/tex>/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].

Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа <ref>[[wikipediaКатегория:Lagrange inversion theorem | Wikipedia {{---}} Lagrange inversion theorem]]</ref>. В общем случае, используя метод символов, производящие функции ограниченных конструкций можно подсчитать следующим способом: {| class="wikitable" |-align="center" !<tex dpi="130">Seq_{k}(A)</tex>||<tex dpi="130">A(z)^{k}</tex>|-align="center" !<tex dpi="130">PSet_{k}(A)</tex>||<tex dpi="130">[u^{k}Дискретная математика и алгоритмы]\exp(-\sum\limits_{i=1}^{k}\dfrac{(-1)^{i}u^{i}A(z^{i})}{i})</tex>|-align="center" !<tex dpi="130">MSet_{k}(A)</tex>||<tex dpi="130">[u^{k}]\exp(\sum\limits_{i=1}^{k}\dfrac{u^{i}A(z^{i})}{i})</tex>|-align="center" !<tex dpi="130">Cycle_{k}(A)</tex>||<tex dpi="130">[u^{k}]\sum\limits_{i \geqslant 1}\dfrac{\phi(i)}{i}\ln\dfrac{1}{1 - u^{i}A(z^i)}</tex>, где <tex dpi="130">\phi(n)</tex> {{---}} [[Функция_Эйлера | функция ЭйлераКатегория: Комбинаторика]].|}