人工智能之数学基础 离散数学----公式参考

第三章 组合数学

前言

组合数学是离散数学的核心分支，研究离散对象的计数、构造与优化。它在密码学、算法设计、概率论、机器学习特征工程、AI 组合优化等领域有广泛应用。本文系统讲解：

基本计数原理（加法/乘法原理）排列与组合（含重复、环排列）容斥原理（Inclusion-Exclusion Principle）生成函数（Generating Functions）简介AI 中的组合优化问题（如子集选择、超参数组合）配套 Python 代码实现（math、itertools、自定义函数、实际案例）一、基本计数原理1. 加法原理（Sum Rule）

若完成一件事有 $ m $ 种互斥方式，另一件事有 $ n $ 种互斥方式，则完成其中任一件事共有 $ m + n $ 种方式。

✅ 示例：从 A 到 B 有 3 条路，从 A 到 C 有 2 条路，则从 A 到 B 或 C 共有 $ 3 + 2 = 5 $ 种走法。

2. 乘法原理（Product Rule）

若完成一件事需分两步，第一步有 $ m $ 种方式，第二步有 $ n $ 种方式，则总共有 $ m \times n $ 种方式。

✅ 示例：3 件上衣 × 4 条裤子 = 12 套搭配。

二、排列与组合1. 排列（Permutation）— 顺序重要(1) 无重复排列

从 $ n $ 个不同元素中选 $ r $ 个进行排列：

$$ P(n, r) = \frac{n!}{(n - r)!} $$

全排列：$ P(n, n) = n! $(2) 有重复排列

若元素可重复（如密码），则 $ n $ 个位置每个有 $ k $ 种选择 → $ k^n $

(3) 环排列（Circular Permutation）

$ n $个不同元素围成一圈的排列数为：

$$ (n - 1)! $$

因旋转视为相同（固定一人，其余排列）

2. 组合（Combination）— 顺序无关

从 $ n $ 个不同元素中选 $ r $ 个（不考虑顺序）：

$$ C(n, r) = \binom{n}{r} = \frac{n!}{r!(n - r)!} $$

性质：$ \binom{n}{r} = \binom{n}{n - r} $帕斯卡恒等式：$ \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} $二项式定理：

$$ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k} $$

3. 重复组合（Stars and Bars）

从 $ n $ 类物品中选 $ r $ 个（允许重复，顺序无关）：

$$ \binom{n + r - 1}{r} $$

✅ 示例：将 5 个相同球放入 3 个不同盒子 → $ \binom{3+5-1}{5} = \binom{7}{5} = 21 $

三、容斥原理（Inclusion-Exclusion Principle）

用于计算多个集合的并集大小，避免重复计数。

1. 两个集合

$$

|A \cup B| = |A| + |B| - |A \cap B| $$

2. 三个集合

$$

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| $$

3. 一般形式（n 个集合）

$$

\left| \bigcup{i=1}^n Ai \right| = \sum{k=1}^n (-1)^{k+1} \sum{1 \leq i1 < \cdots < ik \leq n} |A{i1} \cap \cdots \cap A{ik}| $$

经典应用：错位排列（Derangement）问题：$ n $ 封信装入 $ n $ 个信封，全部装错的方案数 $ D_n $公式：

$$ D_n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!}\right) $$

近似：$ D_n \approx \frac{n!}{e} $四、AI 中的组合优化问题

组合数学在 AI 中常以组合优化（Combinatorial Optimization） 形式出现：

问题类型

描述

组合数学工具

特征子集选择

从 $ d $ 个特征中选 $ k $ 个

$ \binom{d}{k} $ 枚举或启发式

超参数组合搜索

网格搜索所有参数组合

笛卡尔积（乘法原理）

任务分配

将 $ n $ 个任务分配给 $ n $ 个工人

排列 $ n! $

聚类标签分配

$ k $ 个簇标记 $ n $ 个点

$ k^n $（允许空簇）

路径规划

TSP 旅行商问题

全排列 $ (n-1)!/2 $

⚠️ 挑战：组合爆炸（Combinatorial Explosion） 例如：$ \binom{100}{10} \approx 1.7 \times 10^{13} $，无法穷举 → 需启发式（遗传算法、模拟退火）或剪枝。

五、Python 代码实现1. 导入库import mathfrom itertools import permutations, combinations, productfrom functools import lru_cache2. 基本计数函数# 阶乘def factorial(n): return math.factorial(n)# 排列 P(n, r)def perm(n, r): if r > n or r < 0: return 0 return math.perm(n, r) # Python 3.8+# 组合 C(n, r)def comb(n, r): if r > n or r < 0: return 0 return math.comb(n, r) # Python 3.8+# 重复组合def comb_with_replacement(n, r): return comb(n + r - 1, r)# 环排列def circular_perm(n): if n <= 1: return 1 return factorial(n - 1)# 测试print("P(5,3) =", perm(5, 3)) # 60print("C(5,3) =", comb(5, 3)) # 10print("重复组合 C(3,5) =", comb_with_replacement(3, 5)) # 21print("5人环排列 =", circular_perm(5)) # 243. 容斥原理：错位排列（Derangement）@lru_cache(maxsize=None)def derangement(n): """递归计算错位排列数 D_n""" if n == 0: return 1 if n == 1: return 0 return (n - 1) * (derangement(n - 1) + derangement(n - 2))# 或使用容斥公式def derangement_inclusion(n): total = 0 for k in range(n + 1): sign = (-1) ** k total += sign * comb(n, k) * factorial(n - k) return total# 测试for n in range(1, 8): print(f"D({n}) = {derangement(n)} (递归), {derangement_inclusion(n)} (容斥)")

