Symbolic Method

The symbolic method is a technique for quickly converting combinatorial objects into generating functions. We consider specific operations defined on sets and then derive the corresponding operations on generating functions.

We call a combinatorial class (or simply class) a pair \((\mathcal{A},\lvert \cdot \rvert)\), where \(\mathcal{A}\) is a set of combinatorial objects, and the function \(\lvert \cdot \rvert\) maps each combinatorial object to a non-negative integer, generally called the size function. Note that this non-negative integer cannot be infinite. For example, for strings over the alphabet \(\lbrace 0,1\rbrace\), the length of the string can be set as its size function; for trees or graphs, the number of nodes can be set as the size function. Note that this is not absolute; sometimes the size function of certain specific nodes may be set to \(0\), etc.

This article is a simplification based on Chapter 1 of the book Analytic Combinatorics.

Unlabeled System

In the unlabeled system, ordinary generating functions (OGFs) are used. For a set \(\mathcal{A}\), its corresponding OGF is denoted as

\[ A(z)=\sum_{\alpha\in\mathcal{A}}z^{\lvert \alpha \rvert}=\sum_{n\geq 0}a_nz^n \]

We adopt the convention of using the same group of letters to denote the generating function and related quantities for the same class. For example, \(a_n\) denotes \(\lbrack z^n\rbrack A(z)\), i.e., the coefficient of \(z^n\) in \(A(z)\), and \(\mathcal{A}_n\) denotes the set of objects in \(\mathcal{A}\) with size function \(n\) (so \(a_n=\operatorname{card}(\mathcal{A}_n)\), where \(\operatorname{card}\) is the cardinality).

This article will not discuss admissibility; readers may refer to the literature for details.

We now introduce two special combinatorial classes and objects:

• Let \(\epsilon\) denote the neutral object and \(\mathcal{E}=\lbrace \epsilon \rbrace\) the neutral class. The size of the neutral object is \(0\), and the OGF of the neutral class is \(E(z)=1\).
• Let \(\circ\) or \(\bullet\) denote the atom object, and \(\mathcal{Z}_{\circ}=\lbrace \circ\rbrace\) or \(\mathcal{Z}_{\bullet}=\lbrace \bullet\rbrace\), or simply \(\mathcal{Z}\), denote the atom class. The size of the atom object is \(1\), and the OGF of the atom class is \(Z(z)=z\).

For two combinatorial classes \(\mathcal{A}\) and \(\mathcal{B}\), combinatorial isomorphism is denoted as \(\mathcal{A}=\mathcal{B}\) or \(\mathcal{A}\cong\mathcal{B}\), but the latter notation is used only when the isomorphism is non-trivial.

We have

\[ \mathcal{A}\cong\mathcal{E}\times \mathcal{A}\cong\mathcal{A}\times\mathcal{E} \]

where \(\times\) is the binary operation representing the Cartesian product of sets.

(Disjoint) Union Construction

The union of classes \(\mathcal{A}\) and \(\mathcal{B}\) is denoted as

\[ \mathcal{A}+\mathcal{B}=(\mathcal{E}_{1}\times\mathcal{A})+(\mathcal{E}_2\times\mathcal{B}) \]

This definition ensures compliance with the set-theoretic requirement of disjoint sets. We can imagine coloring the objects in \(\mathcal{A}\) red and those in \(\mathcal{B}\) blue.

The corresponding OGF is

\[ A(z)+B(z) \]

Consider

\[ A(z)+B(z)=\sum _ {\alpha\in\mathcal{A}}z^{\lvert \alpha\rvert} + \sum _ {\beta\in\mathcal{B}}z^{\lvert \beta\rvert}=\sum_{n\geq 0}(a_n+b_n)z^n \]

which corresponds to the addition of formal power series.

Cartesian Product Construction

The Cartesian product of classes \(\mathcal{A}\) and \(\mathcal{B}\) is denoted as

