第一章——组合分析

1. 很多概率论中的问题只要通过计算某个事件发生的结果的数目就能解决，关于计数的数学理论就是组合分析（Combinatorial Analysis）。

2. 计数的基本法则：假设一共有r个实验，实验i有 $n_i$ 个结果，那么这r个实验一共有 $n_1n_2...n_r$ 个结果。

3. 对于n个元素，如果其中的 $n_1$ 个元素彼此相同，另 $n_2$ 个彼此相同，...， $n_r$ 个也彼此相同，那么总共就有 $\frac{n!}{n_1!n_2!...n_r!}$ 种不同的排列（Permutation）方式。

例：用6个字母PEPPER进行排列，一共有多少种不同的排列方式。——答案：60种

4. 可能组合数 $\tbinom{n}{r}$ 的定义是： $\frac{n!}{(n-r)!r!}$

5. 组合恒等式： $\tbinom{n}{r}=\tbinom{n-1}{r-1}+\tbinom{n-1}{r}$

理解：从n个元素中取出r个元素，相当于从n个元素中取出一个出来作为独立的一个组，从n-1个元素那一组中取出r-1个元素，同时取出独立组中的一个元素；再从n-1个元素中取出r个元素。

6. 值 $\tbinom{n}{r}$ 经常被称为二项式系数（Binomial Coefficient）,是因为它是下面二项式定理的重要系数： $(x+y)^n=\sum_{k=0}^n \tbinom{n}{k}x^k y^{n-k}$

7. 多项式定理： $(x_1+x_2+...+x_r)^n=\sum_{(n_1,n_2,...n_r): \newline n_1+...+n_r=n}\tbinom{n}{n_1,n_2,...,n_r}x_1^{n_1}x_2^{n_2}...x_r^{n_r}$ ，其中 $\tbinom{n}{n_1,n_2,...,n_r}$ 称为多项式系数（Multinomial Coefficient）

8. 如果 $n_1+...+n_r=n$ ，则定义 $\tbinom{n}{n_1,n_2,...,n_r}$ 为 $\tbinom{n}{n_1, n_2, ..., n_r}=\frac{n!}{n_1!n_2!...n_r!}$ 表示把n个不同的元素分成大小不同的r个不同组的组合数。