Обсуждение:Метод производящих функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (progress...)
 
(не показано 140 промежуточных версий 3 участников)
Строка 1: Строка 1:
=Метод производящих функций=
+
В комбинаторике, особенно в аналитической комбинаторике, [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</tex>. Вес объектов равен сумме весов составляющих его атомов.
  
<tex dpi="130">w(\bullet)=1</tex>
+
{{Определение
 +
|definition=
 +
Считающей последовательностью называется последовательность <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}</tex>, где <tex dpi="130">a_i</tex> {{---}} количество объектов веса <tex dpi="130">i</tex>.
 +
}}
  
<tex dpi="130">w(\circ)=0</tex>
+
Обозначим <tex dpi="350">[t_n]</tex> как оператор взятия <tex dpi="350">n</tex>-того коэффициента производящей функции.
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Считающей последовательностью называется последовательность <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}</tex>, где <tex dpi="130">a_i</tex> {{---}} количество объектов веса <tex dpi="130">i</tex>.
+
Комбинаторным классом <tex dpi="130">A</tex> называется множество комбинаторных объектов, обладающих каким-то свойством.
 
}}
 
}}
  
Производящую функцию класса <tex dpi="130">A</tex> обозначим <tex dpi="130">A(t)=\sum_{i=0}^{\infty }a_i t^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> {{---}} считающая последовательность этого класса.
  
 
{{Определение
 
{{Определение
Строка 26: Строка 38:
  
 
Считающая последовательность: <tex dpi="130">\left \{ 0, 1, 0, ..., 0 \right \}</tex>.
 
Считающая последовательность: <tex dpi="130">\left \{ 0, 1, 0, ..., 0 \right \}</tex>.
 
  
 
Производящая функция последовательности: <tex dpi="130">Z(t)=t</tex>.
 
Производящая функция последовательности: <tex dpi="130">Z(t)=t</tex>.
Строка 39: Строка 50:
 
Считающая последовательность: <tex dpi="130">\left \{ 1, 0, ..., 0 \right \}</tex>.
 
Считающая последовательность: <tex dpi="130">\left \{ 1, 0, ..., 0 \right \}</tex>.
  
 +
Производящая функция последовательности: <tex dpi="130">\varepsilon(t)=1</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</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>
 +
 
 +
==Пары комбинаторных классов (декартово произведение комбинаторных классов)==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Комбинаторным классом <tex dpi="130">A</tex> называется множество комбинаторных объектов, обладающих каким-то свойством.
+
Парой комбинаторных классов <tex dpi="350">A</tex> и <tex dpi="350">B</tex> называется комбинаторный класс <tex dpi="350">C=Pair(A, B)=A \times B=\left \{ (\alpha, \beta) \mid \alpha \in A, \beta \in B \right \}</tex>.
 +
}}
 +
 
 +
<tex dpi="350">w\left ( \left ( \alpha, \beta \right ) \right )=w(\alpha) + w(\beta)</tex>
 +
 
 +
<tex dpi="350">c_n=\sum_{k=0}^{n}a_k b_{n-k}</tex>
 +
 
 +
{{Утверждение
 +
|statement=<tex dpi="350">C(t)=A(t) \cdot B(t)</tex><ref>[[Арифметические действия с формальными степенными рядами]]</ref>
 
}}
 
}}
  
===Объединение комбинаторных классов===
+
==Последовательности комбинаторных классов==
 +
 
 +
===Ограниченная конструкция===
  
 
{{Определение
 
{{Определение
 
|definition=
 
|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">k</tex> объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq_k(A)=\left \{ (\alpha_1, ...,  \alpha_k) \mid \alpha_i \in A \right \}</tex>.
 +
 
 +
<tex dpi="350">w(\left \{ (\alpha_1, ...,  \alpha_k) \mid \alpha_i \in A \right \})=\sum_{i=0}^{k}\alpha_i</tex>
 
}}
 
}}
  
