195
правок
Изменения
UI
=Помеченные объекты=
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, — [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> {{---}} считающая последовательность, то производящие функции выражаются следующим образом:
# В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 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(t)=A(t) \cdot B(t)</tex>
====Пример====
'''[https://ru.wikipedia.org/wiki/Перестановка Перестановки]'''
* <tex dpi="350">P=Seq(Z)</tex>
* <tex dpi="350">P(t)=\frac{1}{1-t}</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)*k!=Seq_k(B)</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 циклические перестановки ] элементов цикла).
}}
