The symbolic method quickly converts combinatorial objects into generating functions. We consider particular operations defined on sets and derive the corresponding operations on their generating functions.
We call a combinatorial class (or simply a class), where is the set of combinatorial objects and maps each object to a finite nonnegative integer called its size. ( A , ∣ ⋅ ∣ ) (\mathcal{A},\lvert \cdot \rvert) ( A , ∣ ⋅ ∣) A \mathcal{A} A ∣ ⋅ ∣ \lvert \cdot \rvert ∣ ⋅ ∣ { 0 , 1 } \lbrace 0,1\rbrace { 0 , 1 } 0 0 0
This article is a simplified treatment based on Chapter 1 of the book Analytic Combinatorics .
Unlabelled Systems
In an unlabelled system, ordinary generating functions (OGFs) are used. For a class , its OGF is denoted by A \mathcal{A} A
A ( z ) = ∑ α ∈ A z ∣ α ∣ = ∑ n ≥ 0 a n z n A(z)=\sum_{\alpha\in\mathcal{A}}z^{\lvert \alpha \rvert}=\sum_{n\geq 0}a_nz^n A ( z ) = α ∈ A ∑ z ∣ α ∣ = n ≥ 0 ∑ a n z n We use the same letters for a class and its generating function. The coefficient counts objects in of size . a n a_n a n [ z n ] A ( z ) \lbrack z^n\rbrack A(z) [ z n ] A ( z ) A ( z ) A(z) A ( z ) z n z^n z n A n \mathcal{A}_n A n A \mathcal{A} A n n n a n = card ( A n ) a_n=\operatorname{card}(\mathcal{A}_n) a n = card ( A n ) card \operatorname{card} card
Admissibility is not discussed in this article; readers may consult the references.
We next introduce two special kinds of combinatorial classes and objects:
Let be the neutral object and the neutral class; their size and OGF are and . ϵ \epsilon ϵ E = { ϵ } \mathcal{E}=\lbrace \epsilon \rbrace E = { ϵ } 0 0 0 E ( z ) = 1 E(z)=1 E ( z ) = 1 ∘ \circ ∘ ∙ \bullet ∙ Z ∘ = { ∘ } \mathcal{Z}_{\circ}=\lbrace \circ\rbrace Z ∘ = { ∘ } Z ∙ = { ∙ } \mathcal{Z}_{\bullet}=\lbrace \bullet\rbrace Z ∙ = { ∙ } Z \mathcal{Z} Z 1 1 1 Z ( z ) = z Z(z)=z Z ( z ) = z
Two classes and that are combinatorially isomorphic are written or ; use the latter only for a nontrivial isomorphism. A \mathcal{A} A B \mathcal{B} B A = B \mathcal{A}=\mathcal{B} A = B A ≅ B \mathcal{A}\cong\mathcal{B} A ≅ B
We have
A ≅ E × A ≅ A × E \mathcal{A}\cong\mathcal{E}\times \mathcal{A}\cong\mathcal{A}\times\mathcal{E} A ≅ E × A ≅ A × E where is a binary operation denoting the Cartesian product of sets. × \times ×
Set (Disjoint) Union Construction
For classes and , their union is denoted by A \mathcal{A} A B \mathcal{B} B
A + B = ( E 1 × A ) + ( E 2 × B ) \mathcal{A}+\mathcal{B}=(\mathcal{E}_{1}\times\mathcal{A})+(\mathcal{E}_2\times\mathcal{B}) A + B = ( E 1 × A ) + ( E 2 × B ) This definition preserves disjointness in set theory: imagine coloring objects of red and objects of blue. A \mathcal{A} A B \mathcal{B} B
The corresponding OGF is
A ( z ) + B ( z ) A(z)+B(z) A ( z ) + B ( z ) Consider
A ( z ) + B ( z ) = ∑ α ∈ A z ∣ α ∣ + ∑ β ∈ B z ∣ β ∣ = ∑ n ≥ 0 ( a n + b n ) z n 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 A ( z ) + B ( z ) = α ∈ A ∑ z ∣ α ∣ + β ∈ B ∑ z ∣ β ∣ = n ≥ 0 ∑ ( a n + b n ) z n This corresponds to addition of formal power series.
Cartesian Product Construction for Sets
For classes and , their Cartesian product is denoted by A \mathcal{A} A B \mathcal{B} B
A × B = { ( α , β ) ∣ α ∈ A , β ∈ B } \mathcal{A}\times \mathcal{B}=\left\lbrace (\alpha, \beta)\mid \alpha \in \mathcal{A},\beta\in\mathcal{B}\right\rbrace A × B = { ( α , β ) ∣ α ∈ A , β ∈ B } The corresponding OGF is
A ( z ) ⋅ B ( z ) A(z)\cdot B(z) A ( z ) ⋅ B ( z ) Define the size of as the sum of the sizes of its components. ( α , β ) (\alpha,\beta) ( α , β )
γ = ( α 1 , α 2 , … , α n ) ⟹ ∣ γ ∣ = ∣ α 1 ∣ + ∣ α 2 ∣ + ⋯ + ∣ α n ∣ \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 γ = ( α 1 , α 2 , … , α n ) ⟹ ∣ γ ∣ = ∣ α 1 ∣ + ∣ α 2 ∣ + ⋯ + ∣ α n ∣ Therefore
A ( z ) ⋅ B ( z ) = ( ∑ α ∈ A z ∣ α ∣ ) ( ∑ β ∈ B z ∣ β ∣ ) = ∑ ( α , β ) ∈ ( A × B ) z ∣ α ∣ + ∣ β ∣ = ∑ n ≥ 0 ∑ i + j = n a i b j z n 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 A ( z ) ⋅ B ( z ) = ( α ∈ A ∑ z ∣ α ∣ ) β ∈ B ∑ z ∣ β ∣ = ( α , β ) ∈ ( A × B ) ∑ z ∣ α ∣ + ∣ β ∣ = n ≥ 0 ∑ i + j = n ∑ a i b j z n This corresponds to multiplication of formal power series.
Sequence Construction for Sets
The Sequence construction generates all possible combinations.
Example
SEQ ( { a } ) = { ϵ } + { a } + { ( a , a ) } + { ( a , a , a ) } + ⋯ SEQ ( { a , b } ) = { ϵ } + { a , b } + { ( a , b ) } + { ( b , a ) } + { ( a , a ) } + { ( b , b ) } + { ( a , b , a ) } + { ( a , b , b ) } + { ( a , a , b ) } + { ( b , b , a ) } + { ( b , a , b ) } + { ( b , b , b ) } + { ( a , a , a ) } + { ( b , a , a ) } + ⋯ \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} SEQ ({ a }) SEQ ({ a , b }) = { ϵ } + { a } + {( a , a )} + {( a , a , a )} + ⋯ = { ϵ } + { a , b } + {( a , b )} + {( b , a )} + {( a , a )} + {( b , b )} + {( a , b , a )} + {( a , b , b )} + {( a , a , b )} + {( b , b , a )} + {( b , a , b )} + {( b , b , b )} + {( a , a , a )} + {( b , a , a )} + ⋯ Different component orders, such as and , are both generated, so Sequence generates ordered combinations. { ( a , b ) } , { ( b , a ) } \lbrace (a,b)\rbrace ,\lbrace (b,a)\rbrace {( a , b )} , {( b , a )}
We define
SEQ ( A ) = E + A + ( A × A ) + ( A × A × A ) + ⋯ \operatorname{SEQ}(\mathcal{A})=\mathcal{E}+\mathcal{A}+(\mathcal{A}\times \mathcal{A})+(\mathcal{A}\times \mathcal{A}\times \mathcal{A})+\cdots SEQ ( A ) = E + A + ( A × A ) + ( A × A × A ) + ⋯ and require , that is, contains no object of size . A 0 = ∅ \mathcal{A}_0=\varnothing A 0 = ∅ A \mathcal{A} A 0 0 0
this OGF is
Q ( A ( z ) ) = 1 + A ( z ) + A ( z ) 2 + A ( z ) 3 + ⋯ = 1 1 − A ( z ) Q(A(z))=1+A(z)+A(z)^2+A(z)^3+\cdots =\frac{1}{1-A(z)} Q ( A ( z )) = 1 + A ( z ) + A ( z ) 2 + A ( z ) 3 + ⋯ = 1 − A ( z ) 1 where is the Pólya quasi-inverse. Q Q Q
Example: ordered rooted trees
We can use the Sequence construction to define ordered rooted trees, that is, rooted trees in which the order among children matters. If the class is , a tree consists of a root node and a Sequence of trees: T \mathcal{T} T
T = { ∙ } × SEQ ( T ) \mathcal{T}=\lbrace \bullet\rbrace\times\operatorname{SEQ}(\mathcal{T}) T = { ∙ } × SEQ ( T ) this OGF is
T ( z ) = z 1 − T ( z ) T(z)=\frac{z}{1-T(z)} T ( z ) = 1 − T ( z ) z The first coefficients are ; ignoring the constant term, this is OEIS . 0 1 1 2 5 14 42 132 429 1430 4862 16796 Reference
Multiset Construction for Sets
The Multiset construction generates all combinations without distinguishing the order of components.
Example
MSET ( { a } ) = { ϵ } + { a } + { ( a , a ) } + { ( a , a , a ) } + ⋯ MSET ( { a , b } ) = { ϵ } + { a } + { ( a , a ) } + { ( a , a , a ) } + ⋯ + { b } + { ( a , b ) } + { ( a , a , b ) } + ⋯ + { ( b , b ) } + { ( a , b , b ) } + { ( a , a , b , b ) } + ⋯ + ⋯ \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} MSET ({ a }) MSET ({ a , b }) = { ϵ } + { a } + {( a , a )} + {( a , a , a )} + ⋯ = { ϵ } + { a } + {( a , a )} + {( a , a , a )} + ⋯ + { b } + {( a , b )} + {( a , a , b )} + ⋯ + {( b , b )} + {( a , b , b )} + {( a , a , b , b )} + ⋯ + ⋯ Notice that sequences with the same components in a different order are identified by the Multiset construction. { ( b , a ) } , { ( a , b , a ) } \lbrace (b,a)\rbrace,\lbrace (a,b,a)\rbrace {( b , a )} , {( a , b , a )} SEQ ( { a , b } ) \operatorname{SEQ}(\lbrace a,b\rbrace) SEQ ({ a , b }) MSET ( { a , b } ) \operatorname{MSET}(\lbrace a,b\rbrace) MSET ({ a , b })
We define its recurrence as
MSET ( { α 0 , α 1 , … , α n } ) = MSET ( { α 0 , α 1 , … , α n − 1 } ) × SEQ ( { α n } ) \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) MSET ({ α 0 , α 1 , … , α n }) = MSET ({ α 0 , α 1 , … , α n − 1 }) × SEQ ({ α n }) That is,
MSET ( A ) = ∏ α ∈ A SEQ ( { α } ) \operatorname{MSET}(\mathcal{A})=\prod _ {\alpha\in\mathcal{A}}\operatorname{SEQ}(\lbrace \alpha\rbrace) MSET ( A ) = α ∈ A ∏ SEQ ({ α }) and require . Equivalently, we may write A 0 = ∅ \mathcal{A}_0=\varnothing A 0 = ∅
MSET ( A ) = SEQ ( A ) / R \operatorname{MSET}(\mathcal{A})=\operatorname{SEQ}(\mathcal{A})/\mathbf{R} MSET ( A ) = SEQ ( A ) / R where is an equivalence relation. We say if and only if there exists a permutation such that for every , . R \mathbf{R} R ( α 1 , … , α n ) R ( β 1 , … , β n ) (\alpha_1,\dots,\alpha_n)\mathbf{R}(\beta_1,\dots,\beta_n) ( α 1 , … , α n ) R ( β 1 , … , β n ) σ \sigma σ j j j β j = α σ ( j ) \beta_{j}=\alpha_{\sigma(j)} β j = α σ ( j )
this OGF is
Exp ( A ( z ) ) = ∏ α ∈ A ( 1 − z ∣ α ∣ ) − 1 = ∏ n ≥ 1 ( 1 − z n ) − a n \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} Exp ( A ( z )) = α ∈ A ∏ ( 1 − z ∣ α ∣ ) − 1 = n ≥ 1 ∏ ( 1 − z n ) − a n Notice that
ln ( 1 + z ) = z 1 − z 2 2 + z 3 3 − ⋯ = ∑ n ≥ 1 ( − 1 ) n − 1 z n n \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} ln ( 1 + z ) = 1 z − 2 z 2 + 3 z 3 − ⋯ = n ≥ 1 ∑ n ( − 1 ) n − 1 z n and , so A ( z ) = exp ( ln ( A ( z ) ) ) A(z)=\exp(\ln(A(z))) A ( z ) = exp ( ln ( A ( z )))
Exp ( A ( z ) ) = exp ( ∑ n ≥ 1 − a n ⋅ ln ( 1 − z n ) ) = exp ( ∑ n ≥ 1 − a n ⋅ ∑ m ≥ 1 − z n m m ) = exp ( A ( z ) 1 + A ( z 2 ) 2 + A ( z 3 ) 3 + ⋯ ) \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} Exp ( A ( z )) = exp ( n ≥ 1 ∑ − a n ⋅ ln ( 1 − z n ) ) = exp ( n ≥ 1 ∑ − a n ⋅ m ≥ 1 ∑ m − z nm ) = exp ( 1 A ( z ) + 2 A ( z 2 ) + 3 A ( z 3 ) + ⋯ ) The operator is the Pólya exponential, also called the Euler transform. Exp \operatorname{Exp} Exp
Example LOJ 6268. Partition numbers
Problem : Let be the number of partitions of . Find modulo . f ( n ) f(n) f ( n ) n n n f ( 1 ) , f ( 2 ) , … , f ( 10 5 ) f(1),f(2),\dots,f(10^5) f ( 1 ) , f ( 2 ) , … , f ( 1 0 5 ) 998244353 998244353 998244353
Solution : Let be the class of all positive integers. Then (the subscript is a restricted construction, discussed below). What is required is I \mathcal{I} I I = SEQ ≥ 1 ( Z ) = Z × SEQ ( Z ) \mathcal{I}=\operatorname{SEQ}_{\geq 1}(\mathcal{Z})=\mathcal{Z}\times \operatorname{SEQ}(\mathcal{Z}) I = SEQ ≥ 1 ( Z ) = Z × SEQ ( Z ) ≥ 1 \geq 1 ≥ 1
MSET ( I ) \operatorname{MSET}(\mathcal{I}) MSET ( I ) The first coefficients of this OGF are (ignoring the constant term), namely OEIS . 1 2 3 5 7 11 15 22 30 42 Reference
Example Luogu P4389. Fu Princess’s Knapsack
Problem : Given kinds of goods with volumes and a positive integer , find the number of ways to fill knapsacks of volumes modulo (unlimited quantities of goods are allowed, and goods of the same volume but different kinds are distinct). Assume and . n n n v 1 , … , v n v_1,\dots ,v_n v 1 , … , v n m m m 1 , 2 , … , m 1,2,\dots,m 1 , 2 , … , m 998244353 998244353 998244353 1 ≤ n , m ≤ 10 5 1\leq n,m\leq 10^5 1 ≤ n , m ≤ 1 0 5 1 ≤ v i ≤ m 1\leq v_i\leq m 1 ≤ v i ≤ m
Solution : Let be the class of goods. The desired values are the coefficients of the OGF corresponding to . A \mathcal{A} A MSET ( A ) \operatorname{MSET}(\mathcal{A}) MSET ( A )
Example Luogu P5900. Counting unlabelled unrooted trees
Problem : Find the number of unlabelled unrooted trees with vertices modulo . Assume . n n n 998244353 998244353 998244353 1 ≤ n ≤ 2 × 10 5 1\leq n\leq 2\times 10^5 1 ≤ n ≤ 2 × 1 0 5
Solution : Let be the combinatorial class of unlabelled rooted trees. Then T \mathcal{T} T
T = { ∙ } × MSET ( T ) \mathcal{T}=\lbrace \bullet\rbrace\times\operatorname{MSET}(\mathcal{T}) T = { ∙ } × MSET ( T ) According to Richard Otter’s paper , the OGF of unrooted trees is Reference
T ( z ) − 1 2 T 2 ( z ) + 1 2 T ( z 2 ) T(z)-\frac{1}{2}T^2(z)+\frac{1}{2}T(z^2) T ( z ) − 2 1 T 2 ( z ) + 2 1 T ( z 2 ) The first coefficients are (ignoring the constant term), namely OEIS . 1 1 1 2 3 6 11 23 47 106 Reference
Powerset Construction for Sets
The Powerset construction generates all subsets.
Example
PSET ( { a } ) = { ϵ } + { a } PSET ( { a , b } ) = { ϵ } + { a } + { b } + { ( a , b ) } PSET ( { a , b , c } ) = { ϵ } + { a } + { b } + { ( a , b ) } + { c } + { ( a , c ) } + { ( b , c ) } + { ( a , b , c ) } \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} PSET ({ a }) PSET ({ a , b }) PSET ({ a , b , c }) = { ϵ } + { a } = { ϵ } + { a } + { b } + {( a , b )} = { ϵ } + { a } + { b } + {( a , b )} + { c } + {( a , c )} + {( b , c )} + {( a , b , c )}
We define its recurrence as
PSET ( { α 0 , α 1 , … , α n } ) = PSET ( { α 0 , α 1 , … , α n − 1 } ) × ( { ϵ } + { α n } ) \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) PSET ({ α 0 , α 1 , … , α n }) = PSET ({ α 0 , α 1 , … , α n − 1 }) × ({ ϵ } + { α n }) That is,
PSET ( A ) ≅ ∏ α ∈ A ( { ϵ } + { α } ) \operatorname{PSET}(\mathcal{A})\cong \prod _ {\alpha\in\mathcal{A}}\left(\lbrace \epsilon \rbrace +\lbrace \alpha\rbrace\right) PSET ( A ) ≅ α ∈ A ∏ ( { ϵ } + { α } ) and require . A 0 = ∅ \mathcal{A}_0=\varnothing A 0 = ∅
this OGF is
Exp ‾ ( A ( z ) ) = ∏ α ∈ A ( 1 + z ∣ α ∣ ) = ∏ n ≥ 1 ( 1 + z n ) a n = exp ( ∑ n ≥ 1 a n ⋅ ln ( 1 + z n ) ) = exp ( ∑ n ≥ 1 a n ⋅ ∑ m ≥ 1 ( − 1 ) m − 1 z n m m ) = exp ( A ( z ) 1 − A ( z 2 ) 2 + A ( z 3 ) 3 − ⋯ ) \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} Exp ( A ( z )) = α ∈ A ∏ ( 1 + z ∣ α ∣ ) = n ≥ 1 ∏ ( 1 + z n ) a n = exp ( n ≥ 1 ∑ a n ⋅ ln ( 1 + z n ) ) = exp ( n ≥ 1 ∑ a n ⋅ m ≥ 1 ∑ m ( − 1 ) m − 1 z nm ) = exp ( 1 A ( z ) − 2 A ( z 2 ) + 3 A ( z 3 ) − ⋯ ) where is the modified Pólya exponential. Exp ‾ \overline{\operatorname{Exp}} Exp
It is immediate that . PSET ( A ) ⊂ MSET ( A ) \operatorname{PSET}(\mathcal{A})\subset \operatorname{MSET}(\mathcal{A}) PSET ( A ) ⊂ MSET ( A )
Cycle Construction for Sets
The Cycle construction generates all combinations without distinguishing combinations that differ only by rotation.
We define it as
CYC ( A ) = ( SEQ ( A ) ∖ { ϵ } ) / S \operatorname{CYC}(\mathcal{A})=\left(\operatorname{SEQ}(\mathcal{A})\setminus\lbrace \epsilon\rbrace\right)/\mathbf{S} CYC ( A ) = ( SEQ ( A ) ∖ { ϵ } ) / S where is an equivalence relation. We say if and only if there exists a cyclic shift such that for every , . S \mathbf{S} S ( α 1 , … , α n ) S ( β 1 , … , β n ) (\alpha_1,\dots,\alpha_n)\mathbf{S}(\beta_1,\dots,\beta_n) ( α 1 , … , α n ) S ( β 1 , … , β n ) τ \tau τ j j j β j = α τ ( j ) \beta_j=\alpha_{\tau(j)} β j = α τ ( j )
Example
For convenience, let both be characters of size . Here we list only strings of sizes and : a , b \mathtt{a},\mathtt{b} a , b 1 1 1 3 3 3 4 4 4
CYC ( { a , b } ) 3 = { a a a } + { a a b } + { a b b } + { b b b } \operatorname{CYC}(\lbrace \mathtt{a},\mathtt{b}\rbrace)_3=\lbrace \mathtt{aaa}\rbrace +\lbrace \mathtt{aab}\rbrace+\lbrace \mathtt{abb}\rbrace+\lbrace \mathtt{bbb}\rbrace CYC ({ a , b } ) 3 = { aaa } + { aab } + { abb } + { bbb } Among cyclically equivalent strings, retain only one representative. a a b S b a a S a b a \mathtt{aab}\mathbf{S}\mathtt{baa}\mathbf{S}\mathtt{aba} aab S baa S aba a b b S b a b S b b a \mathtt{abb}\mathbf{S}\mathtt{bab}\mathbf{S}\mathtt{bba} abb S bab S bba
CYC ( { a , b } ) 4 = { a a a a } + { a a a b } + { a a b b } + { a b b b } + { b b b b } + { a b a b } \operatorname{CYC}(\lbrace \mathtt{a},\mathtt{b}\rbrace)_4=\lbrace \mathtt{aaaa}\rbrace +\lbrace \mathtt{aaab}\rbrace+\lbrace \mathtt{aabb}\rbrace+\lbrace \mathtt{abbb}\rbrace+\lbrace \mathtt{bbbb}\rbrace +\lbrace \mathtt{abab}\rbrace CYC ({ a , b } ) 4 = { aaaa } + { aaab } + { aabb } + { abbb } + { bbbb } + { abab } Here , , , and . a a a b S b a a a S a b a a S a a b a \mathtt{aaab}\mathbf{S}\mathtt{baaa}\mathbf{S}\mathtt{abaa}\mathbf{S}\mathtt{aaba} aaab S baaa S abaa S aaba a a b b S b a a b S b b a a S a b b a \mathtt{aabb}\mathbf{S}\mathtt{baab}\mathbf{S}\mathtt{bbaa}\mathbf{S}\mathtt{abba} aabb S baab S bbaa S abba a b b b S b a b b S b b a b S b b b a \mathtt{abbb}\mathbf{S}\mathtt{babb}\mathbf{S}\mathtt{bbab}\mathbf{S}\mathtt{bbba} abbb S babb S bbab S bbba a b a b S b a b a \mathtt{abab}\mathbf{S}\mathtt{baba} abab S baba
this OGF is
Log ( A ( z ) ) = ∑ n ≥ 1 φ ( n ) n ln 1 1 − A ( z n ) \operatorname{Log}(A(z))=\sum _ {n\geq 1}\frac{\varphi(n)}{n}\ln\frac{1}{1-A(z^n)} Log ( A ( z )) = n ≥ 1 ∑ n φ ( n ) ln 1 − A ( z n ) 1 where is the Euler function and is the Pólya logarithm. φ \varphi φ Log \operatorname{Log} Log
The proof is more involved; see Flajolet's paper or the appendix of Analytic Combinatorics . Reference
Restricted Constructions
The constructions above impose no restriction on the number of components. A predicate on the subscript of can impose such a restriction: SEQ \operatorname{SEQ} SEQ
SEQ = k ( B ) , SEQ ≥ k ( B ) , SEQ 1.. k ( B ) \operatorname{SEQ}_{=k}(\mathcal{B}),\quad \operatorname{SEQ}_{\geq k}(\mathcal{B}),\quad \operatorname{SEQ}_{1..k}(\mathcal{B}) SEQ = k ( B ) , SEQ ≥ k ( B ) , SEQ 1.. k ( B ) Here is often abbreviated as , and means the interval . SEQ = k ( B ) \operatorname{SEQ}_{=k}(\mathcal{B}) SEQ = k ( B ) SEQ k ( B ) \operatorname{SEQ}_k(\mathcal{B}) SEQ k ( B ) SEQ 1.. k ( B ) \operatorname{SEQ}_{1..k}(\mathcal{B}) SEQ 1.. k ( B ) [ 1.. k ] \lbrack 1..k\rbrack [ 1.. k ]
Let be any one of above, and K \mathfrak{K} K SEQ , PSET , MSET , CYC \operatorname{SEQ},\operatorname{PSET},\operatorname{MSET},\operatorname{CYC} SEQ , PSET , MSET , CYC
A = K k ( B ) \mathcal{A}=\mathfrak{K}_k(\mathcal{B}) A = K k ( B ) That is, for , we require α ∈ A \alpha\in\mathcal{A} α ∈ A
α = { ( β 1 , β 2 , … , β k ) ∣ β ∈ B } \alpha =\lbrace (\beta_1,\beta_2,\dots ,\beta_k)\mid \beta\in\mathcal{B}\rbrace α = {( β 1 , β 2 , … , β k ) ∣ β ∈ B } Let be the number of components of a combinatorial object; introduce an extra variable to track this number. χ \chi χ χ ( α ) = k \chi(\alpha)=k χ ( α ) = k
Let
A n , k = card { α ∈ A ∣ ∣ α ∣ = n , χ ( α ) = k } A _ {n,k}=\operatorname{card}\left\lbrace \alpha\in\mathcal{A}\mid \lvert \alpha\rvert =n,\chi(\alpha)=k\right\rbrace A n , k = card { α ∈ A ∣ ∣ α ∣ = n , χ ( α ) = k } Then
A ( z , u ) = ∑ n , k A n , k u k z n = ∑ α ∈ A z ∣ α ∣ u χ ( α ) A(z,u)=\sum _ {n,k}A _ {n,k}u^kz^n=\sum _ {\alpha\in\mathcal{A}}z^{\lvert \alpha\rvert}u^{\chi(\alpha)} A ( z , u ) = n , k ∑ A n , k u k z n = α ∈ A ∑ z ∣ α ∣ u χ ( α ) Extracting the coefficient of gives the desired expression; for example, directly gives u k u^k u k A = SEQ k ( B ) \mathcal{A}=\operatorname{SEQ}_k(\mathcal{B}) A = SEQ k ( B )
A ( z , u ) = ∑ k ≥ 0 u k B ( z ) k = 1 1 − u B ( z ) ⟹ A ( z ) = B ( z ) k \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} ⟹ A ( z , u ) = k ≥ 0 ∑ u k B ( z ) k = 1 − u B ( z ) 1 A ( z ) = B ( z ) k Clearly,
A = SEQ ≥ k ( B ) ⟹ A ( z ) = B ( z ) k 1 − B ( z ) \mathcal{A}=\operatorname{SEQ}_{\geq k}(\mathcal{B})\implies A(z)=\frac{B(z)^k}{1-B(z)} A = SEQ ≥ k ( B ) ⟹ A ( z ) = 1 − B ( z ) B ( z ) k For and , we already have MSET k ( B ) \operatorname{MSET} _ k(\mathcal{B}) MSET k ( B ) PSET k ( B ) \operatorname{PSET} _ k(\mathcal{B}) PSET k ( B )
A ( z , u ) = ∏ n ( 1 − u z n ) − b n ⟹ A ( z ) = [ u k ] exp ( u 1 B ( z ) + u 2 2 B ( z 2 ) + u 3 3 B ( z 3 ) + ⋯ ) \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} ⟹ A ( z , u ) = n ∏ ( 1 − u z n ) − b n A ( z ) = [ u k ] exp ( 1 u B ( z ) + 2 u 2 B ( z 2 ) + 3 u 3 B ( z 3 ) + ⋯ ) and
A ( z , u ) = ∏ n ( 1 + u z n ) b n ⟹ A ( z ) = [ u k ] exp ( u 1 B ( z ) − u 2 2 B ( z 2 ) + u 3 3 B ( z 3 ) − ⋯ ) \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} ⟹ A ( z , u ) = n ∏ ( 1 + u z n ) b n A ( z ) = [ u k ] exp ( 1 u B ( z ) − 2 u 2 B ( z 2 ) + 3 u 3 B ( z 3 ) − ⋯ ) The same applies to . CYC k ( B ) \operatorname{CYC}_k(\mathcal{B}) CYC k ( B )
Computing the OGFs corresponding to and using the above formula MSET 3 ( B ) \operatorname{MSET}_3(\mathcal{B}) MSET 3 ( B ) MSET 4 ( B ) \operatorname{MSET}_4(\mathcal{B}) MSET 4 ( B )
Try computing : A = MSET 3 ( B ) \mathcal{A}=\operatorname{MSET}_3(\mathcal{B}) A = MSET 3 ( B )
[ u 3 ] A ( z , u ) = 1 0 ! ( [ u 3 ] 1 ) + 1 1 ! ( [ u 3 ] ( u 1 B ( z ) + u 2 2 B ( z 2 ) + u 3 3 B ( z 3 ) + ⋯ ) ) + 1 2 ! ( [ u 3 ] ( u 1 B ( z ) + u 2 2 B ( z 2 ) + ⋯ ) 2 ) + 1 3 ! ( [ u 3 ] ( u 1 B ( z ) + ⋯ ) 3 ) = B ( z ) 3 6 + B ( z ) B ( z 2 ) 2 + B ( z ) 3 3 \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} [ u 3 ] A ( z , u ) = 0 ! 1 ( [ u 3 ] 1 ) + 1 ! 1 ( [ u 3 ] ( 1 u B ( z ) + 2 u 2 B ( z 2 ) + 3 u 3 B ( z 3 ) + ⋯ ) ) + 2 ! 1 ( [ u 3 ] ( 1 u B ( z ) + 2 u 2 B ( z 2 ) + ⋯ ) 2 ) + 3 ! 1 ( [ u 3 ] ( 1 u B ( z ) + ⋯ ) 3 ) = 6 B ( z ) 3 + 2 B ( z ) B ( z 2 ) + 3 B ( z ) 3 Try computing : A = MSET 4 ( B ) \mathcal{A}=\operatorname{MSET}_4(\mathcal{B}) A = MSET 4 ( B )
[ u 4 ] A ( z , u ) = 1 0 ! ( [ u 4 ] 1 ) + 1 1 ! ( [ u 4 ] ( u 1 B ( z ) + u 2 2 B ( z 2 ) + u 3 3 B ( z 3 ) + u 4 4 B ( z 4 ) + ⋯ ) ) + 1 2 ! ( [ u 4 ] ( u 1 B ( z ) + u 2 2 B ( z 2 ) + u 3 3 B ( z 3 ) + ⋯ ) 2 ) + 1 3 ! ( [ u 4 ] ( u 1 B ( z ) + u 2 2 B ( z 2 ) + ⋯ ) 3 ) + 1 4 ! ( [ u 4 ] ( u 1 B ( z ) + ⋯ ) 4 ) = B ( z 4 ) 4 + 1 2 ! ( B ( z 2 ) 2 4 + 2 B ( z ) B ( z 3 ) 3 ) + 1 3 ! ( 3 B ( z ) 2 B ( z 2 ) 2 ) + B ( z ) 4 4 ! = B ( z ) 4 24 + B ( z ) 2 B ( z 2 ) 4 + B ( z ) B ( z 3 ) 3 + B ( z 2 ) 2 8 + B ( z 4 ) 4 \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} [ u 4 ] A ( z , u ) = 0 ! 1 ( [ u 4 ] 1 ) + 1 ! 1 ( [ u 4 ] ( 1 u B ( z ) + 2 u 2 B ( z 2 ) + 3 u 3 B ( z 3 ) + 4 u 4 B ( z 4 ) + ⋯ ) ) + 2 ! 1 ( [ u 4 ] ( 1 u B ( z ) + 2 u 2 B ( z 2 ) + 3 u 3 B ( z 3 ) + ⋯ ) 2 ) + 3 ! 1 ( [ u 4 ] ( 1 u B ( z ) + 2 u 2 B ( z 2 ) + ⋯ ) 3 ) + 4 ! 1 ( [ u 4 ] ( 1 u B ( z ) + ⋯ ) 4 ) = 4 B ( z 4 ) + 2 ! 1 ( 4 B ( z 2 ) 2 + 3 2 B ( z ) B ( z 3 ) ) + 3 ! 1 ( 2 3 B ( z ) 2 B ( z 2 ) ) + 4 ! B ( z ) 4 = 24 B ( z ) 4 + 4 B ( z ) 2 B ( z 2 ) + 3 B ( z ) B ( z 3 ) + 8 B ( z 2 ) 2 + 4 B ( z 4 )
Thus for is an expression in . A = K k ( B ) \mathcal{A}=\mathfrak{K}_k(\mathcal{B}) A = K k ( B ) A ( z ) A(z) A ( z ) B ( z ) , B ( z 2 ) , … , B ( z k ) B(z),B(z^2),\dots ,B(z^k) B ( z ) , B ( z 2 ) , … , B ( z k )
Note that a restricted construction does not require . K k ( B ) \mathfrak{K}_k(\mathcal{B}) K k ( B ) B 0 = ∅ \mathcal{B}_0=\varnothing B 0 = ∅
Common restricted constructions
PSET 2 ( A ) : A ( z ) 2 2 − A ( z 2 ) 2 MSET 2 ( A ) : A ( z ) 2 2 + A ( z 2 ) 2 CYC 2 ( A ) : A ( z ) 2 2 + A ( z 2 ) 2 \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} PSET 2 ( A ) MSET 2 ( A ) CYC 2 ( A ) : 2 A ( z ) 2 − 2 A ( z 2 ) : 2 A ( z ) 2 + 2 A ( z 2 ) : 2 A ( z ) 2 + 2 A ( z 2 ) PSET 3 ( A ) : A ( z ) 3 6 − A ( z ) A ( z 2 ) 2 + A ( z 3 ) 3 MSET 3 ( A ) : A ( z ) 3 6 + A ( z ) A ( z 2 ) 2 + A ( z 3 ) 3 CYC 3 ( A ) : A ( z ) 3 3 + 2 A ( z 3 ) 3 \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} PSET 3 ( A ) MSET 3 ( A ) CYC 3 ( A ) : 6 A ( z ) 3 − 2 A ( z ) A ( z 2 ) + 3 A ( z 3 ) : 6 A ( z ) 3 + 2 A ( z ) A ( z 2 ) + 3 A ( z 3 ) : 3 A ( z ) 3 + 3 2 A ( z 3 ) PSET 4 ( A ) : A ( z ) 4 24 − A ( z ) 2 A ( z 2 ) 4 + A ( z ) A ( z 3 ) 3 + A ( z 2 ) 2 8 − A ( z 4 ) 4 MSET 4 ( A ) : A ( z ) 4 24 + A ( z ) 2 A ( z 2 ) 4 + A ( z ) A ( z 3 ) 3 + A ( z 2 ) 2 8 + A ( z 4 ) 4 CYC 4 ( A ) : A ( z ) 4 4 + A ( z 2 ) 2 4 + A ( z 4 ) 2 \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} PSET 4 ( A ) MSET 4 ( A ) CYC 4 ( A ) : 24 A ( z ) 4 − 4 A ( z ) 2 A ( z 2 ) + 3 A ( z ) A ( z 3 ) + 8 A ( z 2 ) 2 − 4 A ( z 4 ) : 24 A ( z ) 4 + 4 A ( z ) 2 A ( z 2 ) + 3 A ( z ) A ( z 3 ) + 8 A ( z 2 ) 2 + 4 A ( z 4 ) : 4 A ( z ) 4 + 4 A ( z 2 ) 2 + 2 A ( z 4 )
The calculation is effective but cumbersome; see the references on Pólya enumeration and cycle indices. Reference Reference
Example LOJ 6538. Counting Alkyls, strengthened version, strengthened version
Problem : Find the number of unordered trees with vertices, rooted at a node of degree at most , while every other node has degree at most , modulo . Assume . n n n 3 3 3 4 4 4 998244353 998244353 998244353 1 ≤ n ≤ 10 5 1\leq n\leq 10^5 1 ≤ n ≤ 1 0 5
Solution : Let the combinatorial class be . Then T \mathcal{T} T
T = { ∙ } × MSET 0 , 1 , 2 , 3 ( T ) \mathcal{T}=\lbrace \bullet\rbrace\times\operatorname{MSET}_{0,1,2,3}(\mathcal{T}) T = { ∙ } × MSET 0 , 1 , 2 , 3 ( T ) Alternatively, let . Then T ^ = T + { ϵ } \hat{\mathcal{T}}=\mathcal{T}+\lbrace \epsilon\rbrace T ^ = T + { ϵ }
T ^ = { ϵ } + { ∙ } × MSET 3 ( T ^ ) \hat{\mathcal{T}}=\lbrace \epsilon\rbrace +\lbrace \bullet\rbrace\times\operatorname{MSET}_{3}(\hat{\mathcal{T}}) T ^ = { ϵ } + { ∙ } × MSET 3 ( T ^ ) The same result can be obtained.
References
Philippe Flajolet and Robert Sedgewick. . Reference