При объединении комбинаторных классов одинаковые объекты разных классов считаются разными. Это делается так, чтобы не рассматривать внутреннюю структуру классов, а работать только со считающими последовательностями и производящими функциями.
 
  
<tex dpi="350">c_n=a_n+b_n</tex>
+
{{Утверждение
 +
|statement=<tex dpi="350">Seq_k(A)(t)=A(t)^k</tex>
 +
|proof=Докажем по индукции:
  
<tex dpi="350">C(t)=A(t)+B(t)</tex>
+
'''База <tex dpi="350">k=1</tex>'''.
 +
:Для <tex dpi="350">k=1</tex> верно, потому что <tex dpi="350">Seq_1(A)=A \Rightarrow Seq_1(A)(t)=A(t)=A(t)^1</tex>.
  
 +
'''Переход'''.
 +
:Пусть для <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=
 
|definition=
Парой комбинаторных классов <tex dpi="350">A</tex> и <tex dpi="350">B</tex> называется комбинаторный класс <tex dpi="350">C=Pair(A, B)=A \times B=\left \{ (\alpha, \beta) \mid \alpha \in A, \beta \in B \right \}</tex>.
+
Последовательностью объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)</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">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>
 +
}}
 +
 
 +
===Применение===
 +
 
 +
<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>
 +
 
 +
<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=Множества <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">w\left ( \left ( \alpha, \beta \right ) \right )=w(\alpha) + w(\beta)</tex>
+
'''База'''
 +
 
 +
<tex dpi="350">A=\varnothing</tex>
 +
 
 +
<tex dpi="350">Set(\varnothing)=\varepsilon=\prod_{\alpha\in A}\varepsilon</tex>
  
<tex dpi="350">c_n=\sum_{k=0}^{n}a_k b_{n-k}</tex>
+
'''Переход'''
  
<tex dpi="350">C(t)=A(t) \cdot B(t)</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=
+
|definition=Мультимножества <tex dpi="350">MSet(A)</tex> {{---}} последовательности с повторениями, но без порядка элементов.
Последовательностью <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq_k(A)=\left \{ (\alpha_1, ...,  \alpha_k) \mid \alpha_i \in A \right \}</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">w(\left \{ (\alpha_1, ...,  \alpha_k) \mid \alpha_i \in A \right \})=\sum_{i=0}^{k}\alpha_i</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>
 +
|}
  
 +
Далее под производящей функцией будет подразумеваться и использоваться экспоненциальная производящая функция, потому что формулы с ней более просты в работе.
  
Такие большие группы часто анализируют с помощью [[Производящая функция|производящих функций]]. Один из популярных методов {{---}} метод символов <ref>[[wikipedia:Symbolic method (combinatorics) | Wikipedia {{---}} Symbolic method]]</ref>. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества.
+
==Свойства экспоненциальной производящей функции==
  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
<tex dpi="150">Seq(A)(t)=\frac{1}{1-A(t)}</tex>.
+
Пусть <tex dpi="350">A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">\{ a_0, a_1, ..., a_n, ... \}</tex>, тогда <tex dpi="350">A'(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">B=\{ a_1, a_2, ..., a_n, ... \}</tex>
 
|proof=
 
|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="350">c_n=\sum_{k=0}^na_k\sum_{t_1+t_2+...+t_k=n}\binom{n}{t_1, t_2, ..., t_n}\cdot b_{t_1} b_{t_2}\cdot...\cdot b_{t_n}</tex>
 +
}}
 +
 +
==Помеченные объекты==
 +
 +
Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки; Если вес объекта равен <tex dpi="350">n</tex>, то все атомы пронумерованы различными целыми числами от <tex dpi="350">1</tex> до <tex dpi="350">n</tex>.
 +
 +
<tex dpi="130">w(①)=1</tex>
 +
 +
<tex dpi="130">w(\circ)=0</tex>
 +
 +
{{Определение
 +
|definition=
 +
Комбинаторным объектом <tex dpi="130">Z</tex> называется комбинаторный объект, состоящий из одного атома веса <tex dpi="130">1</tex>.
 +
 +
<tex dpi="130">Z=\left \{ ① \right \}</tex>
 +
 +
<tex dpi="130">Z(t)=t</tex>
 +
}}
 +
{{Определение
 +
|definition=
 +
Комбинаторным объектом <tex dpi="130">\varepsilon</tex> называется комбинаторный объект, состоящий из одного атома веса <tex dpi="130">0</tex>.
 +
 +
<tex dpi="130">\varepsilon=\left \{ \circ \right \}</tex>
 +
 +
<tex dpi="130">\varepsilon(t)=1</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|50px]] <tex dpi="350">\}</tex>.
 +
 +
