Изменения

В комбинаторике, особенно в аналитической комбинаторике, [https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) символьный метод] - это метод подсчета [https://neerc.ifmo.ru/wiki/index.php?title=Метод Комбинаторные_объекты комбинаторных объектов]. Он использует внутреннюю структуру объектов для получения формул их [[Производящая функция|производящих функций=]]. Этот метод в основном связан с [https://en.wikipedia.org/wiki/Philippe_Flajolet Филиппом Флайоле] и подробно описан в части A его книги с [https://ru.wikipedia.org/wiki/Седжвик,_Роберт Робертом Седжвиком] "Аналитическая комбинаторика"<ref>[https://en.wikipedia.org/wiki/Analytic_Combinatorics "Аналитическая комбинаторика"]</ref>.

 ==Непомеченные комбинаторные объектыБазовые определения==

У атомов определен вес <tex dpi="130">w(</tex>. Вес объектов равен сумме весов составляющих его атомов. {{Определение|definition=Считающей последовательностью называется последовательность <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \bullet)}</tex>, где <tex dpi=1"130">a_i</tex> {{---}} количество объектов веса <tex dpi="130">i</tex>.}}

Обозначим <tex dpi="130350">w(\circ)[t_n]</tex> как оператор взятия <tex dpi=0"350">n</tex>-того коэффициента производящей функции.

Считающей последовательностью называется последовательность Комбинаторным классом <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}A</tex>называется множество комбинаторных объектов, где <tex dpi="130">a_i</tex> {{--обладающих каким-}} количество объектов веса <tex dpi="130">i</tex>то свойством.

=Непомеченные комбинаторные объекты= Введём атомы <tex dpi="350">\bullet</tex> и <tex dpi="350">\circ</tex> следующим образом: <tex dpi="130">w(\bullet)=1</tex> <tex dpi="130">w(\circ)=0</tex> Производящую функцию класса <tex dpi="130">A</tex> обозначим <tex dpi="130">A(t)=\sum_{i=0}^{\infty }a_i t^i</tex>, если <tex dpi="350">\{a_i\}</tex> {{---}} считающая последовательность этого класса.

Считающая последоваетльностьпоследовательность: <tex dpi="130">\left \{ 1, 0, ..., 0 \right \}</tex>.

Производящая функция последовательности: ==Объединение комбинаторных классов== {{Определение|definition=Объединением комбинаторных классов <tex dpi="350">A</tex> и <tex dpi="350">B</tex> называется комбинаторный класс <tex dpi="350">C=A \cup B=A+B</tex>, состоящий из элементов обоих классов, причем равные объекты разных классов объявляются разными.}}Целью этого уточнения является возможность работать только со считающими последовательностями и производящими функциями. <tex dpi="350">c_n=a_n+b_n</tex> <tex dpi="130350">C(t)=\varepsilonleft (\sum_{i=0}^{\infty}a_i \cdot t^i \right )+ \left ( \sum_{i=10}^{\infty}b_i \cdot t^i \right ) = \sum_{i=0}^{\infty}(a_i + b_i)\cdot t^i =A(t)+B(t)</tex>. ==Пары комбинаторных классов (декартово произведение комбинаторных классов)==

