组合数学（2）基础知识
pid：15457033
本章是一些基础知识和常用思想的简单罗列和举例，熟悉的同学可以跳过。
一.常用思想
- 正难则反——求解问题的补集
- 分而治之——将问题进行划分
- double counting——数两次
- 一一对应——双射是个好东西
- 递推关系——先考虑变化过程而不是结果
- 容斥原理和鸽巢原理
二.加法法则和乘法法则
1.加法法则
若具有性质A的集合大小为m，具有性质B的集合大小为n，则具有性质A或性质B的集合的大小为m+n
2.乘法法则
若具有性质A的集合大小为m，具有性质B的集合大小为n，则具有性质A及性质B的集合的大小为mn
例：某BASIC语言的限制标识符最多由三个字符组成，要求第一个字符必须是26个英文字母中的一个，第二三个字符可以是英语字母，也可以是0.1…9的阿拉伯数字，求标识符的数目。
解：一个字符的标识符共26个
两个字符的标识符，第一个字符有26种选择，第二个有36种选择，由乘法原则，共26*36=936个
三个字符的标识符，第一个字符有26种选择，第二个有36种选择，第三个有36种选择，由乘法原则，共26*36*36=33696个
由加法原则，标识符的数目总计为
N=26+936+33696=34658 个
ps.虽然这两个法则看起来很像废话，不过却很实用。
三.排列和组合
1.组合
从n个元素中任取r个元素一组，若不考虑它们的顺序，则称为从n中取r的组合，记为 C_n^r=frac{n!}{(n-r)!cdot r!}
2.排列
从n个元素中任取r个元素一组，若考虑它们的顺序，则称为从n中取r的排列，记为 A^r_n=frac{n!}{(n-r)!}
3.总结
事实上，大部分的排列组合问题都可以归结于将取n个球放在m个盒子里的方案数的问题，根据球是否相同，盒子是否相同，盒子是否非空或只能放一个或无限制，可以分解为几类问题。事实上，将球看成原像集，盒子看成像集，放球的过程看成一个映射，其实问题就归结于原像集和像集中的元素是否有差别，以及这个映射是否是满射或单射。下面对这几个问题进行总结。顺便一提，这玩意叫十二重计数法。
- 乘法原则，答案为 m^n
- 每个球可以从剩下未被选择的盒子里选，答案为 prod_{i=0}^{n-1}(m-i)
- 设 A_i 表示第i个盒子为空，则答案为 left| bar{A_1}cap bar{A_2} cap cdotcdotcdot cap bar{A_n}right| ，由容斥原理，答案等于 sum_{i=0}^{m}{(-1)^i C_m^i (m-i)^n}
- 把空盒全部扔掉即为6的情况，因此枚举空盒数量求和即可， sum_{i=0}^{m}{S_2(n,m-i)} ，注意到这个这个展开以后是一个卷积的形式，所以可以用NTT优化卷积，也可以大力推一波式子，发现可以通过前缀和优化到O（n）的复杂度求出，当然这里只是前OIer顺便提一嘴，搞数学不用太关心这个，再顺便提一嘴，当 m geq n 时，这玩意是贝尔数
- 因为盒子全部相同，每个盒子又至多放一个，因此当 n>m ,答案为0，否则为1，写成示性函数的样子为 left[ nleq m right]
- 6和3的区别在于盒子有无区别，因此6在3的基础上不考虑盒子顺序，除一个 m！ 即可，答案为 S_2(n,m)=frac{sum_{i=0}^{m}{(-1)^i C_m^i (m-i)^n}}{m!} ,这也为第二类stirling数的定义
- 7可以看做在每个盒子事先放一个球，然后就是9的情况，答案为 C_{m+n-1}^{m-1}
- 从 m 个盒子里面选出 n 个来装球，答案为 C^n_m
- n 个球 n-1 个空隙，从中选 m-1 个即可，答案为 C_{n-1}^{m-1}
- 会在之后的文章里补上生成函数和Ferrers图的内容，这里就丢一个转移的式子，设 fleft[ i right]left[ j right] 表示 j 个数和为 i 的方案数，则根据第一个数是否为1，则有 fleft[ i right]left[ j right]=fleft[ i-1 right]left[ j-1 right]+fleft[ i-j right]left[ j right]
- 同5，答案为 left[ nleq m right]
- 先往所有盒子里丢一个球，然后变成了10
到此我们圆满解决了球和模型的所有问题，值得鼓掌！！虽然留了一些坑，鸽巢原理、容斥原理、生成函数什么的，但是会在之后的文章里补上的，毕竟开学时间被推迟了，这个假期应该还是比较有空的。
下面说点认真的，组合数学是一门和诸多数学分支都有交叉的学科，因此对一些其他分支的知识也应该有所了解，下面大概列一下，仅供参考。
- 基础数学：集合和函数、整数、阶乘、模运算、等价关系和序关系
- 线性代数：向量空间、子空间、线性变换、矩阵、特征值理论
- 抽象代数：主要是群论，还有一些域论，环论比较少
- 数论：基础数论知识和著名定理、二次剩余、二平方和四平方和定理
- 数学分析：极限、求导、泰勒展开、级数（生成函数部分会大量涉及）
- 拓扑：拓扑空间和度量空间基本定义、Jordan曲线定理
- 还有一些些概率论和集合论的基础东西，特别是概率论，其实在组合数学中的运用非常广泛
下一篇