Тогда пара <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:1-2-3.png|50px]]<tex dpi="350">)</tex> будет иметь вес 5, но атомы не будут иметь различные пометки от 1 до 5.
 +
 +
Поэтому введем оператор <tex dpi="350">A \star B</tex>, который
 +
# Перебирает все пары из <tex dpi="350">A</tex> и <tex dpi="350">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}=\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">C(t)=A(t) \cdot B(t)</tex>
 +
 +
==Последовательности комбинаторных классов==
 +
 +
===Ограниченная конструкция===
 +
 +
Последовательности длины <tex dpi="350">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом:
 +
* Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex>
 +
* Перенумеруются всеми возможными способами.
 +
 +
Их принято обозначать <tex dpi="350">Seq_k(A)</tex>.
 +
 +
<tex dpi="350">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(t)=\left ( A\left (t\right ) \right )^k</tex>
 +
 +
===Неограниченная конструкция===
 +
 +
Определение <tex dpi="350">Seq(A)</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="130"">S_{0} = 1</tex>, так как есть единственный способ составить пустую последовательность.
+
====Пример====
  
Докажем по индукции.
+
'''Перестановки'''
 +
* <tex dpi="350">P=Seq(Z)</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">[t_n]\frac{1}{1-t}=1</tex>.
 +
* <tex dpi="350">p_n=n!\cdot[t_n]p(t)=n!</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="350">1</tex>, поэтому <tex dpi="350">a_n=1</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>.
:Пусть для <tex dpi="130"">j < n</tex> верно. Докажем для <tex dpi="130"">n</tex>. Возьмем произвольный элемент из <tex dpi="130"">A</tex> веса <tex dpi="130"">i \leqslant  n</tex>, и допишем его к последовательности элементов веса <tex dpi="130"">n-i</tex>. Образуется новая последовательность веса <tex dpi="130"">n</tex>. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса <tex dpi="130"">n</tex> и ни к какой последовательности меньшего веса мы не добавляем один и тот же элемент дважды.
+
 
 +
==Множества==
 +
 
 +
В формализме помеченных объектов <tex dpi="350">MSet=Set</tex>, потому что не бывает одинаковых элементов в множествах.
 +
 
 +
===Ограниченная конструкция===
 +
 
 +
{{Определение
 +
|definition=Ограниченным множеством <tex dpi="350">A=Set_k(B)</tex> назовём множество из <tex dpi="350">k</tex> объектов (порядок не важен).
 
}}
 
}}
  
 +
Рассмотрим <tex dpi="350">\left \{ a_1, a_2, ..., a_k \right \} \in Set_k(B)</tex> и разобьем последовательности в <tex dpi="350">Seq_k(B)</tex> на классы эквивалентности по признаку равенства множеств элементов в них.
  
При непомеченных объектах рассмотренные классы имеют следующие производящие функции:
+
Каждому <tex dpi="350">Set_k(B)</tex> [[Отображения|биективно]] соответствует <tex dpi="350">k!</tex> последовательностей в <tex dpi="350">Seq_k(B)</tex>, потому что все объекты различны.
  
{| class="wikitable"  
+
<tex dpi="350">Set_k(B)\cdot k!=Seq_k(B)</tex>
|-align="center"
+
 
!<tex dpi="130">Seq(A)</tex>||<tex dpi="130">\dfrac{1}{1-A(z)}</tex>
+
<tex dpi="350">Set_k(B)(t)=A(t)=\frac{\left ( B \left ( t \right ) \right )^k}{k!}</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="130">\prod\limits_{n \geqslant 1}\dfrac{1}{(1-z^{n})^{A_{n}}}=\exp(\sum\limits_{k \geqslant 1}\dfrac{A(z^{k})}{k})</tex>
+
<tex dpi="350">A=Set(B)=\sum_{k=0}^{\infty}Set_k(b)</tex> {{---}} множества объектов (порядок не важен).
|-align="center"
+
 
!<tex dpi="130">Pair(A,B)</tex>||<tex dpi="130">A(z)B(z)</tex>
+
Ограничение <tex dpi="350">b_0=B(0)=0</tex> также действует.
|-align="center"
+
 
!<tex dpi="130">Cycle(A)</tex>||<tex dpi="130">\sum\limits_{n \geqslant 1}\dfrac{\phi(n)}{n}\ln\dfrac{1}{1 - A(z^n)}</tex>, где <tex dpi="130">\phi(n)</tex> {{---}} [[Функция_Эйлера | функция Эйлера]].
+
<tex dpi="350">Set(A)(t)=\sum_{k=0}^{\infty}\frac{A(t)^k}{k!}=e^{A(t)}</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>.
 +
}}
  
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, {{---}} помеченные графы. С помеченными объектами используется экспоненциальная производящая функция <ref>[[wikipedia:exponential generating function | Wikipedia {{---}} Exponential generating function]]</ref>. В данном случае для некоторых рассмотренных классов используются следующие производящие функции:
+
{{Утверждение
 +
|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 циклические перестановки] элементов цикла).
 +
}}
  
