组合数学

掌握高级组合数学技巧，解决复杂计数问题

概述

组合数学是算法竞赛中的核心数学分支，涉及计数、排列、组合等问题。本章节深入探讨容斥原理、卡塔兰数、生成函数等高级技巧，为解决世界级竞赛中的复杂组合问题奠定基础。

核心内容

1. 容斥原理

容斥原理是解决复杂计数问题的强大工具，通过加减交替计算集合的并集大小。

基本原理

// 容斥原理：计算多个集合的并集大小
// |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 计算能被某些数整除的数的个数（1到n）
long long inclusionExclusion(long long n, vector<int>& divisors) {
    int m = divisors.size();
    long long result = 0;
    
    // 枚举所有子集
    for (int mask = 1; mask < (1 << m); mask++) {
        long long lcm = 1;
        int bits = 0;
        
        // 计算当前子集的LCM
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                lcm = lcm / __gcd(lcm, (long long)divisors[i]) * divisors[i];
                bits++;
                if (lcm > n) break; // 优化：LCM过大直接跳出
            }
        }
        
        // 根据子集大小决定加减
        if (bits % 2 == 1) {
            result += n / lcm;
        } else {
            result -= n / lcm;
        }
    }
    
    return result;
}

int main() {
    long long n = 100;
    vector<int> divisors = {2, 3, 5};
    
    // 计算1到100中能被2、3或5整除的数的个数
    cout << inclusionExclusion(n, divisors) << endl;
    
    return 0;
}

高级应用：错位排列

// 错位排列：计算n个元素的完全错位排列数
#include <iostream>
#include <vector>
using namespace std;

// 使用容斥原理计算错位排列
long long derangements(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    
    // D(n) = n! * Σ(k=0 to n) (-1)^k / k!
    long long factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial *= i;
    }
    
    double sum = 0;
    long long fact = 1;
    for (int k = 0; k <= n; k++) {
        if (k > 0) fact *= k;
        sum += (k % 2 == 0 ? 1.0 : -1.0) / fact;
    }
    
    return (long long)(factorial * sum + 0.5);
}

// 递推公式计算错位排列（更高效）
long long derangementsDP(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    
    vector<long long> dp(n + 1);
    dp[0] = 1;
    dp[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        // D(n) = (n-1) * (D(n-1) + D(n-2))
        dp[i] = (long long)(i - 1) * (dp[i - 1] + dp[i - 2]);
    }
    
    return dp[n];
}

int main() {
    for (int n = 0; n <= 10; n++) {
        cout << "D(" << n << ") = " << derangementsDP(n) << endl;
    }
    return 0;
}

2. 卡塔兰数

卡塔兰数在组合数学中有着广泛应用，从括号匹配到二叉树计数，是解决递归结构问题的关键。 

// 卡塔兰数的多种计算方法
#include <iostream>
#include <vector>
using namespace std;

// 方法1：递推公式 C(n) = Σ(i=0 to n-1) C(i) * C(n-1-i)
long long catalanDP(int n) {
    vector<long long> catalan(n + 1, 0);
    catalan[0] = catalan[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            catalan[i] += catalan[j] * catalan[i - 1 - j];
        }
    }
    
    return catalan[n];
}

// 方法2：组合数公式 C(n) = C(2n, n) / (n + 1)
long long catalanCombination(int n) {
    // 计算组合数 C(2n, n)
    long long result = 1;
    for (int i = 0; i < n; i++) {
        result = result * (2 * n - i) / (i + 1);
    }
    return result / (n + 1);
}

// 应用1：有效括号序列数量
int validParentheses(int n) {
    return catalanDP(n);
}

// 应用2：二叉搜索树数量
int numBST(int n) {
    return catalanDP(n);
}

// 应用3：山脉数组数量
int mountainArrays(int n) {
    if (n % 2 == 0) return 0; // 偶数长度无法形成山脉
    return catalanDP(n / 2);
}

// 应用4：凸多边形三角剖分数
int triangulations(int n) {
    if (n < 3) return 0;
    return catalanDP(n - 2);
}

int main() {
    int n = 10;
    cout << "Catalan数：" << endl;
    for (int i = 0; i <= n; i++) {
        cout << "C(" << i << ") = " << catalanDP(i) << endl;
    }
    
    cout << "\n应用示例：" << endl;
    cout << "5对括号的有效序列数： " << validParentheses(5) << endl;
    cout << "5个节点的BST数量： " << numBST(5) << endl;
    cout << "六边形三角剖分数： " << triangulations(6) << endl;
    
    return 0;
}

3. 高级组合技巧

生成函数

生成函数是组合数学中的强大工具，能够将组合问题转化为代数问题。 

