$$\huge 容斥原理$$

$容斥原理$

$有n个集合,S_1, S_2, S_3 … S_n, |S| 表示集合S的元素个数$

$\left | \bigcup_{i= 1}^{n} S_i \right | = \sum _ {i = 1}^{n}|S_i| - \sum_{i < j \leq n}^{n}|S_i \cap S_j| + \sum_{j < k \leq n}^{n}|S_i \cap S_j\cap S_k| …$

$插板法$

问题

$有n个苹果以及m个盘子$

$要把这n个苹果全部放入m个盘子中$

$在每一个盘子上放至少1个球$

$盘子两两不同,所有苹果相同$

$求可行的方案数$

解法

$把n个苹果排成一排$

$那么只需要用m-1块板,每块板把相邻的两个苹果隔开$

$就能对应出一种方案数$

$n个苹果有n-1个位置可以进行插板$

$选择其中的m-1个位置$

$总方案数为C_{n-1}^{m-1}$

$组合数参考$组合计数

有约束的问题

$若满足题目要求的方案数比较难求$

$那么就可以用总方案数 - 不满足此要求的方案数$

$即满足题目要求的方案数$

问题

$有n个苹果以及m个盘子$

$要把这n个苹果全部放入m个盘子中$

$在第i个盘子上放至少1个球,至多放A_i个球$

$盘子两两不同,所有苹果相同$

$求可行的方案数$

解法

$设第i个盘子里放了X_i个球$

$满足 \sum _{i=1}^{m} X_i = n$

$且\forall X_i \leq A_i (1 \leq i \leq m)$

$S表示集合{1,2,3…,n}的一个子集$

$T_{S} 表示任意摆放苹果后,对于S中所有元素, i \in S , X_i > A_i 的方案总数$

$那么Ans = C_{n-1}^{m-1} - T_1 - T_2 - .... - T_n + T_{1,2} + T{1,3} + …$

其中

$$T_S = C_{n + m - 1 - \sum A_i - 1(i \in S)}^{m-1}$$