阅读 桌面完整版

组合简介（组合数学入门）

视频：油管/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 

这些项满足递推关系

然后，我们可以很容易的写出至顶向下的动态规划算法实现（用@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

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版