\[ \mathcal{A}\times \mathcal{B}=\left\lbrace (\alpha, \beta)\mid \alpha \in \mathcal{A},\beta\in\mathcal{B}\right\rbrace \]

The corresponding OGF is

\[ A(z)\cdot B(z) \]

We define the size of \((\alpha,\beta)\) as the sum of the sizes of its components. Then clearly

\[ \gamma =(\alpha_1,\alpha_2,\dots ,\alpha_n)\implies \lvert \gamma\rvert =\lvert \alpha_1\rvert +\lvert \alpha_2\rvert +\cdots +\lvert \alpha_n\rvert \]

Thus

\[ A(z)\cdot B(z)=\left(\sum _ {\alpha\in\mathcal{A}}z^{\lvert \alpha\rvert}\right)\left(\sum _ {\beta\in\mathcal{B}}z^{\lvert \beta\rvert}\right)=\sum _ {(\alpha, \beta)\in(\mathcal{A}\times \mathcal{B})}z^{\lvert \alpha\rvert +\lvert \beta\rvert}=\sum_{n\geq 0}\sum_{i+j=n}a_ib_jz^n \]

which corresponds to the multiplication of formal power series.

Sequence Construction

The Sequence construction generates all possible ordered combinations.

Example

\[ \begin{aligned} \operatorname{SEQ}(\lbrace a\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace (a,a)\rbrace +\lbrace (a,a,a)\rbrace +\cdots\\ \operatorname{SEQ}(\lbrace a,b\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a,b\rbrace +\lbrace (a,b)\rbrace + \lbrace(b,a)\rbrace +\lbrace (a,a)\rbrace +\lbrace (b,b)\rbrace\\ &+\lbrace (a,b,a)\rbrace +\lbrace (a,b,b)\rbrace +\lbrace (a,a,b)\rbrace\\ &+\lbrace (b,b,a)\rbrace +\lbrace (b,a,b)\rbrace +\lbrace (b,b,b)\rbrace +\lbrace (a,a,a)\rbrace +\lbrace (b,a,a)\rbrace\\ &+\cdots \end{aligned} \]

We can see that elements with different orders of components, such as \(\lbrace (a,b)\rbrace\) and \(\lbrace (b,a)\rbrace\), are generated. It can be considered that the Sequence construction generates ordered combinations.

We define

\[ \operatorname{SEQ}(\mathcal{A})=\mathcal{E}+\mathcal{A}+(\mathcal{A}\times \mathcal{A})+(\mathcal{A}\times \mathcal{A}\times \mathcal{A})+\cdots \]

with the requirement that \(\mathcal{A}_0=\varnothing\), i.e., there are no objects of size \(0\) in \(\mathcal{A}\).

The corresponding OGF is

\[ Q(A(z))=1+A(z)+A(z)^2+A(z)^3+\cdots =\frac{1}{1-A(z)} \]

where \(Q\) is the Pólya quasi-inversion.

Example: Ordered Rooted Tree

We can use the Sequence construction to define ordered rooted trees, i.e., rooted trees where the order of children matters. Let this combinatorial class be \(\mathcal{T}\); then a tree consists of a root node and a Sequence of trees, i.e.,

\[ \mathcal{T}=\lbrace \bullet\rbrace\times\operatorname{SEQ}(\mathcal{T}) \]

The corresponding OGF is

\[ T(z)=\frac{z}{1-T(z)} \]

The first few coefficients are 0 1 1 2 5 14 42 132 429 1430 4862 16796, ignoring the constant term, which is OEIS A000108.

Multiset Construction

The Multiset construction generates all possible combinations but does not distinguish the order among the elements of the components.

Example

\[ \begin{aligned} \operatorname{MSET}(\lbrace a\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace (a,a)\rbrace +\lbrace (a,a,a)\rbrace +\cdots\\ \operatorname{MSET}(\lbrace a,b\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace (a,a)\rbrace +\lbrace (a,a,a)\rbrace +\cdots\\ &+\lbrace b\rbrace +\lbrace (a,b)\rbrace +\lbrace (a,a,b)\rbrace +\cdots \\ &+\lbrace (b,b)\rbrace + \lbrace (a,b,b)\rbrace +\lbrace (a,a,b,b)\rbrace + \cdots\\ &+\cdots \end{aligned} \]

Note that \(\lbrace (b,a)\rbrace\) and \(\lbrace (a,b,a)\rbrace\) appear in \(\operatorname{SEQ}(\lbrace a,b\rbrace)\) but not in \(\operatorname{MSET}(\lbrace a,b\rbrace)\). It can be considered that the Multiset construction generates unordered combinations.

We define its recurrence as

\[ \operatorname{MSET}(\lbrace \alpha_0,\alpha_1,\dots, \alpha_n\rbrace)=\operatorname{MSET}(\lbrace \alpha_0,\alpha_1,\dots, \alpha_{n-1}\rbrace)\times \operatorname{SEQ}(\lbrace \alpha_n\rbrace) \]

i.e.,

\[ \operatorname{MSET}(\mathcal{A})=\prod _ {\alpha\in\mathcal{A}}\operatorname{SEQ}(\lbrace \alpha\rbrace) \]

with the requirement that \(\mathcal{A}_0=\varnothing\). Alternatively, an equivalent definition is

\[ \operatorname{MSET}(\mathcal{A})=\operatorname{SEQ}(\mathcal{A})/\mathbf{R} \]

where \(\mathbf{R}\) is an equivalence relation: we say \((\alpha_1,\dots,\alpha_n)\mathbf{R}(\beta_1,\dots,\beta_n)\) if and only if there exists a permutation \(\sigma\) such that \(\beta_{j}=\alpha_{\sigma(j)}\) for all \(j\).

The corresponding OGF is

\[ \operatorname{Exp}(A(z))=\prod _ {\alpha \in\mathcal{A}}\left(1-z^{\lvert \alpha \rvert}\right)^{-1}=\prod _ {n\geq 1}\left(1-z^n\right)^{-a_n} \]

Note that

\[ \ln(1+z)=\frac{z}{1}-\frac{z^2}{2}+\frac{z^3}{3}-\cdots =\sum_{n\geq 1}\frac{(-1)^{n-1}z^n}{n} \]

and \(A(z)=\exp(\ln(A(z)))\), so

\[ \begin{aligned} \operatorname{Exp}(A(z))&=\exp\left(\sum _ {n\geq 1}-a_n\cdot \ln\left(1-z^n\right)\right)\\ &=\exp\left(\sum _ {n\geq 1}-a_n\cdot \sum _ {m\geq 1}\frac{-z^{nm}}{m}\right)\\ &=\exp\left(\frac{A(z)}{1}+\frac{A(z^2)}{2}+\frac{A(z^3)}{3}+\cdots \right) \end{aligned} \]

where \(\operatorname{Exp}\) is the Pólya exponential, also known as the Euler transform.

Problem LOJ 6268. Partition Number

Problem: Let \(f(n)\) denote the number of ways to partition \(n\). Find \(f(1),f(2),\dots,f(10^5)\) modulo \(998244353\).

Solution: Let the class of all positive integers be \(\mathcal{I}\). Then \(\mathcal{I}=\operatorname{SEQ}_{\geq 1}(\mathcal{Z})=\mathcal{Z}\times \operatorname{SEQ}(\mathcal{Z})\) (the subscript \(\geq 1\) indicates a restricted construction, see later). The desired quantity is

\[ \operatorname{MSET}(\mathcal{I}) \]

The first few coefficients of the corresponding OGF are 1 2 3 5 7 11 15 22 30 42 (ignoring the constant term), which is OEIS A000041.

Problem Luogu P4389 Princess's Backpack

Problem: Given \(n\) types of items with volumes \(v_1,\dots ,v_n\) and a positive integer \(m\), find the number of ways to fill a backpack with volumes \(1,2,\dots,m\) (unlimited quantity of items, with different types possibly having the same volume) modulo \(998244353\). It is given that \(1\leq n,m\leq 10^5\) and \(1\leq v_i\leq m\).

Solution: Let the combinatorial class of items be \(\mathcal{A}\). The desired quantity is the coefficients of the OGF corresponding to \(\operatorname{MSET}(\mathcal{A})\).

Problem Luogu P5900 Unlabeled Rootless Tree Counting

Problem: Find the number of unlabeled rootless trees with \(n\) nodes modulo \(998244353\). It is given that \(1\leq n\leq 2\times 10^5\).

Solution: Let the combinatorial class of unlabeled rooted trees be \(\mathcal{T}\). Then

\[ \mathcal{T}=\lbrace \bullet\rbrace\times\operatorname{MSET}(\mathcal{T}) \]

According to Richard Otter's paper The Number of Trees, the OGF for rootless trees is

\[ T(z)-\frac{1}{2}T^2(z)+\frac{1}{2}T(z^2) \]

The first few coefficients are 1 1 1 2 3 6 11 23 47 106 (ignoring the constant term), which is OEIS A000055.

Powerset Construction

The Powerset construction generates all subsets.

Example

\[ \begin{aligned} \operatorname{PSET}(\lbrace a\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace \\ \operatorname{PSET}(\lbrace a,b\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace b\rbrace +\lbrace (a,b)\rbrace \\ \operatorname{PSET}(\lbrace a,b,c\rbrace)&=\lbrace \epsilon\rbrace +\lbrace a\rbrace +\lbrace b\rbrace +\lbrace (a,b)\rbrace +\lbrace c\rbrace +\lbrace (a,c)\rbrace +\lbrace (b,c)\rbrace +\lbrace (a,b,c)\rbrace\\ \end{aligned} \]

We define its recurrence as

\[ \operatorname{PSET}(\lbrace \alpha_0,\alpha_1,\dots, \alpha_n\rbrace)=\operatorname{PSET}(\lbrace \alpha_0,\alpha_1,\dots, \alpha_{n-1}\rbrace)\times (\lbrace \epsilon\rbrace +\lbrace \alpha_n\rbrace) \]

i.e.,

\[ \operatorname{PSET}(\mathcal{A})\cong \prod _ {\alpha\in\mathcal{A}}\left(\lbrace \epsilon \rbrace +\lbrace \alpha\rbrace\right) \]

with the requirement that \(\mathcal{A}_0=\varnothing\).

The corresponding OGF is

\[ \begin{aligned} \overline{\operatorname{Exp}}(A(z))&=\prod _ {\alpha\in\mathcal{A}}\left(1+z^{\lvert \alpha \rvert}\right)=\prod _ {n\geq 1}\left(1+z^n\right)^{a_n}\\ &=\exp\left(\sum _ {n\geq 1}a_n\cdot \ln\left(1+z^n\right)\right)\\ &=\exp\left(\sum _ {n\geq 1}a_n\cdot \sum _ {m\geq 1}\frac{(-1)^{m-1}z^{nm}}{m}\right)\\ &=\exp\left(\frac{A(z)}{1}-\frac{A(z^2)}{2}+\frac{A(z^3)}{3}-\cdots \right) \end{aligned} \]

where \(\overline{\operatorname{Exp}}\) is the modified Pólya exponential.

It is easy to see that \(\operatorname{PSET}(\mathcal{A})\subset \operatorname{MSET}(\mathcal{A})\).

Cycle Construction

The Cycle construction generates all possible combinations but does not distinguish those that differ only by a cyclic shift.

We define it as

\[ \operatorname{CYC}(\mathcal{A})=\left(\operatorname{SEQ}(\mathcal{A})\setminus\lbrace \epsilon\rbrace\right)/\mathbf{S} \]

where \(\mathbf{S}\) is an equivalence relation: we say \((\alpha_1,\dots,\alpha_n)\mathbf{S}(\beta_1,\dots,\beta_n)\) if and only if there exists a cyclic shift \(\tau\) such that \(\beta_j=\alpha_{\tau(j)}\) for all \(j\).

Example

For simplicity, let \(\texttt{a},\texttt{b}\) be characters of size \(1\). Here we list only strings of size \(3\) and \(4\):

\[ \operatorname{CYC}(\lbrace \texttt{a},\texttt{b}\rbrace)_3=\lbrace \texttt{aaa}\rbrace +\lbrace \texttt{aab}\rbrace+\lbrace \texttt{abb}\rbrace+\lbrace \texttt{bbb}\rbrace \]

where \(\texttt{aab}\mathbf{S}\texttt{baa}\mathbf{S}\texttt{aba}\) are considered the same, and similarly \(\texttt{abb}\mathbf{S}\texttt{bab}\mathbf{S}\texttt{bba}\) are considered the same.

\[ \operatorname{CYC}(\lbrace \texttt{a},\texttt{b}\rbrace)_4=\lbrace \texttt{aaaa}\rbrace +\lbrace \texttt{aaab}\rbrace+\lbrace \texttt{aabb}\rbrace+\lbrace \texttt{abbb}\rbrace+\lbrace \texttt{bbbb}\rbrace +\lbrace \texttt{abab}\rbrace \]

where \(\texttt{aaab}\mathbf{S}\texttt{baaa}\mathbf{S}\texttt{abaa}\mathbf{S}\texttt{aaba}\), \(\texttt{aabb}\mathbf{S}\texttt{baab}\mathbf{S}\texttt{bbaa}\mathbf{S}\texttt{abba}\), \(\texttt{abbb}\mathbf{S}\texttt{babb}\mathbf{S}\texttt{bbab}\mathbf{S}\texttt{bbba}\), and \(\texttt{abab}\mathbf{S}\texttt{baba}\) are considered the same.

The corresponding OGF is

\[ \operatorname{Log}(A(z))=\sum _ {n\geq 1}\frac{\varphi(n)}{n}\ln\frac{1}{1-A(z^n)} \]

where \(\varphi\) is Euler's totient function, and \(\operatorname{Log}\) is the Pólya logarithm.

The proof is rather complex; readers may refer to Flajolet's paper The Cycle Construction or the appendix of Analytic Combinatorics.

Restricted Constructions

For all the constructions above, we did not restrict the number of "components". If we add a predicate acting on integers as a subscript to \(\operatorname{SEQ}\) to constrain the number of components, such as

\[ \operatorname{SEQ}_{=k}(\mathcal{B}),\quad \operatorname{SEQ}_{\geq k}(\mathcal{B}),\quad \operatorname{SEQ}_{1..k}(\mathcal{B}) \]

where \(\operatorname{SEQ}_{=k}(\mathcal{B})\) is often abbreviated as \(\operatorname{SEQ}_k(\mathcal{B})\), and \(\operatorname{SEQ}_{1..k}(\mathcal{B})\) indicates the interval \(\lbrack 1..k\rbrack\).

Let \(\mathfrak{K}\) be any of the above \(\operatorname{SEQ},\operatorname{PSET},\operatorname{MSET},\operatorname{CYC}\), and let

\[ \mathcal{A}=\mathfrak{K}_k(\mathcal{B}) \]

i.e., for \(\alpha\in\mathcal{A}\), we require

\[ \alpha =\lbrace (\beta_1,\beta_2,\dots ,\beta_k)\mid \beta\in\mathcal{B}\rbrace \]

Let the \(\chi\) function act on a combinatorial object as the number of its components, i.e., we want \(\chi(\alpha)=k\). We can introduce an extra variable to "track" the number of components.

Let

\[ A _ {n,k}=\operatorname{card}\left\lbrace \alpha\in\mathcal{A}\mid \lvert \alpha\rvert =n,\chi(\alpha)=k\right\rbrace \]

Then

\[ A(z,u)=\sum _ {n,k}A _ {n,k}u^kz^n=\sum _ {\alpha\in\mathcal{A}}z^{\lvert \alpha\rvert}u^{\chi(\alpha)} \]

Then we only need to extract the coefficient of \(u^k\) to obtain the corresponding expression. For example, \(\mathcal{A}=\operatorname{SEQ}_k(\mathcal{B})\) directly gives

\[ \begin{aligned} &{}A(z,u)=\sum _ {k\geq 0}u^kB(z)^k=\frac{1}{1-uB(z)}\\ \implies &{}A(z)=B(z)^k \end{aligned} \]

Clearly, also

\[ \mathcal{A}=\operatorname{SEQ}_{\geq k}(\mathcal{B})\implies A(z)=\frac{B(z)^k}{1-B(z)} \]

For \(\operatorname{MSET} _ k(\mathcal{B})\) and \(\operatorname{PSET} _ k(\mathcal{B})\), we already have

\[ \begin{aligned} &{}A(z,u)=\prod_n\left(1-uz^n\right)^{-b_n}\\ \implies &{}A(z)=\lbrack u^k\rbrack \exp\left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\cdots\right) \end{aligned} \]

and

\[ \begin{aligned} &{}A(z,u)=\prod_n\left(1+uz^n\right)^{b_n}\\ \implies &{}A(z)=\lbrack u^k\rbrack \exp\left(\frac{u}{1}B(z)-\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)-\cdots\right) \end{aligned} \]

Similarly for \(\operatorname{CYC}_k(\mathcal{B})\).

Using the above to compute OGFs for \(\operatorname{MSET}_3(\mathcal{B})\) and \(\operatorname{MSET}_4(\mathcal{B})\)

Attempt to compute \(\mathcal{A}=\operatorname{MSET}_3(\mathcal{B})\) as

\[ \begin{aligned} \lbrack u^3\rbrack A(z,u)&= \frac{1}{0!}\left(\lbrack u^3\rbrack 1\right)+\frac{1}{1!}\left(\lbrack u^3\rbrack \left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\cdots \right)\right)\\ &+\frac{1}{2!}\left(\lbrack u^3\rbrack \left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\cdots \right)^2\right)\\ &+\frac{1}{3!}\left(\lbrack u^3\rbrack \left(\frac{u}{1}B(z)+\cdots \right)^3\right)\\ &=\frac{B(z)^3}{6}+\frac{B(z)B(z^2)}{2}+\frac{B(z)^3}{3} \end{aligned} \]

Attempt to compute \(\mathcal{A}=\operatorname{MSET}_4(\mathcal{B})\) as

\[ \begin{aligned} \lbrack u^4\rbrack A(z,u)&= \frac{1}{0!}\left(\lbrack u^4\rbrack 1\right)+\frac{1}{1!}\left(\lbrack u^4\rbrack \left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\frac{u^4}{4}B(z^4)+\cdots \right)\right)\\ &+\frac{1}{2!}\left(\lbrack u^4\rbrack \left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\frac{u^3}{3}B(z^3)+\cdots \right)^2\right)\\ &+\frac{1}{3!}\left(\lbrack u^4\rbrack \left(\frac{u}{1}B(z)+\frac{u^2}{2}B(z^2)+\cdots \right)^3\right)\\ &+\frac{1}{4!}\left(\lbrack u^4\rbrack \left(\frac{u}{1}B(z)+\cdots \right)^4\right)\\ &=\frac{B(z^4)}{4}+\frac{1}{2!}\left(\frac{B(z^2)^2}{4}+\frac{2B(z)B(z^3)}{3}\right)+\frac{1}{3!}\left(\frac{3B(z)^2B(z^2)}{2}\right)+\frac{B(z)^4}{4!}\\ &=\frac{B(z)^4}{24}+\frac{B(z)^2B(z^2)}{4}+\frac{B(z)B(z^3)}{3}+\frac{B(z^2)^2}{8}+\frac{B(z^4)}{4} \end{aligned} \]