{| class="wikitable"
+
Поэтому <tex dpi="350">Seq_k(A) = k\cdot Cycle_k(A)</tex>
|-align="center"
 
!<tex dpi="130">Seq(A)</tex>||<tex dpi="130">\dfrac{1}{1-A(z)}</tex>
 
|-align="center"
 
!<tex dpi="130">Pset(A)</tex>||<tex dpi="130">\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">Cycle(A)</tex>||<tex dpi="130">\ln\dfrac{1}{1-A(z)}</tex>.
 
|}
 
  
===Ограниченные конструкции===
+
Значит, экспоненциальная производящая функция циклов {{---}} <tex dpi="350">Cycle_k(A)(t)=\frac{Seq_k(A)(t)}{k}=\frac{A(t)^k}{k}</tex>.
Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (например, <tex dpi="130">Seq_{k}(A)</tex> {{---}} <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>.
+
===Неограниченная конструкция===
  
Диагональная конструкция позволяет получить доступ к классу всех неупорядоченных пар из различных элементов из <tex dpi="130">A</tex>, то есть к <tex dpi="130">P = PSet_{2}(A)</tex>. Прямое выражение выполняется следующим способом: неупорядоченная пара <tex dpi="130">\langle \alpha, \beta \rangle </tex> связана с двумя упорядоченными парами <tex dpi="130">(\langle \alpha, \beta \rangle </tex> и <tex dpi="130">\langle \beta, \alpha \rangle )</tex>, кроме тех случаев, когда <tex dpi="130">\alpha = \beta</tex>, то есть когда пара лежит на диагонали декартова произведения. Другими словами, <tex dpi="130">PSet_{2}(A) + PSet_{2}(A) + \Delta(A \times A) \cong A \times A</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> (Разложение натурального логарифма в ряд Тейлора)
  
Это, в свою очередь, означает что <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"
+
=Примeчания=
|-align="center"
+
<references/>
!<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="center"
 
!<tex dpi="130">Cycle_{2}(A)</tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}</tex>
 
|}
 
  
Аналогичные рассуждения можно провести и для больших <tex dpi="130">k</tex>, однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов {{---}} [[Лемма Бёрнсайда и Теорема Пойа#Теорема Пойа | теорема Пойа]].
+
=Источники информации=
 +
*[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]
  
Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа <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> {{---}} [[Функция_Эйлера | функция Эйлера]].
 
|}
 

Текущая версия на 22:29, 20 августа 2020

В комбинаторике, особенно в аналитической комбинаторике, символьный метод - это метод подсчета комбинаторных объектов. Он использует внутреннюю структуру объектов для получения формул их производящих функций. Этот метод в основном связан с Филиппом Флайоле и подробно описан в части A его книги с Робертом Седжвиком "Аналитическая комбинаторика"[1].


Содержание

Базовые определения

Каждый комбинаторный объект состоит из атомов.

У атомов определен вес [math]w[/math]. Вес объектов равен сумме весов составляющих его атомов.


Определение:
Считающей последовательностью называется последовательность [math]\left \{ a_0, a_1, ..., a_n \right \}[/math], где [math]a_i[/math] — количество объектов веса [math]i[/math].


Обозначим [math][t_n][/math] как оператор взятия [math]n[/math]-того коэффициента производящей функции.


Определение:
Комбинаторным классом [math]A[/math] называется множество комбинаторных объектов, обладающих каким-то свойством.


Непомеченные комбинаторные объекты

Введём атомы [math]\bullet[/math] и [math]\circ[/math] следующим образом:

[math]w(\bullet)=1[/math]

[math]w(\circ)=0[/math]

Производящую функцию класса [math]A[/math] обозначим [math]A(t)=\sum_{i=0}^{\infty }a_i t^i[/math], если [math]\{a_i\}[/math] — считающая последовательность этого класса.


Определение:
Комбинаторным объектом [math]Z[/math] называется комбинаторный объект, состоящий из одного атома веса [math]1[/math]. [math]Z=\left \{ \bullet \right \}[/math]


Считающая последовательность: [math]\left \{ 0, 1, 0, ..., 0 \right \}[/math].

Производящая функция последовательности: [math]Z(t)=t[/math].


Определение:
Комбинаторным объектом [math]\varepsilon[/math] называется комбинаторный объект, состоящий из одного атома веса [math]0[/math]. [math]\varepsilon=\left \{ \circ \right \}[/math].


Считающая последовательность: [math]\left \{ 1, 0, ..., 0 \right \}[/math].

Производящая функция последовательности: [math]\varepsilon(t)=1[/math].

Объединение комбинаторных классов

Определение:
Объединением комбинаторных классов [math]A[/math] и [math]B[/math] называется комбинаторный класс [math]C=A \cup B=A+B[/math], состоящий из элементов обоих классов, причем равные объекты разных классов объявляются разными.

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

[math]c_n=a_n+b_n[/math]

[math]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)[/math]

