Изменения

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

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

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

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

{{Утверждение|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">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>.}} ====Пример:====

<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">Set(A)(t)=\prod_{\alpha </tex> берется <tex dpi="350">Seq(\in A}(1+t^{w(\alpha)})=\prod_{n=0}^{\infty}(1+t^n)^{a_n}</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)</tex> (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">Seq(A)</tex> существует ограничение на <tex dpiПомеченные объекты="350">A</tex>: <tex dpi="350">a_0=A(0)=0</tex>.

Как можно заметить, для некоторых операторов, например, <tex dpi="350">Set</tex> и <tex dpi="350">MSet(A)=\prod_{\alpha \in A}(Seq(\left \{ \alpha \right \}))</tex>не существует замкнутых формул, поэтому их объекты удобнее обозначать как помеченные. С помеченными объектами используется [https://en.wikipedia.org/wiki/Generating_function#Exponential_generating_function_(EGF) экспоненциальная производящая функция].

Напомним, что если <tex dpi="350">MSet(A)(t)=\prod_left \{a_i \alpha right \in A}\frac</tex> {1}{1-t^{w(\alpha)}}=\prod_{n=1}^{\infty}\left(\frac{1}{1-t^n-}\right)^{a_n}</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="130"350">S_{0} B(t)= 1\left ( A\left (t\right ) \right )^k</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"350">1Seq(A)</tex>не изменилось.

'''Переход'''. {{Утверждение:Пусть для |statement=<tex dpi="130"350">j < nSeq(A)(t)=\frac{1}{1 - A(t)}</tex> верно. Докажем для <tex dpi|proof="130"">n</tex>. Возьмем произвольный элемент из <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="wikitable" {Определение|-aligndefinition="center" !Цикл <tex dpi="130350">Seq(A)</tex>||<tex dpi="130">\dfrac{1}{1-ACycle_k(zB)}</tex>|-align="center" !<tex dpi="130">PSet(A)</tex>||<tex dpi="130">\prod\limits_{n \geqslant 1}(1+z^{n})^{A_{n}}=\exp(-\sum\limits_{k \geqslant 1}\dfrac{(-1)^{k}A(z^{k-})}{k})</tex>|-align="center" !<tex dpi="130">MSet(A)</tex>||ориентированная циклическая последовательность из <tex dpi="130350">\prod\limits_{n \geqslant 1}\dfrac{1}{(1-z^{n})^{A_{n}}}=\exp(\sum\limits_{k \geqslant 1}\dfrac{A(z^{k})}{k})</tex>|-align="center" !объектов класса <tex dpi="130350">Pair(A,B)</tex>||<tex dpi="130">A(z)B(z)</tex>.|-align="center" !Циклов нулевой длины <tex dpi="130350">Cycle(A)0</tex>||, то есть, <tex dpi="130350">\sum\limits_{n \geqslant 1}\dfrac{\phi(n)}{n}\ln\dfrac{1}{1 - A(z^n)}</tex>, где <tex dpic_0="130">\phi(n)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> {{---}} [[Функция_Эйлера | функция ЭйлераКатегория: Комбинаторика]].|}