组合简介（组合数学入门）
视频：油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook
组合计数是在顺序不重要时选择项目的方式。我们从一个简单的格子行走示例出发建立直觉，介绍二项式记号，推导公式，解释递推关系 
，并把所有内容联系到帕斯卡三角。
格子行走示例 — 从左下到右上路径
想象你只能向右（R）或向上（U）移动。要从左下走到需要三次向右和两次向上的点，每一条最短路径都是由五步组成的序列，其中包含三个 R 和两个 U。
走格子: 排列组合
每条有效路径只是从五个位置中选择两个放 U（其余为 R）。所以这样的路径数就是“从 5 中选 2”，记作 
（等于 
）。
示例序列：
R R U R U U R R R U R U R R U R R R U U U U R R R
二项式系数（组合）表示法
从 
个项目中选出 
个（顺序不重要）的方式数记为
或
两者都表示“从 n 中选 m”。
组合公式 — 基于阶乘的推导
先计算有序选择（排列）：从 n 个不同项目中取出长度为 的有序列表的数量为
每一个无序的 
项集合对应 
个有序列表（即这 m 项的排列）。除以 得到组合数：
把公式应用到格子示例
对于总步数 
和向上步数 
：
因此共有 10 条不同的最短路径。
为什么这个公式直观上合理
- 视角一 — 选择位置：从 个位置中选择放置 U 的 个位置；这就是 。
- 视角二 — 用排列除以顺序：先计算 n 步的所有排列，然后除去相同步序的重排（比如相同类型步的交换）。
帕斯卡三角与递推关系
把 
写成行可以形成帕斯卡三角：
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Pascal/帕斯卡三角形
这些项满足递推关系
然后，我们可以很容易的写出至顶向下的动态规划算法实现（用@cache实现记忆化式的递归搜索）：
from functools import cache
@cache
def C(n, m):
if m == 0:
return 1 # C(n, 0) = 1
if m == n:
return 1 # C(n, n) = 1
return C(n-1, m-1) + C(n-1, m)
当然，也可以用自底向上的方式实现：
def C_bottom_up(n, m):
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = 1 # C(i, 0) = 1
for j in range(1, min(i, m)+1):
if j == i:
dp[i][j] = 1 # C(i, i) = 1
else:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
return dp[n][m]
这个自底向上的实现直接从小问题累加到大问题，避免了递归开销，同时也很容易扩展到计算整个帕斯卡三角。
组合数的自底向上 DP 可以用 一维数组优化，利用 滚动数组 原理，因为每一行的计算只依赖上一行。重点是从 右往左更新，这样不会覆盖还没用到的数据。
下面是实现示例：
def C_one_dim(n, m):
dp = [0] * (m+1)
dp[0] = 1 # C(i, 0) = 1
for i in range(1, n+1):
# 从右往左更新，避免覆盖上一行数据
for j in range(min(i, m), 0, -1):
dp[j] = dp[j] + dp[j-1]
return dp[m]
示例：
print(C_one_dim(5, 2)) # 输出 10
✅ 优点：
- 空间复杂度 O(m)
- 时间复杂度 O(n*m)
- 可以方便扩展计算整行或整列组合数
组合证明 — 采苹果
想要从 个苹果中选 个。考虑最后一个苹果（编号为 n）：
如果你选了它，那就必须从前面的 
个中选剩下的 
个：有 
种方法。
如果你不选它，那就必须从前面的 个中选出全部 个：有 
种方法。
这两个互不相交的情况覆盖了所有可能，因此
（该恒等式正是构造帕斯卡三角的规则。）
递推关系的格子解释
在格子上，观察到达某点的任意路径的最后一步：要么是 R，要么是 U。以 R 结尾的路径来自某个前一点，以 U 结尾的路径来自另一个前一点。把这两组路径分别计数并相加就得到相同的加法规则。
常见的小值与说明
（选择零个）。
（选择一个）。
（选择全部）。
当 时的小表：
C(5,0)=1 C(5,1)=5 C(5,2)=10 C(5,3)=10 C(5,4)=5 C(5,5)=1
结语
组合出现在路径计数、二项式展开（系数）、概率与选择问题中。阶乘公式提供直接计算方法，而帕斯卡三角与递推关系则提供归纳直觉和高效构造数值的方式。格子行走示例是将“选择位置”等同于“选择步序”这一组合核心思想可视化的具体方法。
英文：Teaching Kids Programming – Introduction to Combinatorial Mathematics 1
本文一共 1176 个汉字, 你数一下对不对.上一篇: 性能的隐藏引擎: 一切都取决于数据存储的位置(缓存为王)
下一篇: CloudFlare宕机, 半个互联网崩了
