容斥原理与概率期望-学习笔记

CJ_Fu · 2022-07-20 17:05:12 · 个人记录

容斥原理

容斥原理的引入

例

假设班里有 10 个学生喜欢数学，15 个学生喜欢语文，21 个学生喜欢编程，班里至少喜欢一门学科的有多少个学生呢？
是 10 + 15 + 21 = 46 个吗？

解析

不是的，因为有些学生可能同时喜欢数学和语文，或者语文和编程，甚至还有可能三者都喜欢。

假如告诉你有 5 名学生同时喜欢数学和语文，6 名学生同时喜欢数学和编程，7 名学生同时喜欢语文和编程，3 名学生同时喜欢数学语文和编程，那么班里至少喜欢一门学科的有多少个学生呢？

容易得到答案，为 10+15+21-5-6-7+3=31~\text{人}。

为了叙述方便，我们把喜欢语文、数学、编程的学生集合分别用 A, B, C 表示，则学生总数等于 A∪ B∪C 。刚才已经讲过，如果把这三个集合的元素个数 |A|, |B|, |C| 直接加起来，会有一些元素重复统计了，因此需要扣掉 |A ∪ B|, |A ∪ C|, |B ∪ C|，但这样一来，又有一小部分多扣了，需要加回来，即 |A ∪ B ∪ C|。

把上述问题推广到一般情况，就是我们熟知的容斥原理。

容斥原理的一般性

设 f(S) 表示集合 S 中数的个数。

则有：

更加一般的，设 S 为 A_i 的集合，那么有：

容斥原理的证明

我们需要证明在 A_{i} 集合中的任意元素 x , 都由右边的算式被正好 加上了一次。

假设有一任意元素在 k 个 A_{i} 集合中 (k\ge 1) , 我们来验证这个元素正好被加了一次:

• 当 \operatorname{size}(T)=1 时, 元素 x 被加了 C_{k}^{1} 次。
• 当 \operatorname{size}(T)=2 时, 元素 x 被减了 C_{k}^{2} 次。

以此类推。

• 当 \operatorname{size}(T)>k 时, 元素 x 不被考虑。

算算看对不对?

最后它的计算次数就是 \sum_{i=1}^{k}(-1)^{i-1} C_{k}^{i}。
提取一个 (-1) , 是 -\sum_{i=1}^{k}(-1)^{i} C_{k}^{i} 1^{k-i} 。
用二项式定理算出来就是 1-(1-1)^{k}=1 。

习题

例 1

长度为 n 的序列，每个位置可以填 0, 1, 2，且 0, 1, 2 三个字符在序列中至少出现一次，求方案数。n ≤ 10^5。

解析

先随便填，但是会填出不合法。

减去 0 不出现的，减去 1 不出现的，减去 2 不出现的，就会减多。

加上 0, 1 同时不出现的，加上 0, 2 同时不出现的，加上 1, 2 同时不出现的，又加多了。

减去 0, 1, 2 同时出现的，就可以了。

实际上是前面容斥问题的一个简单应用。

例 2

大家已经知道怎么求给定一个方程 \sum\limits^n_{i=1} x_i = b，问非负整数的个数。

现在有限制，x_i ≤ r_i,n ≤ 20。

解析

相当于求每个 x_i 单独合法的交。

考虑容斥，每次枚举哪些 x_i 不满足限制，即 x_i ≥ k_i +1，然后配上正确的容斥系数。

如何让 x_i 不满足限制？

设 x_i' = x_i + k_i + 1，然后把 x_ i' 替换 x_i 就行了。

例 3：\texttt{U177764 错排问题}

错排就是对于 1 ∼ n 的排列 a_i ，对于所有的 i ，满足 ai \not= i。

错排问题就是求数量。

解析

1. 容斥解法：

设 S_{i} 为 a_{i}=i 的排列数。答案是什么?
答案就是 n !-\cup_{i} S_{i} 。后面一堆怎么求?
对 \cup_{i} S_{i} 实行容斥
假设我们枚举的集合大小为 k , 那么 \cap_{i} S_{i} 是什么?

而在此问题中所有的数等价。故 $\cup_{i} S_{i}=\sum_{k=1}^{n}(-1)^{k-1} C_{n}^{k}(n-k) !

把组合数展开化简, 得到 n ! \sum_{i=1}^{n} \frac{(-1)^{k-1}}{k !}
故答案为 n !-n ! \sum_{i=1}^{n} \frac{(-1)^{k-1}}{k !}=n ! \sum_{i=0}^{n} \frac{(-1)^{k}}{k !}

2. DP 解法：

设 $f[n]$ 表示长度为 $n$ 的序列的错排数，再结合 $\text{Hint}$ 想想转移。 假设第 $n$ 个数放在 $x$，设当前序列为 $a$。 若 $a[n] = x$，则除了 $n, x$ 的 $n - 2$ 个数是独立的错排。 若 $a[n]\not= x$，则除了 $n$ 的 $n - 1$ 个数是独立的错排。 $x$ 的取值有 $(n-1)$ 种，故 $f[n] = (n-1)(f[n-1]+f[n-2])$。

概率与期望

概率的定义

概率简单来说就是一个事件有多大的可能发生。

准确的，我们把一次试验所有可能发生情况称作样本空间，对于投一个骰子，样本空间就是 Ω = {1, 2, 3, 4, 5, 6}

在样本空间内的事件 A，其是由样本空间内的情况组成的，如扔一个骰子点数为奇数的事件 B = {1, 3, 5}。

因为事件在一定程度上是以集合的含义定义的，因此可以把事件当作集合来对待。即事件 A, B 同时发生为 A ∩ B (简记为 AB)，两个中只要有一个发生为 A ∪ B。

古典概型

不要被名字吓到。它就是满足下面两个要求的试验

• 试验只有有限个基本结果；
• 试验的每个基本结果出现的可能性是一样的；

在这个条件下，事件 A 发生的概率是 \frac{|A|}{|Ω|}。我们一般把上述概率叫 p(A)。

古典概型下的概率性质

条件概率： 记 p(B \mid A) 表示在 A 事件发生的前提下， B 事件发生的概率, 则

独立事件

直观地说，我们认为两个东西独立，当它们在某种意义上互不影响。

例如，一个人出生的年月日和他的性别，这两件事是独立的；但一个人出生的年月日和他现在的头发总量，这两件事就不是独立的，因为一个人往往年纪越大头发越少。

数学中的独立性与这种直观理解大体相似，但不尽相同。

对于独立事件 A, B,\boxed{P(AB) = P(A)P(B)} 与 A, B 独立等价。

期望的定义

一个变量 x 的期望值, 是它所有可能值乘上概率的和, 用 E(x) 表示。

设可能值的集合为 S, \boxed{E(x)=\sum_{i \in S} p(i) \cdot i}。

期望的性质

• 期望的线性性
  对于任意两个随机变量 A, B（不要求相互独立），有 \boxed{E(A + B) = E(A) + E(B)}。利用这个性质，可以将一个变量拆分成若干个互相独立的变量，分别求这些变量的期望值，最后相加得到所求变量的值。\texttt{参考证明}

• 乘积的期望 当两个随机变量 A, B 相互独立时，有 \boxed{E(AB) = E(A)E(B)}。

习题

习题 1 \texttt{CF148D Bag of mice}

袋子里有 w 只白鼠和 b 只黑鼠，A 和 B 轮流从袋子里抓，谁先抓到白色谁就赢。A 每次随机抓一只，B 每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人都没有抓到白色则 B 赢。A 先抓，问 A赢的概率。