WIKI

基本概念

加法原理 与 乘法原理

排列

1. 不可重复排列数

$$ P^r_n=\frac{n!}{(n-r)!} $$

1. 可重复排列数
   $$ n^r $$

2. 圆排列
   $$ \frac {P^r_n} {r}=\frac{n!}{r(n-r)!} $$

组合
$$ C^r_n=\binom{n}{r}=\frac {P^r_n} {r!}=\frac{n!}{r!(n-r)!} $$
性质
$$ \begin{align} C^r_n&=C^{n-r}_n\\ C^r_n&=C^{r}_{n-1}+C_{n-1}^{r-1}\\ \sum\limits_{i=1}^nC^i_n&=2^n \end{align} $$
多重集的排列与组合

集合 $S$ 中的 元素 可以 相同, 称为 多重集

1. 无限多重集的排列 有$k$ 个不同的 元素 , $S$ 的 $r$ 排列为 $k^r$

2. 有限多重集的排列 $\frac{n!}{n_1!n_2!n_3!\dots n_k!}$

3. 无限组合 $S的r组合 的个数为C^r_{r+k-1}=\binom{r+k-1}{r}=C^{k-1}_{r+k-1}=\binom{r+k-1}{k-1 }$