Пары комбинаторных классов (декартово произведение комбинаторных классов)

Определение:
Парой комбинаторных классов [math]A[/math] и [math]B[/math] называется комбинаторный класс [math]C=Pair(A, B)=A \times B=\left \{ (\alpha, \beta) \mid \alpha \in A, \beta \in B \right \}[/math].


[math]w\left ( \left ( \alpha, \beta \right ) \right )=w(\alpha) + w(\beta)[/math]

[math]c_n=\sum_{k=0}^{n}a_k b_{n-k}[/math]

Утверждение:
[math]C(t)=A(t) \cdot B(t)[/math][2]

Последовательности комбинаторных классов

Ограниченная конструкция

Определение:
Последовательностью [math]k[/math] объектов из [math]A[/math] называется [math]B=Seq_k(A)=\left \{ (\alpha_1, ..., \alpha_k) \mid \alpha_i \in A \right \}[/math]. [math]w(\left \{ (\alpha_1, ..., \alpha_k) \mid \alpha_i \in A \right \})=\sum_{i=0}^{k}\alpha_i[/math]


Утверждение:
[math]Seq_k(A)(t)=A(t)^k[/math]
[math]\triangleright[/math]

Докажем по индукции:

База [math]k=1[/math].

Для [math]k=1[/math] верно, потому что [math]Seq_1(A)=A \Rightarrow Seq_1(A)(t)=A(t)=A(t)^1[/math].

Переход.

Пусть для [math]k=n[/math] верно [math]Seq_n(A)(t)=A(t)^n[/math]. Докажем для [math]k=n+1[/math]:
[math]Seq_{n+1}(A)(t)=A(t)^{n+1}[/math]. Рассмотрим [math]Seq_{n+1}(A)[/math] как [math]Pair(Seq_n(A), A)[/math]. Тогда [math]Seq_{n+1}(A)(t)=A(t)^n \cdot A(t)=A(t)^{n+1}[/math].
[math]\triangleleft[/math]

Неограниченная конструкция

Определение:
Последовательностью объектов из [math]A[/math] называется [math]B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)[/math].


Утверждение:
[math]Seq(A)(t)=\frac{1}{1 - A(t)}[/math]
[math]\triangleright[/math]
[math]Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}[/math] (Геометрическая прогрессия)
[math]\triangleleft[/math]


Ограничение: [math]a_0=0[/math] (также можно встретить [math]A_0=0[/math]). Этому есть как техническое, так и комбинаторное объяснение.

  • Технически, если [math]a_0\gt 1[/math], то мы будем делить на отрицательное число; если [math]a_0=1[/math], то на функцию, у которой свободный член [math]0[/math], — что формализм производящих функций сделать не позволяет.
  • Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.

Примеры

  • Последовательности из не менее, чем 3 объектов:
    • [math]Seq_{\geq 3}=Pair(Seq_3(A), Seq(A))=Seq(A)-Seq_0(A)-Seq_1(A)-Seq_2(A)[/math]
    • [math]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[/math]
  • Последовательности чётной длины:
    • [math]Seq_{\vdots 2}(A)=Seq(Pair(A, A))[/math]
    • [math]Seq_{\vdots 2}(A)(t)=Seq(Pair(A, A))(t)=\frac{1}{1-A\left (t^2\right )}[/math]

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

