第二章 排列与组合

1. 四个基本计数原理

   • 加法原理

     将集合 $S$ 划分为两两不相交的集合 $S_1,S_2,\cdots,S_m$，则 $S$ 的对象数目可以通过确定它的每一个部分的数量并如此相加而得到：
     $$
     \vert S\vert=\vert S_1\vert+\vert S_2\vert+\cdots+\vert S_m\vert
     $$

   • 乘法原理

     令 $S$ 是对象的有序对 $(a,b)$ 的集合，第一个对象 $a$ 来自大小为 $p$ 的一个集合，而对于 $a$ 的每一个选择，对象 $b$ 有 $q$ 种选择，于是，$S$ 的大小为 $p\times q$：
     $$
     \vert S\vert=p\times q
     $$

   • 减法原理

     令 $A$ 是一个集合，而 $U$ 是包含 $A$ 的更大的集合，设
     $$
     \overline{A}=U\setminus A={x\in U:x\notin A}
     $$
     是 $A$ 在 $U$ 中的补。那么 $A$ 中的对象数目 $\vert A\vert$ 由下列法则给出：
     $$
     \vert A\vert=\vert U\vert-\vert\overline{A}\vert
     $$

   • 乘法原理

     令 $S$ 是一个有限集合，把它划分成 $k$ 个部分使得每一部分包含的对象数目相同，于是，此划分中的部分由下述公式给出：
     $$
     k=\dfrac{\vert S\vert}{\text{在一个部分中的对象数目} }
     $$

2. 集合的排列

   $r$ 是正整数，令一个 $n$ 元素集合的 $r$ 排列表示 $n$ 个元素中的 $r$ 个元素的有序放置,用 $P(n,r)$ 表示 $n$ 个元素集合的 $r$ 排列的数目。

   • 定理 2.2.1

     对于正整数 $n$ 和 $r$，$t\le n$，有：
     $$
     P(n,r)=n\times(n-1)\times\cdots\times(n-r+1)=\dfrac{n!}{(n-r)!}
     $$

   • 定理 2.2.2

     $n$ 个元素的循环 $r$ 排列的数目是
     $$
     \dfrac{P(n,r)}{r}=\dfrac{n!}{r\cdot (n-r)!}
     $$

3. 集合的组合（子集）

   $r$ 是非负整数，令一个 $n$ 元素集合 $S$ 的 $r$ 子集表示由 $S$ 的 $n$ 个对象中的 $r$ 个对象组成的子集。用 $n\choose r$ 表示 $n$ 元素集合的 $r$ 子集的数目。

   对每一个非负整数 $n$，下述事实成立：
   $$
   {n\choose 0}=1,\ {n\choose 1}=n,\ {n\choose n}=1,\ {0\choose 0}=1
   $$

   • 定理 2.3.1

     对于 $0\le r\le n$，有
     $$
     P(n,r)=r!{n\choose r}
     $$
     因此
     $$
     {n\choose r}=\dfrac{n!}{r!(n-r)!}
     $$

   • 定理 2.3.2

     对于 $0\le r\le n$，有
     $$
     {n\choose r}={n\choose n-r}
     $$

   • 定理 2.3.3（帕斯卡公式）

     对于所有满足 $1\le k\le n-1$ 的整数 $n$ 和 $k$，有
     $$
     {n\choose k}={n-1\choose k}+{n-1\choose k-1}
     $$

   • 定理 2.3.4

     对于 $n\ge0$，有
     $$
     {n\choose 0}+{n\choose 1}+\cdots+{n\choose n}=2^n
     $$
     且这个共同值等于 $n$ 元素集合的子集数量。

4. 多重集合的排列

   多重集合：元素可以出现多次，如一个有 $3$ 个 $a$，$2$ 个 $b$，无穷多个 $c$ 的多重集合 $M$ 记为 $M={3\cdot a,2\cdot b,\infty\cdot c}$

   • 定理 2.4.1

     设 $S$ 是有 $k$ 种不同类型元素的多重集合，每一个元素有无限重复数，$S$ 的 $r$ 排列数是 $k^r$

   • 定理 2.4.2

     设 $S$ 是有 $k$ 种不同类型元素的多重集合，每一种类型的有限重复数是 $n_1,n_2,\cdots,n_k$。设 $S$ 的大小为 $n=n_1+n_2+\cdots+n_k$。则 $S$ 的排列数目等于
     $$
     \dfrac{n!}{n_1!n_2!\cdots n_k!}
     $$

   • 定理 2.4.3

     设 $n$ 是正整数，$n_1,n_2,\cdots,n_k$ 是正整数且 $n=n_1+n_2+\cdots+n_k$。把 $n$ 对象集合划分为 $k$ 个有标签的盒子，第 $i$ 个盒子有 $n_i$ 个对象，这时的划分方法数等于
     $$
     \dfrac{n!}{n_1!n_2!\cdots n_k!}
     $$
     若盒子没有标签，且 $n_1=n_2=\cdots=n_k$，则划分数等于
     $$
     \dfrac{n!}{k!n_1!n_2!\cdots n_k!}
     $$

5. 多重集合的组合

   通常将多重集合的子集成为组合而不是多重子集

   • 定理 2.5.1

     设 $S$ 是有 $k$ 种不同对象的多重集合，每种元素均有无限重复数，那么 $S$ 的 $r$ 组合的个数等于
     $$
     {r+k-1\choose r}={r+k-1\choose k-1}
     $$

6. 有限概率

   有一个实验 $\varepsilon$，在进行这个实验时，它产生的结果是某有限集合中的一个，假设每一个结果是等可能的，则称这个实验是随机的，所有可能的结果成为这个实验的样本空间，并把它记作 $S$，$S$ 是一个有限集合，如下面这个集合
   $$
   S={S_1,s_2,\cdots,s_n}
   $$
   当我们进行实验 $\varepsilon$ 时，每个 $s_i$ 都有 $1/n$ 的出现机会，所以说结果的概率是 $1/n$，写作
   $$
   Prob(s_i)=1/n
   $$
   一个事件就是样本空间 $S$ 的一个子集 $E$

   在样本空间为 $S$ 的实验中，事件 $E$ 的概率定义为 $S$ 中属于 $E$ 的结果的比率，因此
   $$
   Prob(E)=\dfrac{\vert E\vert}{\vert S\vert}
   $$
   于是很多概率问题可以用排列组合解决

附：中英词汇对照