part1 \textbf{part1} part1 我们定义组合类是一系列组合对象组成的可数集合，组合类都是由一些更本质的组合类构造出来的。我们对每个组合类
A \mathcal A A 都定义了一个大小函数
f : A → N f:A\to \mathbb N f : A → N ，满足对于任意
k ∈ N k\in \mathbb N k ∈ N 只有有限个组合对象
a ∈ A a\in \mathcal A a ∈ A 满足
f ( a ) = k f(a)=k f ( a ) = k ，我们记
f ( a ) f(a) f ( a ) 为
∣ a ∣ |a| ∣ a ∣ ，在需要指出组合类的情况下记为
∣ a ∣ A |a|_\mathcal A ∣ a ∣ A 。
我们将
a ∈ A , ∣ a ∣ = n a\in \mathcal A,|a|=n a ∈ A , ∣ a ∣ = n 的全体记作
A n \mathcal A_n A n ，并以此可以构造一个计数序列满足
A [ n ] = ∣ A n ∣ A[n]=|\mathcal A_n| A [ n ] = ∣ A n ∣ 。
对于两个组合类
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 。我们并不关心对于我们所需的单一性质之外的其他信息，具体的我们忽视组合对象除了大小和组合结构以外的其他信息，从而将很多组合操作简单的映射到并列操作上。
a , b ∈ A a,b\in \mathcal A a , b ∈ A 等价当且仅当
( a , b ) ∈ G (a,b)\in\mathbf G ( a , b ) ∈ G ，我们将其定义为
a G b a\mathbf Gb a G b 。
对于一个组合类，其上的一个等价关系
G \mathbf G G 是
A × A \mathcal A\times \mathcal A A × A 的一个子集
( a , b ) ∣ a , b ∈ A (a,b)|a,b\in \mathcal A ( a , b ) ∣ a , b ∈ A 。其满足以下三个条件：
a ∈ A ⇒ ( a , a ) ∈ G a \in \mathcal A \Rightarrow (a, a) \in \textbf G a ∈ A ⇒ ( a , a ) ∈ G ( a , b ) ∈ G , a ≠ b ⇒ ( b , a ) ∈ G (a, b) \in \textbf G, a \neq b \Rightarrow (b, a) \in \textbf G ( a , b ) ∈ G , a = b ⇒ ( b , a ) ∈ G ( a , b ) , ( b , c ) ∈ G ⇒ ( a , c ) ∈ G (a, b), (b, c) \in \textbf G \Rightarrow (a, c) \in \textbf G ( a , b ) , ( b , c ) ∈ G ⇒ ( a , c ) ∈ G
对于一个组合类
A \mathcal A A 和等价关系
G \mathbf G G 取
S ⊆ A \mathcal S \subseteq \mathcal A S ⊆ A 若
∀ a , b ∈ S , ( a , b ) ∈ G \forall a, b \in \mathcal S, (a, b) \in \textbf G ∀ a , b ∈ S , ( a , b ) ∈ G ，
∀ a ∈ S , b ∈ ∁ A S , ( a , b ) ∉ G \forall a \in \mathcal S, b \in \complement_{\mathcal A}\mathcal S, (a, b) \not \in \textbf G ∀ a ∈ S , b ∈ ∁ A S , ( a , b ) ∈ G 则称
S \mathcal S S 是
G \textbf G G 下的一个等价类。实际讨论中一个等价类的组合对象大小一般相等。
对于一个组合类
A \mathcal A A 和等价关系
G \mathbf G G 取一个新的组合类
A ˉ = A / G \bar{\mathcal A}=\mathcal A/G A ˉ = A / G ，满足
G \mathbf G G 下
A \mathcal A A 的任意一个等价类在
A ˉ \bar {\mathcal A} A ˉ 中只有一个元素作为代表元，一般取某一性质下最小元素例如字典序最小，有时也定义新的组合类的组合对象是原组合类的等价类，就是说新组合类是组合类的组合类。
我们知道一个无标号组合类
A \mathcal A A 对应的 OGF 其形式幂级数为
A ( x ) = ∑ i = 0 ∞ a i x i A(x) = \sum\limits_{i=0}^{\infty} a_ix^i A ( x ) = i = 0 ∑ ∞ a i x i ，其中
x x x 为占位元。它也可以被等价的写作
A ( x ) = ∑ a ∈ A x ∣ a ∣ A(x)=\sum\limits_{a\in \mathcal A}x^{|a|} A ( x ) = a ∈ A ∑ x ∣ a ∣ ，我们称此处的
z ∣ a ∣ z^{|a|} z ∣ a ∣ 为
a a a 的幂表示，这里的
x x x 依然只是单位元。两个 OGF 之间的运算具有一系列的组合意义，OGF 之间的加法与两个不相交组合类的并同构。OGF 之间的乘法和这两个组合类的笛卡尔积同构。
我们记
ϵ \epsilon ϵ 为中性对象，对应的组合类为
E = { ϵ } \mathcal E = \{\epsilon \} E = { ϵ } 称为中性类，恒有
∣ ϵ ∣ = 0 |\epsilon|=0 ∣ ϵ ∣ = 0 ，因此有
E \mathcal E E 的生成函数
E ( x ) = 1 E(x)=1 E ( x ) = 1 。两个中性对象可能不同。
我们有
A ≅ E × A ≅ A × E \mathcal A \cong \mathcal E\times \mathcal A \cong \mathcal A\times \mathcal E A ≅ E × A ≅ A × E ，对于任意组合类
A \mathcal A A 定义
A 0 = E \mathcal A^0=\mathcal E A 0 = E ，但是由于组合意义所以
E \mathcal E E 不能作为笛卡尔积的单位元。由于集合论中需要集合内无重复元素，我们可以对两个类乘上不同的中性类，这样两个集合中可能相同的对象也不同。我们定义两个类
A , B \mathcal A,\mathcal B A , B 的集合并
A + B \mathcal A+\mathcal B A + B 为
( E 1 × A ) ∪ ( E 2 × B ) (\mathcal E_1 \times \mathcal A) \cup (\mathcal E_2 \times \mathcal B) ( E 1 × A ) ∪ ( E 2 × B ) 。
我们记
∙ \bullet ∙ 为原子对象，对应的组合类记作
Z = { ∙ } \mathcal Z=\{\bullet\} Z = { ∙ } 称为原子类。恒有
∣ ∙ ∣ = 1 |\bullet|=1 ∣ ∙ ∣ = 1 因此其对应的生成函数
Z ( x ) = x Z(x)=x Z ( x ) = x 。原子对象一般用于合并数个组合对象，比如作为树的根出现。
01 串的组合类为
S \mathcal S S ，我们要求的就是
∣ S n ∣ |\mathcal S_n| ∣ S n ∣ 。可以写出
S = { ϵ , 0 , 1 , 00 , 01 , 10 , 11 , ⋯ } \mathcal S=\{\epsilon,0,1,00,01,10,11,\cdots\} S = { ϵ , 0 , 1 , 00 , 01 , 10 , 11 , ⋯ } 。我们发现对于一个 01 串要么是空串要么就是 0/1 接在一个 01 串前面。可以写出
S = ϵ + { 0 , 1 } × S \mathcal S=\epsilon+\{0,1\}\times \mathcal S S = ϵ + { 0 , 1 } × S ，写成生成函数就是
S ( x ) = 1 + 2 x S ( x ) S(x)=1+2xS(x) S ( x ) = 1 + 2 x S ( x ) ，求解这个方程得到
1 1 − 2 x \frac{1}{1-2x} 1 − 2 x 1 ，答案写成集合幂级数的形式就是
[ x n ] ∑ i = 0 ∞ 2 i x i \left[x^n\right]\sum_{i=0}^{\infty}2^ix^i [ x n ] ∑ i = 0 ∞ 2 i x i ，也就是
2 n 2^n 2 n 。
考虑卡特兰数有一个很经典的组合意义：
n n n 个节点的二叉树个数，对于一个二叉树，要么为空要么形如左子树-根-右子树。前面提到根可以视为
∙ \bullet ∙ ，那么我们就知道
C = ϵ + C × Z × C \mathcal C=\epsilon+\mathcal C\times \mathcal Z\times \mathcal C C = ϵ + C × Z × C 。翻译成生成函数就是
C ( x ) = 1 + x C ( x ) 2 C(x)=1+xC(x)^2 C ( x ) = 1 + x C ( x ) 2 。解方程得到
C ( x ) = 1 − 1 − 4 x 2 x C(x)=\frac{1-\sqrt{1-4x}}{2x} C ( x ) = 2 x 1 − 1 − 4 x 。广义二项式定理展开即可。
part2 \textbf{part2} part2 有标号体系是无标号体系的自然拓展。有标号体系和无标号体系的区别在于，有标号所关注的组合对象有两两不同的标号，可以彼此区分。我们将标号集合视作正整数集合。一个排列可以被视作一系列两两不同正整数依次排开，而循环分解将这排列视作循环有向图的组合，图的每个顶点都有着正整数标号。
有标号体系内的操作基于一类特殊的乘法：有标号乘。这是对无标号体系中笛卡尔积的自然模拟。同样的，我们也需要对无标号体系中的 OGF 进行自然模拟，也就是我们熟知的 EGF。
我们所处理的对象和无标号体系一样具有有限的组合类与组合对象。但不同的，组合对象是有标签的。每个组合对象都 有颜色/被分配标号 ，以保证组合对象两两不同。
一个具有
n n n 个部分的离散结构其
n n n 个部分分别有一个标号，这些标号组成了一个长度为
n n n 的正整数集，我们称满足这条件的对象是弱标号的。我们称满足这条件的对象是弱标号的。等价地，也可以说每个部分都有标号，这种叙述隐含了标号是属于
Z \mathbb Z Z 的彼此不同的数。一个大小为
n n n 的强标号/有标号对象需要是弱标号的，其标号所组成的集合是
[ 1 , n ] [1,n] [ 1 , n ] 。
一个有标号类是一个由有标号对象组成的组合类，我们上文无标号中提到的组合类命名为无标号类以做区分。一个有标号类
A \mathcal A A 可以用她的计数序列
A [ i ] A[i] A [ i ] 或其中元素表示，即
A ^ ( x ) = ∑ i = 0 ∞ A [ i ] x i i ! = ∑ α ∈ A x ∣ α ∣ ∣ α ∣ ! \hat A(x)=\sum\limits_{i=0}^{\infty} A[i] \frac{x^i}{i!}=\sum\limits_{\alpha\in \mathcal A} \frac{x^{|\alpha|}}{|\alpha|!} A ^ ( x ) = i = 0 ∑ ∞ A [ i ] i ! x i = α ∈ A ∑ ∣ α ∣ ! x ∣ α ∣ 在无标号体系中，我们已经见到了中性类和原子类发挥的作用，不妨在有标号体系中也定义这样的结构。
我们记
ϵ \epsilon ϵ 为中性对象，对应的组合类为
E = { ϵ } \mathcal E = \{\epsilon \} E = { ϵ } 称为中性类，恒有
∣ ϵ ∣ = 0 |\epsilon|=0 ∣ ϵ ∣ = 0 ，因此有
E \mathcal E E 的生成函数
E ^ ( x ) = 1 \hat E(x)=1 E ^ ( x ) = 1 。
我们记
∙ \bullet ∙ 为原子对象，对应的组合类记作
Z = { ∙ } \mathcal Z=\{\bullet\} Z = { ∙ } 称为原子类。我们令对象中唯一的元素标号恒为
1 1 1 ，因此原子类是强标号的。恒有
∣ ∙ ∣ = 1 |\bullet|=1 ∣ ∙ ∣ = 1 因此其对应的生成函数
Z ^ ( x ) = x \hat Z(x)=x Z ^ ( x ) = x 。
有标号类的集合并可以类似无标号类的集合并一样定义。
而有标号类的乘法不好得到良定义，因为笛卡尔积可能导出非良标号对象，也就是两个有标号对象可能存在标号重叠的情况。我们单独定义新的运算：有标号乘法，这可以自然的翻译为 EGF 之间的乘法。
我们接下来要讨论的是重标号操作。由于我们需要让两个强标号对象合并后仍然是强标号的，我们需要进行重标号操作，这种操作要求新的标号的大小关系中保留原标号之间的大小关系。主要有两种这种操作：减缩和增扩。
减缩：对于一个大小为 n 的弱标号结构，减缩操作将每个点的标号映射到整数区间 [ 1 , n ] [1,n] [ 1 , n ]
增扩：我们需要一个增扩函数 e : [ 1 , n ] → Z e:[1,n]\to \mathbb Z e : [ 1 , n ] → Z ∀ i ∈ [ 1 , n ] , e ( i ) > i \forall i\in [1, n], e(i) > i ∀ i ∈ [ 1 , n ] , e ( i ) > i α \alpha α α ^ \hat \alpha α ^ α \alpha α k k k α ^ \hat \alpha α ^ e ( k ) e(k) e ( k ) α \alpha α e ( α ) e(\alpha) e ( α )
我们可以通过这些操作设计出一种适于有标号类的乘法，称为 partitional product。有标号乘法的思路就是对合并后的部分进行重标号，以避免出现同一个标号出现多次。我们取两个有标号对象
β ∈ B \beta \in \mathcal B β ∈ B 和
γ ∈ C \gamma \in \mathcal C γ ∈ C 我们定义这两个对象的有标号乘法（简称乘法）记作
β × γ \beta \times \gamma β × γ ，一个集合，其包含所有由
( β , γ ) (\beta, \gamma) ( β , γ ) 生成的强标号的有序对
( β ′ , γ ′ ) (\beta', \gamma ') ( β ′ , γ ′ ) 。具体的，
β × γ = { ( β ′ , γ ) ∣ ( β ′ , γ ′ ) \beta\times \gamma = \{ (\beta', \gamma) \mid (\beta', \gamma ') β × γ = {( β ′ , γ ) ∣ ( β ′ , γ ′ ) 强标号 ,
ρ ( β ′ ) = β , ρ ( γ ′ ) = γ } \rho(\beta') = \beta, \rho(\gamma') = \gamma \} ρ ( β ′ ) = β , ρ ( γ ′ ) = γ } 。
注意到有标号乘积导出的构造中每个对象都是强标号的。假设
β , γ \beta, \gamma β , γ 都是强标号的，大小分别为
n 1 , n 2 n_1, n_2 n 1 , n 2 ，则分配标号的方案总共有
( n 1 , n 2 n 1 ) \binom{n_1,n_2}{n_1} ( n 1 n 1 , n 2 ) 种。也就是说
∣ β × γ ∣ = ( n 1 + n 2 n 1 ) \lvert\beta\times \gamma\rvert = \dbinom{n_1 + n_2}{n_1} ∣ β × γ ∣ = ( n 1 n 1 + n 2 ) 。
我们从有标号对象拓展到有标号类
B \mathcal B B 和
C \mathcal C C ，定义为
B × C = ⋃ β ∈ B , γ ∈ C β × γ \mathcal B \times \mathcal C = \bigcup\limits_{\beta \in \mathcal B, \gamma \in \mathcal C} \beta\times \gamma B × C = β ∈ B , γ ∈ C ⋃ β × γ ，随后我们可以自然地描述计数序列的关系了。
设
A = B × C \mathcal A=\mathcal B\times \mathcal C A = B × C 我们知道
A n = ⋃ ∣ β ∣ + ∣ γ ∣ = n β × γ \mathcal A_n = \bigcup_{|\beta| + |\gamma| = n} \beta\times \gamma A n = ⋃ ∣ β ∣ + ∣ γ ∣ = n β × γ ，
A [ n ] = ∑ i + j = n ( n i ) B [ i ] × C [ j ] A[n] = \sum_{i + j = n} \binom{n}{i} B[i]\times C[j] A [ n ] = ∑ i + j = n ( i n ) B [ i ] × C [ j ] 。
通过这个构造，我们就可以构造有标号集合、有标号序列和有标号循环了，方法和无标号的构造法类似。
part3 \textbf{part3} part3 ↔ \leftrightarrow ↔ 任意无标号类
A \mathcal A A 都有一个对应的有标号类
A ^ \hat{\mathcal A} A ^ 。
A \mathcal A A 是通过
A ^ \hat{\mathcal A} A ^ 中的元素忽略标号得到的。这个过程需要一个等价关系
S \textbf S S ，对于
a , b ∈ A ^ a,b\in \hat{\mathcal A} a , b ∈ A ^ ，
a S b a\textbf Sb a S b 当且仅当存在任意的重标号方案，使得
a a a 在重标号后可以得到
b b b 。那么
A = A ^ / S \mathcal A = \hat{\mathcal A} / \textbf S A = A ^ / S 。对于一个
S \textbf S S 下元素大小为
n n n 的等价类，我们知道其大小在
[ 1 , n ! ] [1,n!] [ 1 , n !] 之间。故
1 ≤ ∣ A n ^ ∣ ∣ A n ∣ ≤ n ! 1 \le \dfrac{\lvert \hat{\mathcal A_n} \rvert}{\lvert { \mathcal A } _n \rvert} \le n! 1 ≤ ∣ A n ∣ ∣ A n ^ ∣ ≤ n !