<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>
----
=Помеченные объекты=
Такие большие группы часто анализируют с помощью [[Производящая функция|производящих функций]]. Один из популярных методов Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки, а именно {{---}} метод символов если вес объекта <reftex dpi="350">[[wikipedia:Symbolic method (combinatorics) | Wikipedia {{---}} Symbolic method]]n</reftex>. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множествато все атомы пронумерованы различными целыми числами от <tex dpi="350">1</tex> до <tex dpi="350">n</tex>.
{{Утверждение|statement=<tex dpi="150130">Seqw(A)(t)=\fractextcircled{1}{)=1-A(t)}</tex>.|proof=
<tex dpi="130">w(\circ)=0</tex>
{{Определение|definition=Считающей последовательностью называется последовательность <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}</tex>, где <tex dpi="130">a_i</tex>S_{0{---} } количество объектов веса <tex dpi= 1"130">i</tex>, так как есть единственный способ составить пустую последовательность.}}
Докажем по индукцииПроизводящую функцию класса <tex dpi="130">A</tex> обозначим <tex dpi="130">A(t)=\sum_{i=0}^{\infty }a_i t^i</tex>.
'''База <tex dpi{{Определение|definition="130"">n = 1</tex>'''. :Комбинаторным объектом <tex dpi="130"">S_{1}=w_{1} S_{0}=w_{1}Z</tex>называется комбинаторный объект, что верно, так как единственный способ составить последовательность веса <tex dpi="130"">1</tex> {{---}} это взять любой элемент состоящий из одного атома веса <tex dpi="130"">1</tex>.
'''Переход'''. :Пусть для <tex dpi="130"">j < n</tex> верно. Докажем для <tex dpiZ="130"">n</tex>. Возьмем произвольный элемент из <tex dpi="130"">A</tex> веса <tex dpi="130"">i \leqslant n</tex>, и допишем его к последовательности элементов веса <tex dpi="130"">n-i</tex>. Образуется новая последовательность веса <tex dpi="130"">n</tex>. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса <tex dpi="130"">nleft \{ \bullet \right \}</tex> и ни к какой последовательности меньшего веса мы не добавляем один и тот же элемент дважды.
}}
Считающая последовательность: <tex dpi="130">\left \{ 0, 1, 0, ..., 0 \right \}</tex>.
При непомеченных объектах рассмотренные классы имеют следующие производящие функции:
{| 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">\prod\limits_{n \geqslant 1}(1+z^{n})^{A_{n}}=\exp(-\sum\limits_{k \geqslant 1}\dfrac{(-1)^{k}AZ(z^{k})}{k}t)</tex>|-align="center" !<tex dpi="130">MSet(A)t</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">\sum\limits_{n \geqslant 1}\dfrac{\phi(n)}{n}\ln\dfrac{1}{1 - A(z^n)}</tex>, где <tex dpi="130">\phi(n)</tex> {{---}} [[Функция_Эйлера | функция Эйлера]].|}
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, {{---}} помеченные графы. С помеченными объектами используется экспоненциальная производящая функция Определение|definition=Комбинаторным объектом <tex dpi="130">\varepsilon</tex> называется комбинаторный объект, состоящий из одного атома веса <reftex dpi="130">[[wikipedia:exponential generating function | Wikipedia {{---}} Exponential generating function]]0</reftex>. В данном случае для некоторых рассмотренных классов используются следующие производящие функции:
{| 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 dpivarepsilon="130">\exp(A(z))</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>.|} ===Ограниченные конструкции===Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (например, <tex dpi="130">Seq_{k}(A)</tex> {{---}} <tex dpi="130">k</tex> компонентов). Непосредственной формулой для производящих функций является диагональ <tex dpi="130">\Delta</tex> декартова произведения <ref>[[wikipedia:Cartesian product | Wikipedia {{---}} Декартово произведение]]</ref> <tex dpi="130">A \times A</tex>, определяемая как <tex dpi="130">B \equiv \Delta(A \times A) : left \{(a, a) \mid a circ \in Aright \}</tex>. Тогда имеет место соотношение <tex dpi="130">B(z)=A(z^{2})</tex>. Диагональная конструкция позволяет получить доступ к классу всех неупорядоченных пар из различных элементов из <tex dpi="130">A</tex>, то есть к <tex dpi="130">P = PSet_{2}(A)</tex>. Прямое выражение выполняется следующим способом: неупорядоченная пара <tex dpi="130">\langle \alpha, \beta \rangle </tex> связана с двумя упорядоченными парами <tex dpi="130">(\langle \alpha, \beta \rangle </tex> и <tex dpi="130">\langle \beta, \alpha \rangle )</tex>, кроме тех случаев, когда <tex dpi="130">\alpha = \beta</tex>, то есть когда пара лежит на диагонали декартова произведения. Другими словами, <tex dpi="130">PSet_{2}(A) + PSet_{2}(A) + \Delta(A \times A) \cong A \times A</tex>. Это, в свою очередь, означает что <tex dpi="130">2P(z) + A(z^{2}) = A(z)^{2}</tex>. Таким образом можно выразить <tex dpi="130">PSet_{2}(A)</tex>. Аналогично для <tex dpi="130">Seq_{2}(A)</tex>, <tex dpi="130">MSet_{2}(A)</tex> и <tex dpi="130">Cycle_{2}(A)</tex>:
{| class="wikitable" |-align="center" !<tex dpi="130">Seq_{2}(A)</tex>||<tex dpi="130>A(z)^{2}</tex>|-align="center" !<tex dpi="130">PSet_{2}(A)</tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}-\dfrac{A(z^{2})}{2}</tex>|-align="center" !<tex dpi="130">MSet_{2}(A)</tex>||Считающая последовательность: <tex dpi="130">\dfrac{A(z)^{2}}{2}+left \dfrac{A(z^{2})}{2}</tex>|-align="center" !<tex dpi="130">Cycle_{2}(A)</tex>||<tex dpi="130">1, 0, ..., 0 \dfrac{A(z)^{2}}{2}+right \dfrac{A(z^{2})}{2}</tex>|}.
Аналогичные рассуждения можно провести и для больших <tex dpi="130">k</tex>, однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов {{---}} [[Лемма Бёрнсайда и Теорема Пойа#Теорема Пойа | теорема Пойа]].
Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа <ref>[[wikipediaПроизводящая функция последовательности:Lagrange inversion theorem | Wikipedia {{---}} Lagrange inversion theorem]]</ref>. В общем случае, используя метод символов, производящие функции ограниченных конструкций можно подсчитать следующим способом: {| class="wikitable" |-align="center" !<tex dpi="130">Seq_{k}(A)</tex>||<tex dpi="130">A(z)^{k}</tex>|-align="center" !<tex dpi="130">PSet_{k}(A)</tex>||<tex dpi="130">[u^{k}]\expvarepsilon(-\sum\limits_{i=1}^{k}\dfrac{(-1)^{i}u^{i}A(z^{i})}{i}t)</tex>|-align="center" !<tex dpi="130">MSet_{k}(A)</tex>||<tex dpi="130">[u^{k}]\exp(\sum\limits_{i=1}^{k}\dfrac{u^{i}A(z^{i})}{i})</tex>|-align="center" !<tex dpi="130">Cycle_{k}(A)</tex>||<tex dpi="130">[u^{k}]\sum\limits_{i \geqslant 1}\dfrac{\phi(i)}{i}\ln\dfrac{1}{1 - u^{i}A(z^i)}</tex>, где <tex dpi="130">\phi(n)</tex> {{---}} [[Функция_Эйлера | функция Эйлера]].|}