Вес числа равен его значению. Каждое натуральное число встречается 1 раз.

Считающая последовательность: [math]\left \{ 0, 1, ..., 1 \right \}[/math]

[math]w(n)=n[/math]

Класс "Натуральные числа" принято обозначать [math]I[/math]. Считающая последовательность — [math]c_n=\left\{\begin{matrix} 0, n=0\\ 1, n\gt 0 \end{matrix}\right.[/math]

Утверждение:
[math]I(t)=\frac{t}{1 - t}[/math]
[math]\triangleright[/math]

Производящей функцией последовательности из [math]1[/math] явлется [math]Seq(\{1\})=\frac{1}{1-t}[/math].

Чтобы получить производящую функцию класса натуральных чисел, произведем сдвиг вправо по правилам работы со степенными рядами:

[math]t \cdot I(t) = t \cdot \frac{1}{1 - t} = \frac{t}{1-t}[/math]
[math]\triangleleft[/math]

Применение

[math]Seq(I)[/math] — упорядоченное разбиение натуральных чисел на слагаемые.

Тогда производящая функция — [math]Seq(I)(t)=\frac{1}{1-\frac{t}{1-t}}=\frac{1-t}{1-2t}=\frac{1}{1-2t}-\frac{t}{1-2t}[/math]

[math]\left [ t^n \right ] \frac{1-t}{1-2t} = \left\{\begin{matrix} 2 ^ n - 2 ^ {n - 1} = 2 ^ {n - 1}, n \gt 0 \\ 1, n = 0 \end{matrix}\right.[/math], потому что [math]\frac{1}{1-2t}[/math] соответсвует ряду степеней [math]2[/math], а [math]\frac{1}{1-2t}[/math] — ряду [math]2^{x-1}[/math].

Множества

Определение:
Множества [math]Set(A)[/math] — последовательности без повторений и порядка элементов.
Утверждение:
[math]Set(A)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )[/math]
[math]\triangleright[/math]

Докажем по индукции по потенциальным элементам множеств [math]A[/math].

База

[math]A=\varnothing[/math]

[math]Set(\varnothing)=\varepsilon=\prod_{\alpha\in A}\varepsilon[/math]

Переход

Пусть верно для множества [math]A_1[/math], докажем, что будет верно и для множества и [math]A_1+\{\alpha\}[/math], где [math]\alpha\in A\setminus A_1[/math]

В множестве каждый элемент может либо присутствовать, либо отсутствовать, поэтому [math]Set(A_1+\{\alpha\})=Set(A_1)+Set(A_1)\times\{\alpha\}=Set(A_1)(\varepsilon + \alpha)[/math].
[math]\triangleleft[/math]

Пример

  • [math]A = \left \{ \alpha, \beta, \gamma \right \}[/math]
  • [math]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 \}[/math]

[math]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}[/math]

Мультимножества

Определение:
Мультимножества [math]MSet(A)[/math] — последовательности с повторениями, но без порядка элементов.

Как и с [math]Seq(A)[/math] существует ограничение на [math]A[/math]: [math]a_0=A(0)=0[/math].

Утверждение:
[math]MSet(A)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})[/math]
[math]\triangleright[/math]

Докажем по индукции по потенциальным элементам множеств [math]A[/math].

База

[math]A=\varnothing[/math]

[math]MSet(\varnothing)=\varepsilon=\prod_{\alpha\in A}\varepsilon[/math]

Переход

Отличие от множеств в том, что здесь каждый элемент может присутствовать в любом неотрицательном количестве экземпляров, поэтому для каждого элемента [math]\alpha[/math] берется [math]Seq(\{\alpha\})[/math]

Пусть верно для мультимножества [math]A_1[/math], докажем, что будет верно и для мультимножества и [math]A_1+Seq_{\geq1}(\{\alpha\})[/math], где [math]\alpha\in A\setminus A_1[/math]

[math]MSet(A_1+\{\alpha\})=MSet(A_1)+MSet(A_1)\times\{\alpha\}\times Seq_{\geq 1}(\{\alpha \})=MSet(A_1)\cdot Seq(\{\alpha\})[/math].
[math]\triangleleft[/math]

[math]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}[/math]

Помеченные объекты