输出：

D(1) = 0, D(2) = 1, D(3) = 2, D(4) = 9, D(5) = 44, ...

4. itertools 实战：生成所有组合/排列items = ['A', 'B', 'C']# 所有排列（全排列）print("全排列:", list(permutations(items)))# [('A','B','C'), ('A','C','B'), ...]# 选2个的组合print("C(3,2):", list(combinations(items, 2)))# [('A','B'), ('A','C'), ('B','C')]# 选2个的排列print("P(3,2):", list(permutations(items, 2)))# [('A','B'), ('A','C'), ('B','A'), ...]# 笛卡尔积（网格搜索基础）params = { 'lr': [0.01, 0.1], 'batch_size': [32, 64]}keys, values = zip(*params.items())configurations = [dict(zip(keys, v)) for v in product(*values)]print("超参数组合:")for cfg in configurations: print(cfg)5. AI 应用案例：特征子集选择（暴力 vs 启发式）import numpy as npfrom sklearn.datasets import make_classificationfrom sklearn.linear_model import LogisticRegressionfrom sklearn.model_selection import cross_val_score# 生成高维数据X, y = make_classification(n_samples=100, n_features=10, n_informative=3, random_state=42)n_features = X.shape[1]# 暴力搜索：所有大小为 k 的子集def brute_force_feature_selection(X, y, k=3): best_score = -1 best_subset = None for subset in combinations(range(n_features), k): X_sub = X[:, subset] score = np.mean(cross_val_score(LogisticRegression(), X_sub, y, cv=3)) if score > best_score: best_score = score best_subset = subset return best_subset, best_score# 测试（仅适用于小规模）if n_features <= 12: # 避免组合爆炸 subset, score = brute_force_feature_selection(X, y, k=3) print(f"最佳特征子集: {subset}, CV Score: {score:.4f}")else: print("特征数过多，跳过暴力搜索")

实际中常用 递归特征消除（RFE） 或 L1 正则化 替代暴力搜索。

6. 容斥原理：计算“至少一个”的概率

问题：从 1~100 中随机选一个数，能被 2、3 或 5 整除的概率？

def count_divisible(n, divisors): """使用容斥原理计算 [1,n] 中能被任意 divisor 整除的数的个数""" from itertools import combinations total = 0 m = len(divisors) for r in range(1, m + 1): for combo in combinations(divisors, r): lcm = np.lcm.reduce(combo) # 最小公倍数 count = n // lcm if r % 2 == 1: total += count else: total -= count return totaln = 100divisors = [2, 3, 5]count = count_divisible(n, divisors)prob = count / nprint(f"能被 2,3,5 中至少一个整除的数: {count}/{n} → 概率 ≈ {prob:.4f}")# 输出: 74/100 → 0.74六、高级话题：生成函数（简要）

生成函数将序列 $ \{a_n\} $ 编码为幂级数：

$$ G(x) = \sum{n=0}^{\infty} an x^n $$

普通生成函数：用于组合计数指数生成函数：用于排列计数

✅ 示例：$ (1 + x)^n $ 是 $ \binom{n}{k} $ 的生成函数。

# 使用 sympy 计算生成函数系数import sympy as spx = sp.symbols('x')n = 5gf = (1 + x)**ncoeffs = [sp.expand(gf).coeff(x, k) for k in range(n+1)]print(f"(1+x)^{n} 的系数:", coeffs) # [1, 5, 10, 10, 5, 1]七、总结

概念

公式

应用场景

排列

$ P(n,r) = \frac{n!}{(n-r)!} $

密码、调度

组合

$ \binom{n}{r} $

抽样、子集选择

重复组合

$ \binom{n+r-1}{r} $

资源分配

容斥原理

$ \

\cup A_i\

= \sum (-1)^{k+1} \

\cap A{ik}\

$

概率、错排

错位排列

$ Dn = n! \sum{k=0}^n \frac{(-1)^k}{k!} $

密码学、匹配问题

关键洞见：

组合爆炸是 AI 的核心挑战之一，需平衡精确性与效率；itertools 是 Python 处理组合问题的利器；容斥原理是处理“至少/至多”问题的通用框架；在特征工程、超参调优、强化学习动作空间设计中，组合思维至关重要。

后续

python过渡项目部分代码已经上传至gitee，后续会逐步更新。

资料关注

：咚咚王 gitee：https://gitee.com/wy18585051844/ai_learning

《Python编程：从入门到实践》 《利用Python进行数据分析》 《算法导论中文第三版》 《概率论与数理统计（第四版） (盛骤) 》 《程序员的数学》 《线性代数应该这样学第3版》 《微积分和数学分析引论》 《（西瓜书）周志华-机器学习》 《TensorFlow机器学习实战指南》 《Sklearn与TensorFlow机器学习实用指南》 《模式识别（第四版）》 《深度学习 deep learning》伊恩·古德费洛著 花书 《Python深度学习第二版(中文版)【纯文本】 (登封大数据 (Francois Choliet)) (Z-Library)》 《深入浅出神经网络与深度学习+(迈克尔·尼尔森（Michael+Nielsen）》 《自然语言处理综论 第2版》 《Natural-Language-Processing-with-PyTorch》 《计算机视觉-算法与应用(中文版)》 《Learning OpenCV 4》 《AIGC：智能创作时代》杜雨+&+张孜铭 《AIGC原理与实践：零基础学大语言模型、扩散模型和多模态模型》 《从零构建大语言模型（中文版）》 《实战AI大模型》 《AI 3.0》