期望的线性性 , 组合数 , 二项式定理 , 计数原理 , 球盒问题 , 容斥原理

Login to join training plan

习题答疑

---

期望的线性性

表达：$E(ax + by) = aE(x) + bE(y)$

总的期望 = 部分期望的和

例题

• 给定 $n$ 个石子，每次随机取走一个，求期望多少次能够取走 $1$ 号石子。

  定义法：$E(x) = \sum_{i = 1}^n i \times \left( \prod_{j = 1}^{i - 1} \dfrac{n-j}{n-j +1}\right) \times \dfrac1{n-i+1}$；

  线性性：$(n-1) \times \dfrac 12 + 1$。

• 给定 $n$ 个硬币，第 $i$ 个硬币的价值是 $w_i$，每次随机取走一个硬币，每次随机取走一个硬币，获得收益是左右两个硬币的价值的乘积，求期望收益：$E(x) = \sum_{l=1}^n \sum_{r=l+2}^n \dfrac{2\times (r-l-1)!}{(r-l+1)!} \times w_l \times w_r$

---

组合数

组合数写作 $C(n, m), C_n^m , \dbinom nm$，表示在 $n$ 个互不相同的物品中选 $m$ 个物品的方案数。

组合数公式

$C_n^m = \dfrac{n!}{m!(n-m)!}$

$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$

$\sum_{r=0}^n C_n^r = 2^n$

$\sum_{i=m}^n C_i^m = C_{n+1}^{m+1}$

$\sum_{i=0}^k C_n^i \times C_{m}^{k-i}$

求组合数

给定 $n,m,P$，保证 $P$ 为质数，求 $C_n^m \bmod P$。

1. $m \le n \le 10^3, P \le 10^9$，递推公式预处理；
2. $m \le n \le 10^9, P \le 10^9$，预处理阶乘及阶乘的逆元，利用阶乘公式求解；
3. $m \le n \le 10^{9}, P \le 10^5$，卢卡斯定理 $C_n^m = C_{\frac nP}^{\frac mP} \times C_{n\bmod P}^{m\bmod P} \bmod P$

---

二项式定理

二项式定理求解这样一类问题：$\begin{matrix}\underbrace{(a+b)\times (a+b) \times \cdots \times (a+b)}\\n个\end{matrix}$，其公式为 $(a+b)^n = \sum_{i=0}^n C_n^i a^ib^{n-i}$

---

计数原理

加法原理

做一件事，完成它有 $N$ 类方式，第一类方式有 $M_1$ 种方法，第二类方式有 $M_2$ 种方法，$\dots$，第 $N$ 类方式有 $M_N$ 种方法，那么完成这件事情共有 $M_1 + M_2 + \dots + M_N$ 种方法。

乘法原理

做一件事，完成它需要分成 $N$ 个步骤，做第一步有 $M_1$ 种不同的方法，做第二步有 $M_2$ 种不同的方法，$\dots$，做第 $N$ 步有 $M_N$ 种不同的方法。那么完成这件事共有 $M_1 \times M_2 \times M_N$ 种不同的方法。

减法原理

总的减去不合法的就是所求的。

鸽巢原理（抽屉原理）

将 $n+1$ 个物品放到 $n$ 个抽屉里，总会有一个抽屉里放了至少 $2$ 个物品。

将 $n+2$ 个物品放到 $n$ 个抽屉里，总会有一个抽屉里放了至少 $2$ 个物品。

……

将 $2n$ 个物品放到 $n$ 个抽屉里，总会有一个抽屉里放了至少 $2$ 个物品。

将 $2n + 1$ 个物品放到 $n$ 个抽屉里，总会有一个抽屉里放了至少 $3$ 个物品。

除法原理

假设我们要求的方案都在集合 $A$ 里，如果我们能找到一个集合 $B$，使得 $A$ 中的每个方案和 $B$ 中的每个元素一一对应，那么我们数数 $B$ 中的元素个数就行了。

