排列与组合

官官方数学老师·13 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ 排列与组合数学排列与组合排列

计数原理排列组合

排列与组合

看图搞清排列组合的边界、计数模型与易错细节

按空格/→ 演示下一步

1 / 13 页

全部页面点击任意一页，跳回舞台从这页播放

计数原理排列组合

排列与组合

看图搞清排列组合的边界、计数模型与易错细节

1第 1 页 · 排列与组合

分步乘法计数原理

上一页我们认识了排列与组合的符号长相,但所有计数题往下追根,都先要会一件更底层的事:把一连串选择拆成几步相乘。

适用场景

完成一件事需依次走完 k 步,每步都有若干种独立选择时使用

计数公式

若各步选法数分别为 n₁,n₂,…,nₖ,则总方案数 = n₁·n₂·…·nₖ

分步 vs 分类

连续选择走乘法(分步),互斥分支走加法(分类);二者不可混用

三条边界

①各步顺序固定 ②各步互不依赖 ③后一步选法不被前一步改变

A 到 D 的多段公路行程对应 →分步乘法计数

A→B 有 n₁ 条、B→C 有 n₂ 条、C→D 有 n₃ 条,全程路径数 = 三段路数相乘

N = n_1 \times n_2 \times \cdots \times n_k

2第 2 页 · 分步乘法计数原理

分类加法计数原理

上一页用分步乘法解决了「先选火车、再选出租车」这类需要分阶段决策的问题。现在换个场景：地铁直达、公交转一次、打车直达——三条互不重叠的路线，挑一条就走完。怎么数？

互斥分类

把完成方式按「不重不漏」的标准分成若干类，类与类之间互斥

分类计数

分别数出每一类内部有多少种具体方案

求和得总数

把各类方案数相加，总数等于各类方案数之和

加法边界

事件只选一种方案就能完成时用加法；需连续决策时用乘法

回家的几条互不重合路线对应 →分类加法计数原理

「回家路线」对应一个类，类内的方案数相加；前提是路线之间不互通（类与类互斥）

|A \cup B| = |A| + |B| - |A \cap B|;\ A \cap B = \varnothing \Rightarrow |A \cup B| = |A| + |B|

3第 3 页 · 分类加法计数原理

排列

分步乘法告诉我们「一步一个选择」。当结果靠顺序区分——比如冠军、亚军、季军各有名次——就是排列要研究的问题。

定义

从n个不同元素中取m个（m≤n），按一定顺序排成一列

顺序是关键

同样的元素，顺序不同就是不同的排列

计数公式

P(n,m) = n×(n-1)×…×(n-m+1)，即 n!/(n-m)!

全排列

m=n时所有元素都参与排列，P(n,n)=n!

与组合的边界

排列看顺序，组合只看「选谁」，不关心顺序

运动会颁奖台对应 →排列

同样三人，金银铜的名次互换就是不同的颁奖结果

P(n,m) = \dfrac{n!}{(n-m)!}

4第 4 页 · 排列

排列数

上一页说了「排列」是什么：从 n 个不同元素里取 k 个，按顺序排成一列。但光是描述还不够——到底有多少种排法？这就要请出「排列数」。

符号约定

记作 A_n^k（或 P_n^k），n 是元素总数，k 是取出个数

计算公式

A_n^k = n(n-1)(n-2)…(n-k+1) = n!/(n-k)!

推导依据

分步乘法：第 1 位 n 选，第 2 位 n-1 选……第 k 位 n-k+1 选

边界约定

k > n 时 A_n^k = 0；k = 0 或 k = n 时分别为 1 和 n!

典型应用

排名次、选座位、排赛程——只要「位置不同结果不同」就用它

颁奖台金银铜牌对应 →排列数 A_n^k

8 人争 3 块奖牌，谁站中央、谁站两侧，位置不同名次就不同

A_n^k = n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!}

5第 5 页 · 排列数

全排列

前面学的排列数 A(n,k) 是从 n 个里选 k 个排起来。当 k 推到上限 n——元素一个不剩全部用上——就到了全排列。这是组合数学里最朴素、也最锋利的一把刀。

全部参与

n 个不同元素无一遗漏，全部出现在排列里，位置恰好填满

顺序敏感

任意两个位置上的元素交换，就得到一个不同的全排列

计数公式

全排列数 = n!，首位 n 种、次位 n-1 种……一路乘到 1

排列数的特例

全排列数 = A(n,n)，是 k 取到上限时排列数的边界情形

复杂度与应用

n! 增长极快——暴力遍历只在小规模可行；密码穷举、TSP 是经典场景

全班同学拍合影排队对应 →全排列

每个同学都得在，队形不同就是不同的排列

P(n,n) = n! = n \times (n-1) \times \cdots \times 2 \times 1 = A_n^n

6第 6 页 · 全排列

阶乘

上页全排列 P(n,n) 算出的连乘 n·(n-1)·…·1 出现得太频繁，被数学家起了个专名——阶乘。今天聊聊它的来龙去脉和延展。

递归定义

n! = n·(n-1)!, 0! = 1; 把逐个安放翻译成递推

全排列的记号

n! 本质就是 P(n,n)，表示 n 个元素排满一列的方法数

0! = 1 的约定

让递推 n!=n·(n-1)! 在 n=1 处不破, 也对应空集唯一排法

延拓到 Gamma 函数