// 生成函数应用：整数分拆
#include <iostream>
#include <vector>
using namespace std;

// 计算整数n的分拆数（不同顺序视为同一分拆）
int partitions(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    
    // 对每个可能的部分进行处理
    for (int part = 1; part <= n; part++) {
        for (int sum = part; sum <= n; sum++) {
            dp[sum] += dp[sum - part];
        }
    }
    
    return dp[n];
}

// 计算整数n的不同分拆数（所有部分都不同）
int distinctPartitions(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    
    for (int part = 1; part <= n; part++) {
        for (int sum = n; sum >= part; sum--) {
            dp[sum] += dp[sum - part];
        }
    }
    
    return dp[n];
}

// 五边形数定理应用：快速计算分拆数
vector<int> fastPartitions(int n) {
    vector<int> p(n + 1, 0);
    p[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int k = 1; ; k++) {
            // 五边形数：k(3k-1)/2
            int pent1 = k * (3 * k - 1) / 2;
            int pent2 = k * (3 * k + 1) / 2;
            
            if (pent1 > i) break;
            
            // 应用递推关系
            if (k % 2 == 1) {
                p[i] += p[i - pent1];
                if (pent2 <= i) p[i] += p[i - pent2];
            } else {
                p[i] -= p[i - pent1];
                if (pent2 <= i) p[i] -= p[i - pent2];
            }
        }
    }
    
    return p;
}

int main() {
    int n = 20;
    
    cout << "整数分拆：" << endl;
    for (int i = 1; i <= 10; i++) {
        cout << "P(" << i << ") = " << partitions(i) << endl;
    }
    
    cout << "\n不同分拆：" << endl;
    for (int i = 1; i <= 10; i++) {
        cout << "Q(" << i << ") = " << distinctPartitions(i) << endl;
    }
    
    // 验证五边形数定理
    vector<int> fast = fastPartitions(n);
    cout << "\n快速算法验证：P(" << n << ") = " << fast[n] << endl;
    cout << "标准算法：P(" << n << ") = " << partitions(n) << endl;
    
    return 0;
}

Burnside引理

// Burnside引理：计算在群作用下的不同着色数
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 计算最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算圆形项链的不同着色数（可旋转和翻转）
long long necklaceColorings(int n, int k) {
    if (n == 0) return 1;
    
    long long result = 0;
    
    // 旋转对称：对每个可能的旋转角度
    for (int i = 0; i < n; i++) {
        int cycles = gcd(n, i);
        result += (long long)pow(k, cycles);
    }
    
    // 翻转对称
    if (n % 2 == 1) {
        // 奇数：n条翻转轴，每条轴固定1个珠子
        result += n * (long long)pow(k, (n + 1) / 2);
    } else {
        // 偶数：n/2条穿过顶点的轴 + n/2条穿过边中点的轴
        result += (n / 2) * (long long)pow(k, n / 2 + 1);
        result += (n / 2) * (long long)pow(k, n / 2);
    }
    
    // 应用Burnside引理：平均不动点数
    return result / (2 * n);
}

// 计算正方形的不同着色数（4个顶点，k种颜色）
long long squareColorings(int k) {
    // 8个对称操作：恒等、3个旋转、4个翻转
    long long result = 0;
    
    // 恒等变换：所有着色都不动
    result += (long long)pow(k, 4);
    
    // 90度和270度旋转：4个顶点必须同色
    result += 2 * k;
    
    // 180度旋转：对角顶点同色
    result += (long long)k * k;
    
    // 4个翻转：相邻顶点成对同色
    result += 4 * (long long)k * k;
    
    return result / 8;
}

int main() {
    cout << "项链着色问题：" << endl;
    for (int n = 3; n <= 8; n++) {
        for (int k = 2; k <= 4; k++) {
            cout << "n=" << n << ", k=" << k << ": " 
                 << necklaceColorings(n, k) << " 种不同着色" << endl;
        }
    }
    
    cout << "\n正方形着色：" << endl;
    for (int k = 2; k <= 5; k++) {
        cout << k << " 种颜色： " 
             << squareColorings(k) << " 种不同着色" << endl;
    }
    
    return 0;
}

解题技巧

🎯 问题识别

学会识别不同类型的组合问题：计数问题用容斥原理，递归结构考虑卡塔兰数，对称问题应用Burnside引理。

⚡ 计算优化

大数计算时注意溢出，使用模运算和快速幂。预计算组合数和阶乘可以显著提高效率。

🔄 递推关系

许多组合问题都有优美的递推关系。寻找状态转移方程，往往比直接计算更高效。

🧮 数学洞察

深入理解组合恒等式和生成函数，它们是解决复杂组合问题的强大工具。

📚 章节目录