可重集的排列数

有 $n$ 个元素，它们共分成了 $m$ 类，第 $i$ 类有 $sz_i$ 个元素，求排列的方案数。

$$\dfrac{n!}{sz_1! \times sz_2! \times \cdots \times sz_m!} = \dfrac{n!}{\prod _{i=1}^m sz_i!}$$

---

球盒问题

洛谷日报 | P5824十二重计数法

球盒问题是组合计数问题的基本模型，绝大多数组合计数问题或者它的子问题的本质都是球盒问题。

问题描述：将 $n$ 个小球放到 $m$ 个盒子中，有多少种放法。

附加条件：

• 小球之间区分/不区分
• 盒子之间区分/不区分
• 每个盒子随便放/最多放一个/最少放一个

所以球盒问题共有 $2 \times 2 \times 3$ 种问法：

1. [小球区分][盒子区分][随便放] : 每个小球有 $m$ 种去处，乘法原理相乘得 $m^n$；
2. [小球区分][盒子区分][最多放一个] : 排列数 $A_m^n$；
3. [小球不区分][盒子区分][最多放一个] : 组合数 $C_m^n$；
4. [小球不区分][盒子区分][最少放一个] : 隔板法，将小球排成一列，那么会产生 $n-1$ 个空，在这些空中放入 $m-1$ 个挡板，这样就能把小球分成 $m$ 段。放置挡板的方案数是 $C_{n-1}^{m-1}$；
5. [小球不区分][盒子区分][随便放] : 先将小球的数量增加 $m$ 个，就变成了一共 $n+m$ 个小球。根据问题 $4$ 的解决方法，共有 $C_{n+m-1}^{m-1}$ 种插板的方案。在这样放出来的结果的基础上，在每个盒子中删掉一个小球，总方案数不变；
6. [小球区分][盒子不区分][最多放一个] : 如果 $n \le m$ 为 $1$，反之为 $0$；
7. [小球不区分][盒子不区分][最多放一个] : 与第 $6$ 问类似，如果 $n \le m$ 为 $1$，反之为 $0$；
8. [小球不区分][盒子不区分][最少放一个] : 转化成求 $x_1 + x_2 + x_3 + \dots + x_m = n (x_i>0)$ 的个数，设 DP 状态 $f_{i, j}$ 表示把 $n$ 化成 $m$ 个正整数的方案数，转移式为 $f_{i, j} = f_{i-1, j-1} + f_{i-j, j}$；
9. [小球不区分][盒子不区分][随便放] : 相当于在第 $8$ 问中允许一些 $x_i = 0$，枚举有多少 $x \ne 0$，相加得到 $\sum_{i=1}^mf_{n, i}$；
10. [小球区分][盒子区分][最少放一个] : No；
11. [小球区分][盒子不区分][随便放] : No；
12. [小球区分][盒子不区分][最少放一个] : No。

---

容斥原理

容斥用来解决这样一类问题：给定若干限制条件，要求每个限制条件都满足的方案数。它们往往正着做满足条件很困难。

• 求 $1000$ 以内与 $2, 3, 5$ 互质的数的个数。

  $1000 - \dfrac {1000}2 - \dfrac {1000}3 - \dfrac {1000}5 + \dfrac {1000}{2\times 3}+ \dfrac {1000}{2\times 5}+ \dfrac {1000}{3\times 5} + \dfrac {1000}{2\times 3 \times 5}$。

• 在 $n \times m$ 的棋盘上放棋子，棋子有 $c$ 种不同的颜色，同一个位置最多放一个棋子，要求每行至少有一个棋子，每列至少有一个棋子，每种颜色的棋子至少在棋盘中有一个，求方案数。

  设 $f(p, q, r)$ 表示至少有 $p$ 个行 $q$ 个列没有棋子，至少 $r$ 种颜色没有出现的方案数：$f(p, q, c) = C_n^p C_m^q C_c^r(c+1-r)^{(n-p)(m-q)}$。