第一章 组合数学基础
绪论
组合学问题求解的方法大致可以分为两类，一类是从组合学基本概念、基本原理出发解题的所谓常规法，例如，利用容斥原理、二项式定理、波利亚定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等。另一类方法则不同，它们通常与问题所涉及的组合学概念无关，而对多种问题均可使用，常用的有：
- 数学归纳法。
- 迭代法。
- 一一对应技术。这是组合数学理论常用的一个计数技巧。其原理就是建立两个事物之间的一一对应关系，把一个较复杂的组合计数问题 $\mathrm{A}$ 转化为另一个容易计数的问题 $\mathrm{B}$，从而利用 $\mathrm{B}$ 的计数运算达到对 $\mathrm{A}$ 的各种不同方案的计数。它的应用是多方面的，在组合学中最常见的是利用它将问题的模式转化为一种已经解决的问题模式
- 殊途同归方法。即从不同角度讨论计数问题，以建立组合等式，尤其在组合恒等式的证明中，故也称组合意义法。
- 数论方法。特别是利用整数的奇偶性、整除性等数论性质进行分析推理的方法。
两个基本法则
加法法则
如果完成一件事情有两个方案，而第一个方案有 $m$ 种方法，第二个方案有 $n$ 种方法可以实现，只要选择任何方案中的某一种方法，就可以完成这件事情，并且这些方法两两互不相同，则完成这件事情共有 $m+n$ 种方法。
若用集合语言，加法法则则可以描述为：设有限集合 $A$ 有 $m$ 个元素，$B$ 有 $n$ 个元素，且 $A$ 与 $B$ 不相交，则 $A$ 与 $B$ 的并共有 $m+n$ 个元素。
乘法法则
如果完成一件事情需要两个步骤，而第一步有 $m$ 种方法、第二步有 $n$ 种方法去实现，则完成该件事情共有 $m\cdot n$ 种方法。
若用集合语言，乘法法则则可以描述为：设有限集合 $A$ 有 $m$ 个元素，$B$ 有 $n$ 个元素，$a\in A,b\in B$，记 $(a,b)$ 为一有序对。所有有序对构成的集合称为 $A$ 和 $B$ 的积集（或笛卡尔乘积），记作 $A\times B$。那么，$A\times B$ 共有 $m\cdot n$ 个元素。
排列与组合
相异元素不允许重复的排列数和组合数
从 $n$ 个相异元素中不重复地取 $r$ 个元素的排列数和组合数分别为：
$$ \begin{align} P_n^r&=P(n,r)=n(n-1)\dots(n-r+1)=\dfrac{n!}{(n-r)!} \\\\ C_n^r&=C(n,r)=\binom{n}{r}=\dfrac{P_n^r}{r!}=\dfrac{n!}{(n-r)!r!} \end{align} $$
排列问题的模型是将 $r$ 个有区别的球放入 $n$ 个不同的盒子，每盒不超过 $1$ 个，则总的放法数为 $\mathrm{P}(n,r)$，同样，若球不加区别，则有 $\mathrm{C}(n,r)$ 种放法。
相异元素允许重复的排列
从 $n$ 个不同元素中允许重复地选 $r$ 个元素的排列，简称 $r$ 元重复排列。其排列的个数记为 $\mathrm{RP}(\infty,r)$。
本问题对应的模型是将 $r$ 个有区别的球放入 $n$ 个不同的盒子，每个盒子中的球数不加限制而且同盒的球部分次序。
显然，这样的排列数 $\mathrm{RP}(\infty,r)=n^r$。
从集合的角度，问题也可以描述为：设集合 $S=\{\infty\cdot e_1,\infty\cdot e_2,\dots,\infty\cdot e_n\}$，即 $S$ 中共含有 $n$ 类元素，每个元素有无穷多个，从 $S$ 中取 $r$ 个元素的排列数即为 $\mathrm{RP}(\infty,r)$。
不尽相异元素的排列
设 $S=\{n_1\cdot e_1,n_2\cdot e_2,\dots,n_t\cdot e_t\}$，即元素 $e_i$ 有 $n_i$ 个，且 $\sum\limits_{i=1}^t n_i=n$，从 $S$ 中任取 $r$ 个元素，求其排列数 $\mathrm{RP}(n,r)$。
本问题的数学模型是将 $r$ 个有区别的球放入 $t$ 个不同的盒子，而每个盒子的容量是有限的，其中第 $i$ 个盒子最多只能放入 $n_i$ 个球，求分配方案数。
此问题计算比较复杂，此处只给出几个特例。
(1) 当 $r=1$ 时，$\mathrm{RP}(n,1)=P_t^1=t$.
(2) 当 $r=n$ 时，此 $n$ 个元素的全排列数为
$$ \mathrm{RP}(n,n)=\dfrac{n!}{\prod\limits_{i=1}^tn_i!} $$
(3) 当 $t=2$ 时，
$$ RP(n,n)=\dfrac{n!}{n_1!n_2!}=\binom{n}{n_1} $$
相异元素不允许重复的圆排列
- 把 $n$ 个有标号的珠子排成一个圆圈，共有多少种不同的排法？ $$ \mathrm{CP}(n,n)=\dfrac{\mathrm{P}(n,n)}{n}=(n-1)! $$
- 从 $n$ 个相异元素中不重复地取 $r$ 个围成圆排列，求不同的排列总数 $\mathrm{CP}(n,r)$. $$ \mathrm{CP}(n,r)=\dfrac{\mathrm{P}(n,r)}{r}=\dfrac{n!}{r(n-r)!} $$
- 从 $n$ 个相异珠子中取 $r$ 个穿成一个项链，共有 $$ \dfrac{\mathrm{P}(n,r)}{2r}=\dfrac{n!}{2r(n-r)!} $$ 种不同的穿法。
相异元素允许重复的组合
设 $S=\{\infty\cdot e_1,\infty\cdot e_2,\dots,\infty\cdot e_n\}$，从 $S$ 中允许重复地取 $r$ 个元素构成组合，称为 $r$ 可重集合，其组合数记为 $\mathrm{RC}(\infty,r)$。
有
$$ \mathrm{RC}(\infty,r)=\mathrm{C}(n+r-1,r)=\dfrac{(n+r-1)!}{r!(n-1)!} $$
重复组合的模型是将 $r$ 个无区别的球放入 $n$ 个不同的盒子，每个盒子的球数不受限制。
不尽相异元素的组合
设 $S=\{n_1\cdot e_1,n_2\cdot e_2,\dots,n_t\cdot e_t\},\sum\limits_{i=1}^t n_i=n$，从 $S$ 中任取 $r$ 个，求其组合数 $\mathrm{RC}(n,r)$。
设多项式
$$ \prod_{i=1}^t\sum_{j=0}^{n_i}x^j=\prod_{i=1}^t(1+x+x^2+\dots+x^{n_i})=\sum_{r=0}^na_rx^r $$
则 $\mathrm{RC}(n,r)$ 就是多项式中 $x^r$ 的系数，即
$$ \mathrm{RC}(n,r)=a_r $$
