286
правок
Изменения
м
|-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="150">f{n,k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}</tex>.
Количество таких деревьев с <tex dpi="130">n</tex> вершинами образуют последовательность <tex dpi="130"> 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots</tex> <ref>[http://oeis.org/A000081 | Number of unlabeled rooted trees with n node]</ref>
[[File:Forests.png|670px]]
В итоге, <tex dpi="130">C_{n}=\dfrac{1}{n}\sum_{i=0}^{s-1}k^{\mathrm{gcd}(n,i)}</tex>.
==Производящие функцииМетод производящих функций==
Такие большие группы часто анализируют с помощью [[Производящая функция|производящих функций]]. Один из популярных методов {{---}} метод символов (англ. ''Symbolic method''). Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества.
При непомеченных объектах рассмотренные классы имеют следующие производящие функции:
|}
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, {{---}} помеченные графы. С помеченными объектами используется экспоненциальная производящая функция. <ref>[[wikipedia:exponential generating function | Wikipedia {{---}} Exponential generating function]]</ref> . В данном случае для некоторых рассмотренных классов используются следующие производящие функции:
{| class="wikitable"
|-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>
