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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Непомеченные комбинаторные объекты)
Строка 207: Строка 207:
 
=Помеченные объекты=
 
=Помеченные объекты=
  
 +
'''какое-то бесполезное введение. Что значит "удобнее"? просто есть такие классы и всё)'''
 
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, — [https://e-maxx.ru/algo/counting_connected_graphs помеченные графы]. С помеченными объектами используется [https://en.wikipedia.org/wiki/Generating_function#Exponential_generating_function_(EGF) экспоненциальная производящая функция].
 
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, — [https://e-maxx.ru/algo/counting_connected_graphs помеченные графы]. С помеченными объектами используется [https://en.wikipedia.org/wiki/Generating_function#Exponential_generating_function_(EGF) экспоненциальная производящая функция].
  
Напомню, что если <tex dpi="350">\left \{ a_i \right \}</tex> {{---}} считающая последовательность, то производящие функции выражаются следующим образом:
+
Напомню, '''Научный текст нужно писать безлично''' что если <tex dpi="350">\left \{ a_i \right \}</tex> {{---}} считающая последовательность, то производящие функции выражаются следующим образом:
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 249: Строка 250:
 
==Помеченные объекты==
 
==Помеченные объекты==
  
Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки, а именно {{---}} если вес объекта <tex dpi="350">n</tex>, то все атомы пронумерованы различными целыми числами от <tex dpi="350">1</tex> до <tex dpi="350">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(①)=1</tex>
Строка 255: Строка 256:
 
<tex dpi="130">w(\circ)=0</tex>
 
<tex dpi="130">w(\circ)=0</tex>
  
Далее под производящей функцией будет подразумеваться экспоненциальная производящая функция.
+
Далее под производящей функцией будет подразумеваться экспоненциальная производящая функция. '''это лучше вынести в самое начало раздела и сказать, почему'''
  
 
{{Определение
 
{{Определение
Строка 287: Строка 288:
 
==Пары комбинаторных классов (декартово произведение комбинаторных классов)==
 
==Пары комбинаторных классов (декартово произведение комбинаторных классов)==
  
Напрямую декартово произведение нам не даст корректный комбинаторный объект.
+
Напрямую декартово произведение нам не даст корректный комбинаторный объект. '''переформулируй'''
  
 
Пусть <tex dpi="350">A= \{</tex> [[Файл:1-2.png|50px]] <tex dpi="350">\}</tex>,
 
Пусть <tex dpi="350">A= \{</tex> [[Файл:1-2.png|50px]] <tex dpi="350">\}</tex>,
Строка 294: Строка 295:
 
Тогда пара <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">(</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 \star B</tex>, который
 
# Перебирает все пары из <tex dpi="350">A</tex> и <tex dpi="350">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>.
+
# В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 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>''([https://ru.wikipedia.org/wiki/Сочетание Сочетания])''<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">c_n=\sum_{k=0}^na_kb_{n-k}\binom{n}{k}</tex>''([https://ru.wikipedia.org/wiki/Сочетание Сочетания])''<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>
Строка 308: Строка 309:
 
===Ограниченная конструкция===
 
===Ограниченная конструкция===
  
Последовательности длины <tex dpi="350">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом:
+
Последовательности длины <tex dpi="350">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом:  
 
* Мы составляем все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex>
 
* Мы составляем все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex>
 
* Затем всеми возможными способами их перенумеруем.
 
* Затем всеми возможными способами их перенумеруем.
 +
'''научный текст пишется безлично'''
 +
  
 
Обозначаются <tex dpi="350">Seq_k(A)</tex>.
 
Обозначаются <tex dpi="350">Seq_k(A)</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_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>
Строка 322: Строка 326:
 
Определение <tex dpi="350">Seq(A)</tex> и соответствующая производящая функция не изменились.
 
Определение <tex dpi="350">Seq(A)</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">b_0=B(0)=0</tex> как и <tex dpi="350">Seq(A)</tex> и в <tex dpi="350"Mset(A)></tex> в мире непомеченных объектов. '''опечатки, формулировки'''
  
 
====Пример====
 
====Пример====
  
'''[https://ru.wikipedia.org/wiki/Перестановка Перестановки]'''
+
'''[https://ru.wikipedia.org/wiki/Перестановка Перестановки]''' '''вроде тоже можно дать ссылку на нирк'''
 
* <tex dpi="350">P=Seq(Z)</tex>
 
* <tex dpi="350">P=Seq(Z)</tex>
 
* <tex dpi="350">P(t)=\frac{1}{1-t}</tex>
 
* <tex dpi="350">P(t)=\frac{1}{1-t}</tex>
Строка 333: Строка 337:
  
 
==Урны==
 
==Урны==
 
+
'''что такое урна'''
 
Урна характеризуется только количеством атомов в ней, поэтому <tex dpi="350">a_n=1</tex>
 
Урна характеризуется только количеством атомов в ней, поэтому <tex dpi="350">a_n=1</tex>
  
Строка 347: Строка 351:
 
<tex dpi="350">A=Set_k(B)</tex> {{---}} множество из <tex dpi="350">k</tex> объектов (порядок не важен).
 
<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 B</tex>
+
<tex dpi="350">\left \{ a_1, a_2, ..., a_k \right \} \in B</tex> '''что это такое'''
  
 
Каждому <tex dpi="350">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">k!</tex> последовательностей в <tex dpi="350">Seq_k(B)</tex>, потому что все объекты различны.
Строка 363: Строка 367:
 
<tex dpi="350">Set(A)(t)=\sum_{k=0}^{\infty}\frac{A(t)^k}{k!}=e^{A(t)}</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">Set(A)</tex> {{---}} урна, где вместо атомов взяли объекты класса <tex dpi="350">A</tex>. '''напиши чуть более развернуто, а не предложениями в три слова'''
  
 
==Циклы==
 
==Циклы==
Строка 384: Строка 388:
 
===Неограниченная конструкция===
 
===Неограниченная конструкция===
  
<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-A(t) \right )=ln\left (\frac{1}{1-A(t)}\right )</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-A(t) \right )=ln\left (\frac{1}{1-A(t)}\right )</tex> '''почему'''
  
 
==См.также==
 
==См.также==

Версия 18:58, 26 июня 2020

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


Содержание

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

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

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


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


Определение:
Комбинаторным классом [math]A[/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]. Тут вообще ничего не понятно. Что за точки и кружочки, что такое А и а_i


Определение:
Комбинаторным объектом [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=\left \{ c \mid c \in A \vee c \in B \right \}[/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]
[math]\triangleright[/math]
Верно, потому что коэффициенты производящей функции описываются равенством выше внеси в один пункт с определением, если тут нечего сказать. Можешь добавить линк на операции с формальными рядами
[math]\triangleleft[/math]

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

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

Определение:
Последовательностью [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\gt 1[/math], то мы будем делить на отрицательное число; если [math]a_0=1[/math], то на функцию, у которой свободный член [math]0[/math], — что формализм производящих функций сделать не позволяет.
  • Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
  • [math]a_0=0 \Leftrightarrow A(0)=0[/math] какой-то бесполезный факт


Примеры

  • Последовательночти из не менее 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]

НЕ ПИШИ ЭТО МАТРИЦЕЙ. ЕСТЬ EQUATION [math]c_n=\left\{\begin{matrix} 0, n=0\\ 1, n\gt 0 \end{matrix}\right.[/math]

[math]I(t)=t \cdot Seq(Z)(t) = t \cdot \frac{1}{1 - t} = \frac{t}{1 - t}[/math] что такое I и почему равенство выполняется?

[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]Set(A)[/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)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \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]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]A=Cycle_k(B)[/math] — ориентированная циклическая последовательность из [math]k[/math] объектов класса [math]B[/math].


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

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


Утверждение:
почему? [math]Cycle(A)(t)=\sum_{n \geq 1} \frac{\phi(n)}{n} ln \left ( \frac{1}{1-A(z^n)} \right )[/math], где [math]\phi(n)[/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]НУ НЕЕЕ
Утверждение:
Пусть [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]


Утверждение:
С точки зрения комбинаторики композиция производящих функций [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}[/math](Сочетания)[math]=\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], как и в непомеченных комбинаторных объектах, формируются следующим образом:

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

научный текст пишется безлично


Обозначаются [math]Seq_k(A)[/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]b_0=B(0)=0[/math] как и [math]Seq(A)[/math] и в [math][/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]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 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]0[/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]Cycle(A)(t)=\sum_{k=0}^{\infty}Cycle_k(A)(t)=0+\sum_{k=1}^{\infty}\frac{A(t)^k}{k}=-ln \left (1-A(t) \right )=ln\left (\frac{1}{1-A(t)}\right )[/math] почему

См.также

Примeчания

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