We find that in \(\mathcal{A}=\mathfrak{K}_k(\mathcal{B})\), \(A(z)\) is an expression in terms of \(B(z),B(z^2),\dots ,B(z^k)\).

Note that for restricted constructions \(\mathfrak{K}_k(\mathcal{B})\), there is no requirement that \(\mathcal{B}_0=\varnothing\).

Common Restricted Constructions

\[ \begin{aligned} \operatorname{PSET} _ {2}(\mathcal{A})&:\quad \frac{A(z)^2}{2}-\frac{A(z^2)}{2}\\ \operatorname{MSET} _ {2}(\mathcal{A})&:\quad \frac{A(z)^2}{2}+\frac{A(z^2)}{2}\\ \operatorname{CYC} _ {2}(\mathcal{A})&:\quad \frac{A(z)^2}{2}+\frac{A(z^2)}{2} \end{aligned} \]

\[ \begin{aligned} \operatorname{PSET} _ {3}(\mathcal{A})&:\quad \frac{A(z)^3}{6}-\frac{A(z)A(z^2)}{2}+\frac{A(z^3)}{3}\\ \operatorname{MSET} _ {3}(\mathcal{A})&:\quad \frac{A(z)^3}{6}+\frac{A(z)A(z^2)}{2}+\frac{A(z^3)}{3}\\ \operatorname{CYC} _ {3}(\mathcal{A})&:\quad \frac{A(z)^3}{3}+\frac{2A(z^3)}{3}\\ \end{aligned} \]

