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

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

写给2020

设计笔记

Tokin

2020年12月8日 00:32

从毕业到现在，我认为我的转折点有两个，一个是16年选择去HF实习、在一家公司工作了近三年，另一个可能就是今年了，因为种种原因换了三份工作。

年初

从家里回HF，因为疫情在租的房子里远程办公，全栈开发非常累，也因为远程办公作息混乱，更因为疫情哪里也去不了，吃饭、买菜都非常不便，堆积在心里的压力无处排解，久而久之闷地自己的心态有了一些变化，人也变得丧了很多。然后开始想回家找一份轻松的工作，回去有熟悉的环境、熟悉的朋友、小而扁平的公司人际关系...终于在疫情解禁可以正常乘坐高铁时，我于4月低辞职了。

5月

因为家在小城市，工作机会挺少的，所以我周边城市也投了一些，最后面了几家后，选择了去JN的一家小公司做前端，工资相较在HF也没有降，前端技术栈是Vue、UniAPP，这些也都是我常用的技术栈，我也是从0开始构建起当时项目的移动端APP。

JN并不是我当时理想的工作城市，在这工作的两个月期间，我没有停下投简历的步伐，最后面试了几家后拿到2个Offer，遂毅然地辞职回家。

7月

因为另一家入职通知太迟了，最终我选择了CMTT的ZZ分公司，虽然是没有编制的三方合同工，但是工作稳定，公司依山傍水环境很好、有员工宿舍、有食堂、上班骑车5分钟、基本能保证17:30准时下班，薪资尚可。算半个YQ吧，因为没有营收压力，整个公司很佛系也很养老，丝毫没有以前呆过的公司对待项目的紧迫感，技术栈非常老旧、工作效率异常低下。

可能是因为疫情转好，也经常跟朋友出门玩乐，年初的抑郁心情开始拨雾渐明，渐渐地开始厌烦这种稳定又一眼看得到头的工作，开始担心在这里工作太久而缺乏竞争力，加之今年也25岁了，是我工作地第三年，如果程序员35岁是一个坎，我想真的应该慎重地规划自己未来10年了。

上海

这是我为自己规划未来的工作的城市，我精心地准备简历、笔试、面试，开始在招聘软件上投了一些公司，我把面试时间安排到了一个相近地时间，最后争取到了大概6家公司地面试机会时，我请了三天假假独自一人来到了上海面试，计划一天面2家，因为时间很赶，一边不想打乱自己地面试计划，一边又想尽可能多的面一些公司而多一些机会，所以面试期间也谨慎的投了几家公司。

每天早上早起准备今天的日程，看自己准备的笔试面试手册，因为成本原因，我住的比较偏，要赶公交、挤地铁，期间两天还下非常大的雨，我要尽可能安排好路线，饶是如此也会避免迟到而忘记吃午饭，一天面三家公司。最后多请了一天假，4天时间里面了9家公司，人都瘦了6斤，终于最后收到2个Offer。

一家是中小公司，一家是PA外包，都是前端，后来因为工资相差有点多，且刚来上海很缺钱，权衡后选择了PA外包，计划先工作一年左右在上海稳定下来后再考虑换工作。

于是从ZZ辞职，9月中旬来到上海入职了

12月，是我在上海工作第3个月了，工作环境很Nice，第一次接触敏捷开发，感觉效率很高，每个人都各司其职，任务粒度划分地非常精细，所以加班的情况很少见，也经常有大佬Review我的代码，我也收益颇丰，希望能够学到更多。

聊聊别的

很久没有更新博客了，语言组织能力进一步下降，晦涩又难通地语句拼合出整篇流水账文章，虽然没有华丽地辞藻，但还是想写点什么，写给2020最特别地一年，写给我下一个十年。

有时候莫名的压力超出自己地承受能力导致自己丧失上进心，失去目标，变得迷茫，好在经过近半年多调整，终于走出年初地低谷。我博客地副标题也从年初地“只是近黄昏”更新成了“无限进步”，希望自己能够保持学习，时刻上进，毕竟未来可期！

非常感谢你阅读到这里，砥砺、共勉！

遐说
咸九高速-幕阜山扶贫攻坚重点项目 2021年8月9日 09:38

咸九高速-幕阜山扶贫攻坚重点项目

遐说

Dorad

2021年8月9日 09:38

咸九高速，全称为咸宁（通山）至九江（武宁）高速公路。该项目起于县南林桥镇南林桥枢纽互通立交，接已建成的咸通高速公路和G56杭瑞高速公路通山段，经杨芳林乡、厦铺镇、闯王镇、九管会，止于九宫山二号隧道与通武高速公路江西段相接，路线全长约64.7公里。其咸宁段为46.7km，江西段约18km，项目总投资599034万元。该项目采用四车道高速公路建设标准建设，设计速度100公里/小时，路基宽度26米。全线设置南林桥互通、厦铺互通、九宫山互通等3处互通立交，估算总造价超百亿元，建设期为48个月。已于2021年1月开工建设，预计通车时间为2024年。

普通视图