Как можно заметить, для некоторых операторов, например, [math]Set[/math] и [math]MSet[/math] не существует замкнутых формул, поэтому их объекты удобнее обозначать как помеченные. С помеченными объектами используется экспоненциальная производящая функция.

Напомним, что если [math]\left \{ a_i \right \}[/math] — считающая последовательность, то производящие функции выражаются следующим образом:

Обычная [math]ogf(t) = \sum_{i=0}^{\infty}a_it^i[/math]
Экспоненциальная [math]egf(t) = \sum_{i=0}^{\infty}\frac{a_it^i}{n!}[/math]

Далее под производящей функцией будет подразумеваться и использоваться экспоненциальная производящая функция, потому что формулы с ней более просты в работе.

Свойства экспоненциальной производящей функции

Утверждение:
Пусть [math]A(t)[/math] — экспоненциальная производящая функция последовательности [math]\{ a_0, a_1, ..., a_n, ... \}[/math], тогда [math]A'(t)[/math] — экспоненциальная производящая функция последовательности [math]B=\{ a_1, a_2, ..., a_n, ... \}[/math]
[math]\triangleright[/math]
[math]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)[/math]
[math]\triangleleft[/math]
Утверждение:
[math]\left (\int A(t) \right )'=A(t)[/math][3]
Утверждение:
Пусть [math]A(t)[/math] — экспоненциальная производящая функция последовательности [math]\{ a_0, a_1, ..., a_n, ... \}[/math], тогда [math]\int A(t)[/math] — экспоненциальная производящая функция последовательности [math]B=\{ 0, a_0, a_1, a_2, ..., a_n, ... \}[/math][4]


Утверждение:
С точки зрения комбинаторики композиция производящих функций [math]A[/math] и [math]B[/math] означает подстановку вместо каждого возможного атома в [math]A[/math] всех объектов из класса [math]B[/math].

[math]A \left ( B \left ( t \right ) \right )=\sum_{n=0}^{\infty}\frac{B(t)^n\cdot a_n}{n!}[/math]

[math]c_n=\sum_{k=0}^na_k\sum_{t_1+t_2+...+t_k=n}\binom{n}{t_1, t_2, ..., t_n}\cdot b_{t_1} b_{t_2}\cdot...\cdot b_{t_n}[/math]

Помеченные объекты

Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки; Если вес объекта равен [math]n[/math], то все атомы пронумерованы различными целыми числами от [math]1[/math] до [math]n[/math].

[math]w(①)=1[/math]

[math]w(\circ)=0[/math]


Определение:
Комбинаторным объектом [math]Z[/math] называется комбинаторный объект, состоящий из одного атома веса [math]1[/math].

[math]Z=\left \{ ① \right \}[/math]

[math]Z(t)=t[/math]


Определение:
Комбинаторным объектом [math]\varepsilon[/math] называется комбинаторный объект, состоящий из одного атома веса [math]0[/math].

[math]\varepsilon=\left \{ \circ \right \}[/math]

[math]\varepsilon(t)=1[/math]


Объединение комбинаторных классов

Одинаковых объектов также нет, мы ставим разные метки на одинаковые объекты из разных классов, чтобы сделать их различными.

[math]c_n=a_n+b_n[/math]

[math]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)[/math]


Пары комбинаторных классов (декартово произведение комбинаторных классов)

Декартово произведение, определенное для непомеченных объектов, нам не даст корректный комбинаторный объект.

Пусть [math]A= \{[/math] 1-2.png [math]\}[/math], [math]B= \{[/math] 1-2-3.png [math]\}[/math].

Тогда пара [math]([/math] 1-2.png [math],[/math]1-2-3.png[math])[/math] будет иметь вес 5, но атомы не будут иметь различные пометки от 1 до 5.

Поэтому введем оператор [math]A \star B[/math], который

  1. Перебирает все пары из [math]A[/math] и [math]B[/math].
  2. В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе [math]A \star B[/math] будет лежать [math]([/math] 1-2.png [math],[/math]3-4-5.png[math])[/math], но не будет лежать [math]([/math] 1-2.png [math],[/math]3-5-4.png[math])[/math].

[math]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!}\frac{b_{n-k}}{(n-k)!}[/math]

[math]C(t)=A(t) \cdot B(t)[/math]

Последовательности комбинаторных классов

Ограниченная конструкция

