组合数学: 简介一(帕斯卡三角/二项式系数)

2025年11月16日 04:44

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

格子行走示例 — 从左下到右上路径

想象你只能向右（R）或向上（U）移动。要从左下走到需要三次向右和两次向上的点，每一条最短路径都是由五步组成的序列，其中包含三个 R 和两个 U。 [caption id="attachment_70414" align="alignnone" width="512"]

走格子: 排列组合[/caption] 每条有效路径只是从五个位置中选择两个放 U（其余为 R）。所以这样的路径数就是“从 5 中选 2”，记作 [math]C(5,2)[/math]（等于 [math]C(5,3)[/math]）。示例序列：

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

二项式系数（组合）表示法

从 [math]n[/math] 个项目中选出 [math]m[/math] 个（顺序不重要）的方式数记为 [math]C(n,m)[/math] 或 [math]\binom{n}{m}[/math] 两者都表示“从 n 中选 m”。

组合公式 — 基于阶乘的推导

先计算有序选择（排列）：从 n 个不同项目中取出长度为 [math]m[/math] 的有序列表的数量为 [math] n\times(n-1)\times\cdots\times(n-m+1)=\dfrac{n!}{(n-m)!} [/math] 每一个无序的 [math] m [/math] 项集合对应 [math] m! [/math] 个有序列表（即这 m 项的排列）。除以 [math] m! [/math] 得到组合数： [math]C(n,m)=\dfrac{n!}{m!(n-m)!}.[/math]

把公式应用到格子示例

对于总步数 [math]n=5[/math] 和向上步数 [math]m=2[/math]： [math]C(5,2)=\dfrac{5!}{2!,3!}=\dfrac{120}{2\times 6}=10 [/math] 因此共有 10 条不同的最短路径。

为什么这个公式直观上合理

视角一 — 选择位置：从 [math]n[/math] 个位置中选择放置 U 的 [math]m[/math] 个位置；这就是 [math]C(n,m)[/math]。
视角二 — 用排列除以顺序：先计算 n 步的所有排列，然后除去相同步序的重排（比如相同类型步的交换）。

帕斯卡三角与递推关系

把 [math]C(n,k)[/math] 写成行可以形成帕斯卡三角：

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

[caption id="attachment_70413" align="alignnone" width="847"]

Pascal/帕斯卡三角形[/caption] 这些项满足递推关系 [math] C(n,m)=C(n-1,m-1)+C(n-1,m) [/math] 然后，我们可以很容易的写出至顶向下的动态规划算法实现（用@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)
可以方便扩展计算整行或整列组合数

组合证明 — 采苹果

想要从 [math]n[/math] 个苹果中选 [math]m[/math] 个。考虑最后一个苹果（编号为 n）：如果你选了它，那就必须从前面的 [math]n-1[/math] 个中选剩下的 [math]m-1[/math] 个：有 [math]C(n-1,m-1)[/math] 种方法。如果你不选它，那就必须从前面的 [math]n-1[/math] 个中选出全部 [math]m[/math] 个：有 [math]C(n-1,m) [/math] 种方法。这两个互不相交的情况覆盖了所有可能，因此 [math] C(n,m)=C(n-1,m-1)+C(n-1,m) [/math] （该恒等式正是构造帕斯卡三角的规则。）

递推关系的格子解释

在格子上，观察到达某点的任意路径的最后一步：要么是 R，要么是 U。以 R 结尾的路径来自某个前一点，以 U 结尾的路径来自另一个前一点。把这两组路径分别计数并相加就得到相同的加法规则。

常见的小值与说明

[math]C(n,0)=1[/math]（选择零个）。 [math]C(n,1)=n[/math]（选择一个）。 [math]C(n,n)=1[/math]（选择全部）。当 [math]n=5[/math] 时的小表：

 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

英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
智能手机 HTC One M9 使用测评虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
按揭贷款(房贷,车贷) 每月还贷计算器去年给银行借了17万英镑买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定是比较常用的. 简单来说就是每个月交的钱是...
第一次私校家长会: 原来家长比孩子还卷前几天参加了娃的第一次家长会，和几位家长聊下来，真是个个都很厉害。不光孩子们卷，家长也一样卷，一眼望去基本都是 Dr/博士。娃还调侃我一句：“这有什么的，你不也是 Dr 吗？” 我心里默默想：还好没写学校名字，不然我这野鸡大学的头衔真拿不出手 😂。私校里真是人才济济，乐器过 8 级的太常见了，卷得不得了。我还问过娃，是想当 big fish in a small pond...
拔牙后的注意事项(图, 慎入) Care of Mouth after Extraction 昨天又拔了两颗牙, 初步定在5月4号装牙套. 这是牙医诊所给的术后注意事项: 拔完后需要等3-4小时麻醉失效后才能吃喝. 稍微流点血是很正常的. 但是请不要漱口吐出, 因为这会加速流血. 你只要轻轻的含着口水并咽下即可. 如果一直流血, 请拿着纱布(并不是纸巾)放在拔牙处20分钟. 24小时内请不要运动, 术后几小时内回家静静坐着. 12小时内不要吸烟, 喝酒或者喝热饮, 因为这会让伤口流血....
WP中检查白名单的用户是否登陆? WordPress 提供了一个方法 is_user_logged_in() 用于检查用户是否是登陆状态. 但是很可惜这个方法在 pluggable.php 中定义. 也就是说如果你需要在插件中使用, 那么这个函数是没有被定义的. 我们来看一下 is_user_logged_in() 的实现: function is_user_logged_in()...
北爱尔兰的黑暗树篱 Dark Hedges 是摄影的取景之地老实说, 去北爱尔兰当天我才了解到黑暗树篱这个地方(Dark Hedges), 因为都是媳妇做的功课, 日程安排上了, 我当上司机, 然后被普及了知识. 北爱尔兰的黑暗树篱是我们访问北爱尔兰的第一站, 从机场开车过去大概50分钟(黑暗树篱在机场的北面40英里左右). 黑暗树篱 Dark Hedges地址: Bregagh Rd, Stranocum,...
比特币最近波动有点大: 一天牛市一天熊比特币10万美金以内都是最后上车的机会！比特币近期的价格波动可以归因于多个关键因素，包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道，特朗普再次当选，他可能会推动减少美国对乌克兰的支持，这可能会影响全球金融市场和风险偏好。同时，特朗普正在将自己塑造为亲加密货币的候选人，表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测，导致市场情绪在乐观和不确定性之间波动。特朗普对俄乌战争的态度美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任（第二次），那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测，而是正在实际塑造市场的关键力量。特朗普（Donald Trump）减少美国对乌克兰的支持，全球投资者可能会预期地缘政治稳定性发生变化，从而增加对比特币作为避险资产的需求。同时，他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策，例如明确的合规指南或减少监管审查，可能会吸引更多机构投资者进入市场，并促进更广泛的加密货币采用。然而，政策的快速变化也可能导致短期市场剧烈波动，因为市场需要时间来消化新的政策动向。朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道，Bybit交易所（全球第二）这些被盗的ETH已经被清洗，此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心，还可能引发更严格的监管审查，导致短期市场动荡。此外，被盗资金的大规模流动和出售可能对市场流动性造成冲击，进一步加大价格波动。随着这些事件的持续发酵，比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。与此同时，与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗，人们对加密行业安全漏洞的担忧持续存在，同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起，共同导致了比特币近期的剧烈价格波动。...

普通视图