Γ(n+1)=n!, 把阶乘定义域从自然数扩到实数与复数

极快的增长速度

Stirling 公式 n!≈√(2πn)(n/e)ⁿ, 比任何指数级更猛

n 个人排队拍照对应 →阶乘

每换一次站位就是一张新合影, 所有可能的照片数就是 n!

n!=\prod_{k=1}^{n}k,\quad 0!=1,\quad \Gamma(n+1)=n!

7第 7 页 · 阶乘

组合

上页学了排列——5人排队领奖,顺序变了就是不同结果。现实中更多问题只问'选哪几个':5人做项目小组,谁先加入无关紧要,名单定下来就够了。组合正是处理这类'顺序无关'的选取。

顺序无关

选出k个元素成一组,组内谁先谁后不影响结果本身

组合的定义

从n个不同元素中任取k个成一组,记作C(n,k)或C_n^k

组合数公式

C(n,k)=n!/[k!(n-k)!],等价于A(n,k)除以k!

关键性质

对称性 C(n,k)=C(n,n-k);归一 C(n,0)=C(n,n)=1

判别准则

问'选哪几个'用组合;问'排第几/名次'用排列

从菜单点3道菜对应 →组合 C(n,k)

只关心点了哪3道,不关心第几道先上桌

\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{A_n^k}{k!}

8第 8 页 · 组合

组合数

上一页我们讲了「组合」——从n个里选k个，不计顺序。但到底有多少种选法？这就需要「组合数」来精确计数。

组合数公式

C(n,k) = n!/(k!(n-k)!)，本质是先按排列算再除以k!消序

对称性

C(n,k) = C(n,n-k)，选k个等价于弃n-k个

边界值

C(n,0)=C(n,n)=1，不取或全取都只有一种

帕斯卡恒等式

C(n,k)=C(n-1,k-1)+C(n-1,k)，是递推与杨辉三角的根基

典型应用

二项式定理系数、古典概型、超几何分布都建立在它之上

彩票摇号顺序对应 →组合数

6个中奖号码无论以何种顺序摇出都对应同一组；A(n,k)/k!就是把k!种内部排列折成一种选法

C_n^k = \frac{n!}{k!(n-k)!} = \frac{A_n^k}{k!}

9第 9 页 · 组合数

组合数性质1

上一节我们用定义式 C(n,k)=n!/[k!(n−k)!] 来算组合数。今天看第一条隐藏规律：选 k 个和选 n−k 个，方案数竟然相等——这就是对称性。

对称公式

C(n,k) = C(n, n−k)，选 k 个与选 n−k 个的方案数相等

组合直觉

从 n 个里「挑出 k 个」与「挑出 n−k 个」是同一件事的两种看法

对称轴

k = n/2 时居于对称轴附近，对应组合数取到最大值的位置

定义验证

在公式 n!/(k!(n−k)!) 中把 k! 与 (n−k)! 调换位置，分母不变

选 5 人参赛 vs 不参赛对应 →C(n,k)=C(n,n−k)

选 5 个人参赛 ≡ 选 n−5 个人不参加，本质是同一次划分

C_n^k = C_n^{n-k} = \dfrac{n!}{k!\,(n-k)!}

10第 10 页 · 组合数性质1

组合数性质2

性质1告诉我们 C(n,k)=C(n,n-k)，那是同一行里的对称。组合数还有一条更'跨行'的恒等式——把两个相邻组合数加起来，居然等于下一行的某个组合数。

杨辉恒等式

C(n,k)+C(n,k-1)=C(n+1,k)，三个不同 n 之间的桥梁

分类证明

从 n+1 人选 k 人，按是否含甲分成两组相加

杨辉三角

每行中间项由肩上两项相加得到

典型应用

化简含 C 的求和、推导二项式系数递推

选队员分组对应 →杨辉恒等式两边

甲在不在队里把人分成两条路，两路人数之和就是从更多人里选

C(n,k) + C(n,k-1) = C(n+1, k)

11第 11 页 · 组合数性质2

本节要点

✓分步用乘、分类用加——两条原理贯穿始终
✓排列讲顺序，组合讲选取
✓组合数是排列数除以 k! 的去序结果
✓对称性与递推式是组合数计算的两条捷径
✓易错：先选后排要乘回顺序，注意区分

延伸主题：二项式定理排列组合综合应用容斥原理

12第 12 页 · 本节要点

课后思考

先合上笔记自己想想，再点开参考答案对照思路。

1组合数公式 C(n,k)=n!/[k!(n-k)!] 里，分母两个阶乘各在"除掉"什么重复计数？

参考答案(n-k)! 把 n! 缩成 P(n,k)，只保留前 k 位的排列；k! 合并 k 个被选元素的内部顺序，于是从排列退回组合。

230 人中选 3 人组队，要求甲、乙恰好一人入选。用分类加法与分步乘法分别求方案数。

参考答案分类加法：C(28,2)+C(28,2)。分步乘法：C(2,1)×C(28,2)。两种思路都得到 2×378=756，殊途同归。

3若允许重复（如从 {A,B,C} 中可重选 3 个字母），原排列数公式 P(n,k) 还成立吗？如何修正？

参考答案不再成立，n<k 时分母即失效。可重排列改用 n^k=27，可重组合改用 C(n+k-1,k)。本质：从阶乘结构转为幂与组合恒等式。

13第 13 页 · 课后思考