Последовательности длины [math]k[/math], как и в непомеченных комбинаторных объектах, формируются следующим образом:

  • Cоставляются все возможные последовательности из [math]k[/math] объектов из [math]A[/math]
  • Перенумеруются всеми возможными способами.

Их принято обозначать [math]Seq_k(A)[/math].

[math]n[/math]-тый член выражается следующим образом: [math]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!}[/math]

Поэтому производящая функция — [math]B(t)=\left ( A\left (t\right ) \right )^k[/math]

Неограниченная конструкция

Определение [math]Seq(A)[/math] не изменилось.

Утверждение:
[math]Seq(A)(t)=\frac{1}{1 - A(t)}[/math]
[math]\triangleright[/math]
[math]Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}[/math] (Геометрическая прогрессия)
[math]\triangleleft[/math]

Действует ограничение на [math]b_0=B(0)=0[/math], как и на [math]Seq(A)[/math] и [math]MSet(A)[/math] в формализме непомеченных объектов.

Пример

Перестановки

  • [math]P=Seq(Z)[/math]
  • Экспоненциальной производящей функцией является [math]P(t)=\frac{1}{1-t}[/math].
  • Обычной производящей функции [math]\frac{1}{1-t}[/math] соответствует считающая последовательность [math]\left \{ 1, 1, ..., 1\right \}[/math], поэтому [math][t_n]\frac{1}{1-t}=1[/math].
  • [math]p_n=n!\cdot[t_n]p(t)=n![/math]

Урны

Кобинаторный класс "Урна" — множество, характеризующееся только количеством атомов в объекте, то есть элементов каждого веса — [math]1[/math], поэтому [math]a_n=1[/math].

Производящая функция этого класса — [math]edf(t)=\sum_{n=0}^{\infty}\frac{1\cdot t^n}{n!}=\sum_{n=0}^{\infty}\frac{t^n}{n!}=e^t[/math].

Множества

В формализме помеченных объектов [math]MSet=Set[/math], потому что не бывает одинаковых элементов в множествах.

Ограниченная конструкция

Определение:
Ограниченным множеством [math]A=Set_k(B)[/math] назовём множество из [math]k[/math] объектов (порядок не важен).


Рассмотрим [math]\left \{ a_1, a_2, ..., a_k \right \} \in Set_k(B)[/math] и разобьем последовательности в [math]Seq_k(B)[/math] на классы эквивалентности по признаку равенства множеств элементов в них.

Каждому [math]Set_k(B)[/math] биективно соответствует [math]k![/math] последовательностей в [math]Seq_k(B)[/math], потому что все объекты различны.

[math]Set_k(B)\cdot k!=Seq_k(B)[/math]

[math]Set_k(B)(t)=A(t)=\frac{\left ( B \left ( t \right ) \right )^k}{k!}[/math]

Неограниченная конструкция

[math]A=Set(B)=\sum_{k=0}^{\infty}Set_k(b)[/math] — множества объектов (порядок не важен).

Ограничение [math]b_0=B(0)=0[/math] также действует.

[math]Set(A)(t)=\sum_{k=0}^{\infty}\frac{A(t)^k}{k!}=e^{A(t)}[/math]

Можно рассматривать [math]Set(A)[/math] как композицию урны и [math]A[/math], другими словами, можно вместо атомов в урне взять объекты класса [math]A[/math].

Циклы

Ограниченная конструкция

Определение:
Цикл [math]A=Cycle_k(B)[/math] — ориентированная циклическая последовательность из [math]k[/math] объектов класса [math]B[/math]. Циклов нулевой длины [math]0[/math], то есть, [math]c_0=0[/math].


Утверждение:
Каждому циклу [math](b_1, b_2, ..., b_k)[/math] длины [math]k[/math] биективно соответствует [math]k[/math] упорядоченных последовательностей (циклические перестановки элементов цикла).

Поэтому [math]Seq_k(A) = k\cdot Cycle_k(A)[/math]

Значит, экспоненциальная производящая функция циклов — [math]Cycle_k(A)(t)=\frac{Seq_k(A)(t)}{k}=\frac{A(t)^k}{k}[/math].

Неограниченная конструкция

Определение:
Циклы [math]A=Cycle(B)=\sum_{k=0}^{\infty}Cycle_k(B)[/math].

[math]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 )[/math] (Разложение натурального логарифма в ряд Тейлора)

См.также

Примeчания

Источники информации