\[ \begin{aligned} \operatorname{PSET} _ {4}(\mathcal{A})&:\quad \frac{A(z)^4}{24}-\frac{A(z)^2A(z^2)}{4}+\frac{A(z)A(z^3)}{3}+\frac{A(z^2)^2}{8}-\frac{A(z^4)}{4}\\ \operatorname{MSET} _ {4}(\mathcal{A})&:\quad \frac{A(z)^4}{24}+\frac{A(z)^2A(z^2)}{4}+\frac{A(z)A(z^3)}{3}+\frac{A(z^2)^2}{8}+\frac{A(z^4)}{4}\\ \operatorname{CYC} _ {4}(\mathcal{A})&:\quad \frac{A(z)^4}{4}+\frac{A(z^2)^2}{4}+\frac{A(z^4)}{2}\\ \end{aligned} \]

The above calculation method, though effective, is somewhat cumbersome. Readers may refer to the WolframMathWorld pages on Pólya Enumeration Theorem and Cycle Index, among other related materials. The latter, Cycle Index, frequently appears in generating function expressions on OEIS.

Problem LOJ 6538. Alkane Counting Enhanced Enhanced Edition

Problem: Find the number of unordered trees with \(n\) nodes that are rooted, with the root node having degree at most \(3\) and all other nodes having degree at most \(4\), modulo \(998244353\). It is given that \(1\leq n\leq 10^5\).

Solution: Let the combinatorial class be \(\mathcal{T}\). Then

\[ \mathcal{T}=\lbrace \bullet\rbrace\times\operatorname{MSET}_{0,1,2,3}(\mathcal{T}) \]

Alternatively, let \(\hat{\mathcal{T}}=\mathcal{T}+\lbrace \epsilon\rbrace\). Then

\[ \hat{\mathcal{T}}=\lbrace \epsilon\rbrace +\lbrace \bullet\rbrace\times\operatorname{MSET}_{3}(\hat{\mathcal{T}}) \]

which yields the same result.

References

• Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics.

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用