Комбинаторным классом Парой комбинаторных классов <tex dpi="130350">A</tex> и <tex dpi="350">B</tex> называется множество комбинаторных объектовкомбинаторный класс <tex dpi="350">C=Pair(A, B)=A \times B=\left \{ (\alpha, \beta) \mid \alpha \in A, \beta \in B \right \}</tex>.}} <tex dpi="350">w\left ( \left ( \alpha, обладающих каким\beta \right ) \right )=w(\alpha) + w(\beta)</tex> <tex dpi="350">c_n=\sum_{k=0}^{n}a_k b_{n-то свойством.k}</tex> {{Утверждение|statement=<tex dpi="350">C(t)=A(t) \cdot B(t)</tex><ref>[[Арифметические действия с формальными степенными рядами]]</ref>

===Объединение Последовательности комбинаторных классов== ===Ограниченная конструкция=== 

Последовательностью <tex dpi="350">Ck</tex> объектов из <tex dpi="350">A \cup </tex> называется <tex dpi="350">B=Seq_k(A+B)=\left \{ c | c (\alpha_1, ..., \alpha_k) \in A mid \vee c alpha_i \in B A \right \}</tex>.

При объединении комбинаторных классов одинаковые объекты считаются разными<tex dpi="350">w(\left \{ (\alpha_1, ... Это делается так, чтобы не рассматривать внутреннюю структуру, а работать только с считающими послеовательностями и производящими функциями. \alpha_k) \mid \alpha_i \in A \right \})=\sum_{i=0}^{k}\alpha_i</tex>

{{Утверждение|statement=<tex dpi="350">CSeq_k(A)(t)=A(t)^k</tex>|proof=Докажем по индукции: '''База <tex dpi="350">k=1</tex>'''.:Для <tex dpi="350">k=1</tex> верно, потому что <tex dpi="350">Seq_1(A)=A \Rightarrow Seq_1(A)(t)=A(t)=A(t)^1</tex>. '''Переход'''.:Пусть для <tex dpi="350">k=n</tex> верно <tex dpi="350">Seq_n(A)(t)=A(t)^n</tex>. Докажем для <tex dpi="350">k=n+1</tex>:<tex dpi="350">Seq_{n+1}(A)(t)=A(t)^{n+1}</tex>. Рассмотрим <tex dpi="350">Seq_{n+1}(A)</tex> как <tex dpi="350">Pair(Seq_n(A), A)</tex>. Тогда <tex dpi="350">Seq_{n+B1}(A)(t)=A(t)^n \cdot A(t)=A(t)^{n+1}</tex>.}} ===Неограниченная конструкция===

Последовательностью объектов из <tex dpi="350">CA</tex> называется <tex dpi="350">B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)</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> (Геометрическая прогрессия)}}  '''Ограничение:''' <tex dpi="350">a_0=0</tex> (также можно встретить <tex dpi="350">A_0=0</tex>). Этому есть как техническое, так и комбинаторное объяснение.* Технически, если <tex dpi="350">a_0>1</tex>, то мы будем делить на отрицательное число; если <tex dpi="350">a_0=1</tex>, то на функцию, у которой свободный член <tex dpi="350">0</tex>, {{---}} что формализм производящих функций сделать не позволяет.* Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей. ====Примеры====* Последовательности из не менее, чем 3 объектов:** <tex dpi="350">Seq_{\geq 3}=Pair(Seq_3(A), Seq(A))=Seq(A)-Seq_0(A)-Seq_1(A)-Seq_2(A)</tex>** <tex dpi="350">Seq_{\geq 3}(t)=Pair(Seq_3(A), Seq(A))(t)=A(t)^3 \cdot \frac{1}{1-A(t)}=\frac{A(t)^3}{1-A(t)}=(Seq(A)-Seq_0(A)-Seq_1(A)-Seq_2(A))(t)=\frac{1}{1-A(t)}-0-A(t)-A(t)^2</tex>* Последовательности чётной длины:** <tex dpi="350">Seq_{\vdots 2}(A)=Seq(Pair(A, A))</tex>** <tex dpi="350">Seq_{\vdots 2}(A)(t)=Seq(Pair(A, BA))(t)=\frac{1}{1-A\left (t^2\right )}</tex> ==Комбинаторный класс "Натуральные числа"== Вес числа равен его значению. Каждое натуральное число встречается 1 раз. Считающая последовательность: <tex dpi="350">\left \{ 0, 1, ..., 1 \right \}</tex> <tex dpi="350">w(n)=n</tex> Класс "Натуральные числа" принято обозначать <tex dpi="350">I</tex>.Считающая последовательность {{---}}<tex dpi="350">c_n=\left\{\begin{matrix}0, n=0\\ 1, n>0\end{matrix}\right.</tex> {{Утверждение|statement=<tex dpi="350">I(t)=\frac{t}{1 - t}</tex>|proof=Производящей функцией последовательности из <tex dpi="350">1</tex> явлется <tex>Seq(\{1\})=\frac{1}{1-t}</tex>. Чтобы получить производящую функцию класса натуральных чисел, произведем сдвиг вправо по правилам работы со степенными рядами:<tex dpi="350">t \cdot I(t) = t \cdot \frac{1}{1 - t} = \frac{t}{1-t}</tex>}} ===Применение=== <tex dpi="350">Seq(I)</tex> {{---}} упорядоченное [[Нахождение количества разбиений числа на слагаемые|разбиение натуральных чисел на слагаемые]]. Тогда производящая функция {{---}} <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">\left [ t^n \right ] \frac{1-t}{1-2t} = \left\{\begin{matrix}2 ^ n - 2 ^ {n - 1} = 2 ^ {n - 1}, n > 0\\ 1, n = 0\end{matrix}\right.</tex>, потому что <tex dpi="350">\frac{1}{1-2t}</tex> соответсвует ряду степеней <tex dpi="350">2</tex>, а <tex dpi="350">\frac{1}{1-2t}</tex> {{---}} ряду <tex dpi="350">2^{x-1}</tex>. ==Множества== {{Определение|definition=Множества <tex dpi="350">Set(A)</tex> {{---}} последовательности без повторений и порядка элементов.}}{{Утверждение|statement=<tex dpi="350">Set(A)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )</tex>|proof=Докажем по индукции по потенциальным элементам множеств <tex dpi="350">A</tex>. '''База''' <tex dpi="350">A=\varnothing</tex> <tex dpi="350">Set(\varnothing)=\varepsilon=\prod_{\alpha\in A }\varepsilon</tex> '''Переход''' Пусть верно для множества <tex dpi="350">A_1</tex>, докажем, что будет верно и для множества и <tex dpi="350">A_1+\{\alpha\}</tex>, где <tex dpi="350">\alpha\in A\setminus A_1</tex>В множестве каждый элемент может либо присутствовать, либо отсутствовать, поэтому <tex dpi="350">Set(A_1+\{\alpha\})=Set(A_1)+Set(A_1)\times B\{\alpha\}=Set(A_1)(\varepsilon + \alpha)</tex>.}} ====Пример====* <tex dpi="350">A =\left \{ \alpha, \beta, \gamma \right \}</tex>* <tex dpi="350">Set(A) = \left \{ \varnothing, \left \{ \alpha \right \}, \left \{ \beta\right \}, \left \{ \gamma \right \}, \left \{ \alpha, \beta\right \}, \left \{ \alpha, \gamma \right \}, \left \{ \beta, \gamma \right \}, \left \{ \alpha, \beta, \gamma \right \} \right \}</tex> <tex dpi="350">Set(A)(t)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )(t)=\prod_{\alpha \in A}(1+t^{w(\alpha)})=\prod_{n=0}^{\infty}(1+t^n)^{a_n}</tex> ==Мультимножества== {{Определение|definition=Мультимножества <tex dpi="350">MSet(A)</tex> {{---}} последовательности с повторениями, но без порядка элементов.}}Как и с <tex dpi="350">Seq(A)</tex> существует ограничение на <tex dpi="350">A</tex>: <tex dpi="350">a_0=A(0) =0</tex>.{{Утверждение| statement=<tex dpi="350">MSet(A)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})</tex>|proof=Докажем по индукции по потенциальным элементам множеств <tex dpi="350">A</tex>. '''База''' <tex dpi="350">A=\varnothing</tex> <tex dpi="350">MSet(\varnothing)=\varepsilon=\prod_{\alpha \in A}\varepsilon</tex> '''Переход''' Отличие от множеств в том, что здесь каждый элемент может присутствовать в любом неотрицательном количестве экземпляров, поэтому для каждого элемента <tex dpi="350">\alpha</tex> берется <tex dpi="350">Seq(\{\alpha\})</tex> Пусть верно для мультимножества <tex dpi="350">A_1</tex>, докажем, что будет верно и для мультимножества и <tex dpi="350">A_1+Seq_{\geq1}(\{\alpha\})</tex>, где <tex dpi="350">\beta alpha\in BA\setminus A_1</tex><tex dpi="350">MSet(A_1+\{\alpha\})=MSet(A_1)+MSet(A_1)\times\{\alpha\}\times Seq_{\geq 1}(\{\alpha \})=MSet(A_1)\cdot Seq(\{\alpha\})</tex>.

Пусть <tex dpi="150350">Seq(A)(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">\frac{1a_0, a_1, ..., a_n, ... \}{1-</tex>, тогда <tex dpi="350">A'(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">B=\{ a_1, a_2, ..., a_n, ... \}</tex>.

<tex dpi="130"">S_{0} = 1</tex>, так как есть единственный способ составить пустую последовательность.==Пример====

Докажем по индукции'''Перестановки'''* <tex dpi="350">P=Seq(Z)</tex>* Экспоненциальной производящей функцией является <tex dpi="350">P(t)=\frac{1}{1-t}</tex>.* Обычной производящей функции <tex dpi="350">\frac{1}{1-t}</tex> соответствует считающая последовательность <tex dpi="350">\left \{ 1, 1, ..., 1\right \}</tex>, поэтому <tex dpi="350">[t_n]\frac{1}{1-t}=1</tex>.* <tex dpi="350">p_n=n!\cdot[t_n]p(t)=n!</tex>

'''База <tex dpi="130"">n = 1</tex>'''. Урны==:<tex dpi=Кобинаторный класс "130Урна"">S_{1}=w_{1---} S_{0}=w_{1}</tex>множество, что вернохарактеризующееся только количеством атомов в объекте, так как единственный способ составить последовательность то есть элементов каждого веса {{---}} <tex dpi="130"350">1</tex> {{---}} это взять любой элемент веса , поэтому <tex dpi="130"350">a_n=1</tex>.

'''Переход'''. :Пусть для Производящая функция этого класса {{---}} <tex dpi="130"350">j < edf(t)=\sum_{n=0}^{\infty}\frac{1\cdot t^n}{n!}=\sum_{n</tex> верно. Докажем для <tex dpi="130"">0}^{\infty}\frac{t^n}{n!}=e^t</tex>. Возьмем произвольный элемент из  ==Множества== В формализме помеченных объектов <tex dpi="130350"">A</tex> веса <tex dpiMSet="130"">i \leqslant nSet</tex>, и допишем его к последовательности потому что не бывает одинаковых элементов веса в множествах. ===Ограниченная конструкция=== {{Определение|definition=Ограниченным множеством <tex dpi="130"350">n-i</tex>. Образуется новая последовательность веса <tex dpiA="130"">nSet_k(B)</tex>. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса назовём множество из <tex dpi="130"350">nk</tex> и ни к какой последовательности меньшего веса мы объектов (порядок не добавляем один и тот же элемент дваждыважен).

{| class<tex dpi="wikitable350" >Set_k(B)\cdot k!=Seq_k(B)</tex>|-align="center" !<tex dpi="130350">SeqSet_k(B)(t)=A(t)=\frac{\left ( B \left ( t \right ) \right )^k}{k!}</tex>|| ===Неограниченная конструкция=== <tex dpi="130350">A=Set(B)=\dfracsum_{1k=0}^{1-A\infty}Set_k(zb)}</tex>{{---}} множества объектов (порядок не важен).|-align="center" !Ограничение <tex dpi="130350">PSetb_0=B(A0)=0</tex>||также действует. <tex dpi="130350">\prod\limits_{n \geqslant 1}Set(A)(1+z^{n}t)^{A_{n}}=\exp(-\sum\limits_sum_{k =0}^{\geqslant 1infty}\dfracfrac{A(-1t)^k}{k!}=e^{A(z^{k}t)}{k})</tex>|-align="center" !Можно рассматривать <tex dpi="130350">MSetSet(A)</tex>||как композицию урны и <tex dpi="130350">\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="130350">Pair(A,B)</tex>. ==Циклы== ===Ограниченная конструкция=== {{Определение||definition=Цикл <tex dpi="130350">A=Cycle_k(z)B(z)</tex>|{{---align}} ориентированная циклическая последовательность из <tex dpi="center350" !>k</tex> объектов класса <tex dpi="130350">Cycle(A)B</tex>||. Циклов нулевой длины <tex dpi="130350">\sum\limits_{n \geqslant 1}\dfrac{\phi(n)}{n}\ln\dfrac{1}{1 - A(z^n)}0</tex>, где то есть, <tex dpi="130350">\phi(n)c_0=0</tex> {{---}} [[Функция_Эйлера | функция Эйлера]].|}}

Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, {{---}} помеченные графыУтверждение|statement=Каждому циклу <tex dpi="350">(b_1, b_2, ... С помеченными объектами используется экспоненциальная производящая функция , b_k)</tex> длины <tex dpi="350">k</tex> биективно соответствует <tex dpi="350">k<ref/tex>упорядоченных последовательностей ([[https://en.wikipedia:exponential generating function | Wikipedia {{---.org/wiki/Cyclic_permutation циклические перестановки] элементов цикла).}} 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="130350">PsetSeq_k(A)</tex>||<tex dpi="130">k\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">Cyclecdot Cycle_k(A)</tex>||<tex dpi="130">\ln\dfrac{1}{1-A(z)}</tex>.|}

===Ограниченные конструкции===Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (напримерЗначит, экспоненциальная производящая функция циклов {{---}} <tex dpi="130350">Seq_Cycle_k(A)(t)=\frac{k}Seq_k(A)</tex> (t)}{k}=\frac{---A(t)^k}{k} <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) : \{(a, a) \mid a \in A\}</tex>. Тогда имеет место соотношение <tex dpiНеограниченная конструкция=="130">B(z)=A(z^{2})</tex>.

Диагональная конструкция позволяет получить доступ к классу всех неупорядоченных пар из различных элементов из {{Определение|definition=Циклы <tex dpi="130350">A</tex>, то есть к <tex dpi="130">P Cycle(B)=\sum_{k= PSet_0}^{2\infty}Cycle_k(AB)</tex>. Прямое выражение выполняется следующим способом: неупорядоченная пара }}<tex dpi="130350">\langle \alpha, \beta \rangle </tex> связана с двумя упорядоченными парами <tex dpiCycle(A)(t)="130">(\langle \alpha, \beta \rangle </tex> и <tex dpisum_{k="130">0}^{\langle \beta, \alpha \rangle infty}Cycle_k(A)(t)</tex>, кроме тех случаев, когда <tex dpi="130">0+\alpha sum_{k= 1}^{\infty}\beta</tex>, то есть когда пара лежит на диагонали декартова произведения. Другими словами, <tex dpi="130">PSet_frac{2}A(At) + PSet_^k}{2k}=-ln \left (1+\left (-A(t)\right ) \right ) + =-ln \Deltaleft (1-A (t) \times Aright ) =ln\left (\cong frac{1}{1-A (t)}\times Aright )</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}+\dfrac{A(z^{2})}{2}</tex>|-alignПримeчания="center" !<tex dpi="130">Cycle_{2}(A)<references/tex>||<tex dpi="130">\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}</tex>|}

Аналогичные рассуждения можно провести и для больших <tex dpi="130">k<Источники информации=*[https:/tex>/youtu.be/J2L-vdytqC0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e Artem Vasilyev {{---}} Descrete maths lectures, однако расчеты быстро становятся сложнымиunmarked objects]*[https://youtu. Классический способ исправления таких вопросов be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e Artem Vasilyev {{---}} Descrete maths lectures, marked objects]*[[Лемма Бёрнсайда https://neerc.ifmo.ru/wiki/index.php?title=Конструирование_комбинаторных_объектов_и_их_подсчёт Викиконспекты {{---}} Конструирование комбинаторных объектов и Теорема Пойа#Теорема Пойа | теорема Пойаих подсчёт]*[https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) Wikipedia {{---}} Symbolic method].

Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа <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}Дискретная математика и алгоритмы]\exp(-\sum\limits_{i=1}^{k}\dfrac{(-1)^{i}u^{i}A(z^{i})}{i})</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> {{---}} [[Функция_Эйлера | функция ЭйлераКатегория: Комбинаторика]].|}