第二章排列与组合

四个基本计数原理
- 加法原理
  
  将集合 $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{在一个部分中的对象数目} }$
集合的排列

$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)!}$
集合的组合（子集）

$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$ 元素集合的子集数量。
多重集合的排列

多重集合：元素可以出现多次，如一个有 $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!}$
多重集合的组合

通常将多重集合的子集成为组合而不是多重子集
- 定理 2.5.1
  
  设 $S$ 是有 $k$ 种不同对象的多重集合，每种元素均有无限重复数，那么 $S$ 的 $r$ 组合的个数等于
  ${r+k-1\choose r}={r+k-1\choose k-1}$
有限概率

有一个实验 $\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}$
于是很多概率问题可以用排列组合解决

附：中英词汇对照

中	英	中	英
划分	partition	部分	part
大小	size	补	complement
泛集	university set	多重集合	multiset
排列	permutation	组合	combination
子集	subset	多重子集	submultiset
等可能的	equally likely	随机的	randomly
事件	event	概率	probability

第二章 排列与组合

第二章排列与组合