Изменения

Перейти к: навигация, поиск

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

436 байт добавлено, 00:10, 25 июня 2020
UI
В [https://ru.wikipedia.org/wiki/Комбинаторика комбинаторике], особенно в [https://en.wikipedia.org/wiki/Analytic_Combinatorics аналитической комбинаторике], [https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) символический метод] - это метод подсчета [https://neerc.ifmo.ru/wiki/index.php?title=Комбинаторные_объекты комбинаторных объектов]. Он использует внутреннюю структуру объектов для получения [https://ru.wikipedia.org/wiki/Математическая_формула формул для ] их [[Производящая функция|производящих функций]]. Этот метод в основном связан с [https://en.wikipedia.org/wiki/Philippe_Flajolet Филиппом Флайоле] и подробно описан в части A его книги с [https://ru.wikipedia.org/wiki/Седжвик,_Роберт Робертом Седжвиком] "Аналитическая комбинаторика"<ref>[https://en.wikipedia.org/wiki/Analytic_Combinatorics "Аналитическая комбинаторика"]</ref>.
=Непомеченные комбинаторные объекты=
{{Определение
|definition=
Комбинаторным классом <tex dpi="130">A</tex> называется [https://ru.wikipedia.org/wiki/Множество множество ] комбинаторных объектов, обладающих каким-то свойством.
}}
==Пары комбинаторных классов ([https://ru.wikipedia.org/wiki/Прямое_произведение декартово произведение ] комбинаторных классов)==
{{Определение
{{Утверждение
|statement=<tex dpi="350">Seq_k(A)(t)=A(t)^k</tex>
|proof=Докажем по [[Математическая индукция|индукции]]:
'''База <tex dpi="350">k=1</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> ([https://ru.wikipedia.org/wiki/Геометрическая_прогрессия Геометрическая прогрессия])
}}
==Комбинаторный объект "[[Натуральные числа]]"==
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
<tex dpi="350">I(t)=t \cdot Seq(Z)(t) = t \cdot \frac{1}{1 - t} = \frac{t}{1 - t}</tex>
<tex dpi="350">Seq(I)</tex> {{---}} упорядоченное [https://ru.wikipedia.org/wiki/Разбиение_числа разбиение на слагаемые].
<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">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>
==[http://en.wikipedia.org/wiki/Cyclic_order Циклы]==
===Ограниченная конструкция===
{{Утверждение
|statement=
<tex dpi="350">Cycle(A)(t)=\sum_{n \geq 1} \frac{\phi(n)}{n} ln \left ( \frac{1}{1-A(z^n)} \right )</tex>, где <tex dpi="350">\phi(n)</tex> {{---}} [[функция Эйлера]].
}}
195
правок

Навигация