Изменения

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

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

|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">Seq(A)\alpha</tex> существует ограничение на берется <tex dpi="350">A</tex>: <tex dpi="350">a_0=ASeq(0\{\alpha\})=0</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(AA_1+\{\alpha\})=MSet(A_1)+MSet(A_1)\times\{\alpha\}\times Seq_{\geq 1}(\prod_{\alpha \in A})=MSet(A_1)\cdot Seq(\left \{ \alpha \right \})</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">ogf(t) = \sum_{i=0}^{\infty}a_it^i</tex>, где <tex dpi="350">\left \{ a_i \right \}</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>}}

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

Действует ограничение на <tex dpi="350">b_0=B(0)=0n</tex> как и -тый член выражается следующим образом: <tex dpi="350">Seq(A)</tex> и в <tex dpib_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="350"Mset(A)>1}^{k}\frac{a_{t_i}}{t_i!}</tex> в мире непомеченных объектов.

Обозначаются Поэтому производящая функция {{---}} <tex dpi="350">Seq_kB(t)=\left (A\left (t\right ) \right )^k</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(t)=\left Seq( A\left (t\right ) \right )^k</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>. Циклов нулевой длины <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</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>. ===Неограниченная конструкция=== {{Определение|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чания=<references/> =Источники информации=*[https://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] [[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]