286
правок
Изменения
OGF + EGF
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">P=PSet(A)</tex> {{---}} множество всех множеств, составленных из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{l}\}</tex> {{---}} количество объектов веса от <tex dpi="130">1</tex> до <tex dpi="130">l</tex>. Для простоты Мы также считаем , что нет объектов веса <tex dpi="130"">0</tex>. Тогда '''количество множеств''' суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">P_{n}=p_{n, n}</tex>, где <tex dpi="150">p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} p_{n-ik, k-1}</tex> {{---}} количество таких множеств, которые содержат объекты, вес которых не больше чем <tex dpi="150">k</tex>. Причем <tex dpi="150">p_{0, i} = 1</tex>, так как не набирать никакой вес есть один способ, а <tex dpi="150">p_{i, 0} = 0</tex>, <tex dpi="150"">i \ne 0</tex>, так как нельзя набрать положительный вес из ничего.
|proof=Изначально у нас есть только пустое множество веса <tex dpi="130">0</tex>. Рассмотрим очередной этап вычисления <tex dpi="130">p_{n,k}</tex>. Для данных <tex dpi="130">n</tex> и <tex dpi="130">k</tex> у нас уже имеется множество, которое необходимо дополнить. Мы можем сделать это добавляя от <tex dpi="130">0</tex> до <tex dpi="130">\lfloor \frac{n}{k} \rfloor</tex> элементов веса <tex dpi="130">k</tex> (при условии, что столько различных элементов имеется) в данное множество. Следовательно, у нас образуется новые множества, которые будет необходимо дополнить элементами веса меньше <tex dpi="130">k</tex> (чтобы избежать повторений) суммарного веса <tex dpi="130">n-ik</tex>, где <tex dpi="130">i</tex> {{---}} количество элементов веса <tex dpi="130">k</tex> которое мы добавили в данное множество. Довольно легко заметить, что данные операции полностью соответствуют описанной выше формуле.
}}
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">C=Cycle(A)</tex> {{---}} множество всех циклов <ref>[[wikipedia:Cyclic order|Wikipedia {{---}} Циклы]]</ref> из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots m\}</tex>.
Тогда '''количество циклов''' веса <tex dpi="150">n</tex> можно вычислить как <tex dpi="150">C_{n}=\sum_{s=1}^{n}c_{n, s}</tex>, где <tex dpi="150">c_{n,s}</tex> {{---}} количество циклов веса <tex dpi="150">n</tex> длины <tex dpi="150">s</tex>.
==Производящие функции==
{| class="wikitable"
!<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">\sum\limits_{n \geqslant 1}\dfrac{\phi(n)}n\ln\dfrac{1}{1-A(z^n)}</tex>, где <tex dpi="130">\phi(n)</tex> {{---}} [[Функция_Эйлера | функция Эйлера]].
|}
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, {{---}} помеченные графы. С помеченными объектами используется экспоненциальная производящая функция. <ref>[[wikipedia:exponential generating function | Wikipedia {{---}} Exponential generating function]]</ref> В данном случае для рассмотренных классов используются следующие производящие функции:
{| class="wikitable"
|-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">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>
|-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>.
|}
== См.также ==
*[https://www.youtube.com/playlist?list=PLrNmXMVD0XDSluoHUcasgvvmBAkf2BGLi Online Course Materials from Robert Sedgewick]
*[https://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
*[https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) Wikipedia {{---}} Symbolic method]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
