组合数学基础

1）加法原理

$n$种方法，每种有$n_i$种完成方式，则总完成方式数为 $$\sum_{i=1}^{n}n_i$$

2）乘法原理

$n$个步骤，每步有$n_i$种完成方式，则总完成方式数为 $$\prod_{i=1}^nn_i$$

3）排列与组合

$n$个不同的数中取$m$个数排称一列，则总方法数为 $$A_n^m=\frac{n!}{(n-m)!}$$ 称为排列数。 不考虑顺序，则总方法数为 $$C_n^m=\frac{n!}{m!(n-m)!}$$ 被称为组合数。组合数又记为$\binom{n}{m}$。（注意上下） 特殊情况，若$n>m$，则$A_n^m=C_n^m=0$。 全排列。$A_n^n=n!$ 圆排列。我们不是将数排成一列，而是将其排于圆上，这样可以旋转等价。 $m$个数中，同一个圆排列被计算$m$次。故圆排列数为 $$A_n^m/m$$ 捆绑法。相邻元素绑在一起。 7个人排列，其中A和B必须相邻，C和D必须相邻，求总排列方法。 将A和B看成一个人AB，C和D看成一个人CD，则总方案数为 $$(7-2)!\times 4=480$$ 乘4是因为AB、CD可以交换位置。 可重排列。有$a_1$个1，$a_2$个2，…… 共$m$个元素。则排列数为 $$\frac{m!}{\prod a_i!}$$ 错排问题。$n$个元素的排列，其中每个元素都不能在其原本的位置，求总方案数。 设总方案数为$f(n)$。显然$f(1)=0,f(2)=1$。 我们分类讨论第$n$个元素的情况。设它放在了位置m。 + 若$m$放在了位置$n$，则其余元素、位置与$m、n$无关。共有$f(n-2)$种方案。 + 若$m$没有放在位置$n$。那么我们不看位置$m$和里面的球$n$，则其余的元素和位置是独立而一一对应的，位置$n$和球$m$相对应。共有$f(n-1)$种方案。 这里的对应意为“$x$不能放在位置$y$中”。 递推公式为$f(n)=(n-1)(f(n-1)+f(n-2))$。（因为选$m$有$n-1$种方法。

4）二项式定理

$$(x+1)^n=\sum_{i=0}^n \binom{n}{i}x^i$$ 杨辉三角（帕斯卡三角）为一个数表，其第i行第j列为$\binom{i}{j}$ 有这样一个递推式： $$\binom{i}{j}=\binom{i-1}{j-1}+\binom{i-1}{j}(0

5）容斥原理

先 不考虑 重复情况，最后再将重复情况排除。 $$|A\cup B|=|A|+|B|-|A\cap B|$$ 更为广义的情况： $$ |S_1\cup S_2\cup \cdots \cup S_n|= \sum_{S\subseteq\{1,2,3,\cdots ,n\}} (-1)^{|S|+1}|\bigcap_{i\in S}S_i| $$

6) 抽屉原理

$(n+1)$个苹果放在$n$个抽屉里，必有一个抽屉有两个苹果； $n$个苹果放在$m$个抽屉里，必有一个抽屉有$\lceil \frac{n}{m} \rceil$个苹果。