组合数学 - 从入门到入土

ToastBread · 2025-02-05 09:55:03 · 学习·文化课

1 排列与组合

下文中无特殊说明外，均假设所有性质不相关。

1.1 加法原理与乘法原理

• 加法法则：具备性质 A,B 的事件分别有 m,n 个，则具有性质 A 或 B 的有 m+n 个。

应用举例：（截止于 2025/2/5）洛谷主题库中的入门题目有 389 题，普及-有 969 题，那么主题库中难度是入门或普及-的题目共有 389+969=1358 题。

• 乘法法则：具备性质 A,B 的事件分别有 m,n 个，则同时具有性质 A 与 B 的有 mn 个。

应用举例：

从 XaoWa118,one_of_the_person,HeYuChenC 中选取一人去做 P1001,P1002,P2482 中的任意一道题目共有 3\times3=9 种选法。

1.2 一一对应

• 一一对应：假设性质 A 和性质 B 一一对应，那么对性质 A 的计数可以转化为对性质 B 的计数。

应用举例：

假设 n 个人打单打赛，求至少举行几次比赛才能决出冠军。

考虑单打赛的同义词：每次淘汰一人。利用一一对应，我们就知道至少要举行 n-1 轮比赛，才能决出冠军。

1.3 排列组合

排列组合的记号有很多种，本文选取 \dbinom{n}{m} 和 \mathrm{A}^m_n 表示。

• 排列：把 n 个互不相同的元素选 m 个出来，关注顺序，叫排列。总共的方案数是 n(n-1)(n-2)\cdots(n-m+1)=\dfrac{n!}{(n-m)!}=m!\dbinom{n}{m}=\mathrm{A}^m_n。

应用举例：

在可乐，雪碧，芬达中选取两种饮料先后排队结账，共有 3\times2=6 种方案。

• 组合：把 n 个互不相同的元素选 m 个出来，不论顺序，叫组合。总共的方案数是 \dfrac{n(n-1)(n-2)\cdots(n-m+1)}{m!}=\dfrac{n!}{m!(n-m)!}=\dfrac{\mathrm{A}^m_n}{m!}=\dbinom{n}{m}。

应用举例：

在机房的 5 个人中选取 3 个人一起下楼锻炼，共有 \dfrac{5\times4\times3}{3\times2\times1}=10 种选法。

之间的关系：排列在乎顺序，组合不论顺序。 m 个元素不同的排列方式有 m! 种，所以排列是组合的 m! 倍。

1.4 允许重复和不相邻的组合

• 允许重复的组合：把 n 个互不相同的元素选 m 个出来，不论顺序，允许重复，叫允许重复的组合。总共的方案数是 \dbinom{n+m-1}{m}。

理解：

假设原来的物品为 a_1,a_2,\cdots,a_n，新的物品堆为 b_1,b_2,\cdots,b_n+m-1。对 b 做不允许重复的组合，记 b 选出的组合为 c_1,c_2,\cdots,c_m。那么就表示选取了 a_{c_1},a_{c_2-1},a{c_3-2}\cdots,a_{c_m-(m-1)}。

应用举例：

在可乐，雪碧，芬达中选取两瓶饮料，允许重复，一起不分顺序结账，共有 \dbinom{3+2-1}{2}=\dbinom{4}{2}=6 种方案。

• 不相邻的集合：把 n 个互不相同的元素选 m 个出来，不论顺序，禁止相邻，叫不相邻的集合。总共的方案数是 \dbinom{n-m+1}{m}。

理解与上文类似，不再重复。

应用举例：

在机房的 5 个人中选取 2 个人一起下楼锻炼，但为了防止机惨，要求禁止相邻两人一起下楼。共有 \dbinom{5-2+1}{2}=\dbinom{4}{2}=6 种选法。

1.5 二项式推论

1.6 Lucas 定理

1.7 斯特林（Stirling）数

1.8 小球模型