组合数学中的组合类与计数生成函数 我们从一个具体问题开始：考虑用红色和蓝色的小球排成一列，其中红色球不能连续出现。比如长度为3的序列中，合法的有"红蓝红"、"蓝红蓝"、"蓝蓝蓝"等，非法的有"红红蓝"。我们如何系统化地计数所有长度为n的合法序列？ 第一步，定义组合类。一个组合类A是一个有限或可数无穷的集合，并配有一个大小函数|·|: A → ℕ，将每个元素映射到一个非负整数（通常是该元素的某种"尺寸"）。在我们的例子中，组合类A是所有不含连续红色球的序列的集合，大小函数是序列的长度。 第二步，引入生成函数。组合类A的计数生成函数是形式幂级数：A(x) = Σ_ {a∈A} x^{|a|} = Σ_ {n≥0} a_ n x^n，其中a_ n是A中大小为n的元素个数。生成函数将组合计数问题转化为代数对象的系数提取问题。 第三步，利用组合构造建立方程。对于我们的序列问题，可以这样分解：任何合法序列要么是空序列，要么以蓝色球开头（后面接任意合法序列），要么以单个红色球加一个蓝色球开头（再接合法序列）。用符号表示：A = {ε} + {蓝} × A + {红} × {蓝} × A。这里ε代表空序列，×表示笛卡尔积。 第四步，将组合构造转化为生成函数方程。根据生成函数的性质，不相交并对应生成函数加法，笛卡尔积对应生成函数乘法。设蓝色球和红色球的大小均为1（它们贡献长度1），则生成函数方程化为：A(x) = 1 + x·A(x) + x·x·A(x) = 1 + xA(x) + x²A(x)。 第五步，求解生成函数。整理方程得：A(x) - xA(x) - x²A(x) = 1，即A(x)(1 - x - x²) = 1，所以A(x) = 1/(1 - x - x²)。这正是斐波那契数的生成函数！这意味着长度为n的合法序列数就是第n+1个斐波那契数（通常定义F₀=0, F₁=1，则a_ n = F_ {n+1}）。 通过这个例子，我们看到了组合类与生成函数方法的核心步骤：定义组合类→建立组合构造→转化为生成函数方程→求解→解释系数。这种方法能将复杂的组合约束转化为可解的代数方程，是组合计数的强大工具。