2019暑期集训第二讲：组合数学&概率&数学期望
主讲人：韩耀东
时间：7.19
组合数学 & 概率期望DP
组合数学
1. 排列组合
1. 加法原理
完成一列事的方法有 n 类，其中第 i 类方法包括$a_i$种不同的方法，且这些方法互不重合，则完成这件事共有 $a_1 + a_2 + \cdots + a_n$ 种不同的方法
2. 乘法原理
若完成一件事需要 n 个步骤，其中第 i 个步骤有 $a_i$ 种不同的完成方法，且这些步骤互不干扰，则完成这件事共有 $a+1 a_2 \cdots * a_n$ 种不同的方法
两原理的区别：
一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”
3. 排列数
在 $n$ 个不同元素种，任取 $与均为自然数，下同m(m\leq n,m与n均为自然数，下同)$ 个元素按照一定的顺序排成一列，叫做从$n$个不同元素中取出$m$ 个元素的一个排列；产生排列的个数叫做从 $n$ 个不同元素中取出 $m$个元素的排列数，用符号 $A_n^m$ 来表示
排列分为全排列和部分排列，全排列的m = n
4. 组合数
从 n 个不同元素中，任取$m (m\leq n)$个元素组成一个集合，叫做从n 个不同元素中取出m 个元素的一个组合；从n个不同元素中取出$（m （m\leq n)$ 个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数。用符号$或者是C_n^m (或者是 (^m_n) )$表示
组合数性质
- $C_n^m = C_n^{n-m}$
- $Cn^m = C{n-1} ^ m + C_{n-1} ^{m-1}$ (可用杨辉三角推到)
- $C_n^0 + C_n^1 + C_n^2 + C_n^3 + \cdots + C_n^n = 2^n$
- $\sum{i=0}^m C_n^i C_m^{m-i} = C{m+n}^m(n \geq m) $ 分开取和一起取是一样的（也可以理解成先取和后取）
5. 多重集的排列数
设集合 $S = {n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k}$ ,是由$n_1$ 个$a_1$，$n_2$个$a_2$$\cdots$ $n_k$ 个 $a_k$ 组成的多重集。S的全排列个数为：
6. 多重集的组合数
n种不一样的球，每种球的个数是无限的，从中选k个出来组成一个多重集（不考虑元素的顺序），产生的不同多重集的数量为：
$C_{n+k-1} ^ {k-1}$
如何证明？
设第 i 个元素选$x_i$ 个，问题转化为方程$x_1+x_2+\cdots+x_n = k$的非负整数解的个数。令$y_i = x_i + 1$ ,则答案为$y_1+y_2+\cdots y_n = k + n$ 的正整数解的个数。也就是说有$k+n$ 个 ”1“ 排成一排，问题等价于把这些“1” 分成 k 个部分，有多少种方法？
7. 不相邻的排列
$1\sim n$ 这 n 个自然数中选k 个，这k 个数中任何两个数不相邻数的组合有 $C_{n-k+1}^k$种
设取出来的k个数为：
$1 < b_1 < b_2 < b_3 < \cdots < b_k \le n$
要保证两数字没有相邻，那么两数相差至少间隔一
$1 \le b_1 < b_2-1 < b_3-2 < b_4-3 < \cdots < b_k-k+1 \le n-k+1 $
在这里，转换为了C系列，设$c[i] = b[i] - i + 1$ ，所以
$1 \le c_1 < c_2 < c_3 < c_4 < \cdots < c_k \le n-k+1 $
所以问题就变成：在n-k+1个元素种选中k 个组合数$C_{n-k+1}^k$
8. 错位排列
胸口贴着编号为$1,2,\cdots,n$ 的 n 个球员分别住在编号为$1,2,\cdots ,n$ 的n个房间里面。现规定每个人住一个房间，自己的编号不能和房间的编号一样
设答案为 $d[n]$
只考虑第 n 个人，
假如n指定要和第 i 个人互换房间，那么其他 n - 2 个人怎么分不关他们的事情，这样的 i 有 n - 1 个，故这种情况对答案的贡献是$(n-1)$ 个 $d[n-2]$。
假如n只是要第 i 个人到他的房间，但他自己不去第 i 个房间，也就是说不是互换，那么该怎么思考呢？既然n不到第 i 个房间，那可以让n把自己胸口贴的标号换成 i ，假装自己是 i，然后错排$1\sim n$ 。这样他自己就一定不会呆在第 i 个房间了。所以有 n-1 个 d[n-1].
故答案为 $d[n] = (n-1)(d[n-1] + d[n-2]) (n\ge 3)$
同时也有 $d[n] = n \times d[n-1]+ (-1)^n$
9. 圆排列
n 个人全部来围成一圈为$Q_n^n$ ，其中已经排好的一圈，从不同位置断开，又变成不同的队列。所以：$Q_n^n \times n = A_n^n \rarr Q_n = (n-1)!$
由此可知部分圆排列为 $Q_n^r = {A_n^r \over r} = {n! \over r \times (n-r)!}$
组合数求法
- 递推公式$O(n^2)$
- 定义（预处理阶乘）
- 数字比较大阶乘会爆的话就会取模。然后除法用逆元来算，卢卡斯可以更好的做这件事情
卢卡斯定理
$Cn^k = C{n\over p}^{k\over p} * C_{n\%p}^{k\%p} \pmod p$
洛谷P3807
1 |
|
2. 卡特兰数
引子：给一个凸多边形，用n-3条不相交的对角线把它分成n-2个三角形，求不同的方法数目
- 边$V_1V_n$在最终的剖分种一定会恰好属于某个三角形$V_1V_nV_k$
- 两条边将多边形划分为了一个k边形和一个$n-k+1$边形
故$f(n) = f(2)f(n-1) + f(3)f(n-2)+\cdots + f(n-1)f(2)$
另一种思路：
考虑$V_1$ 的连线
$n(f(3)f(n-1) + f(4)f(n-2)+\cdots + f(n-1)f(3)$ 个部分
因为每个方案被计算了2n-6次，
$f(n) = (f(3)f(n-1) + f(4)f(n-2)+\cdots + f(n-1)f(3))\times n/(2n-6)$
上面两式合并可得：$f(n+1) = {4n-6\over n}f(n)$
上述这一种是紫书上面的推到方法，$f(1) = f(2) = 1$
另一种例子
n 个 0， n 个1，排列m长度序列，满足任意前缀种0的个数不少于1的个数的序列的数量为$Catn = {C{2n}^n\over n+1}$
若S不满足：任意前缀0的个数不小于1的个数
则至少存在一个最小的位置 $2*p+1\in [1,2n]$ 使得$s[1\sim 2p+1]$ 中有p个0，p+1个1
而把$s[2p+2\sim 2n]$中的所有数字取反后，包含n-p-1个0，n-p个1于是得到了n-1个0，n+1个1的序列
同理，令n-1个0，与n+1个1随意排成的序列，也必有一个最小的位置$2p’+1$，
使得$s’[1\sim2p’+1]$ 中有p’个0，p’+1个1
把s’剩下的一半取反，n个0，n个1排成的，存在一个前缀0比1多的序列
因此，以下两种序列构成一种双射
- 由n个0，n个1构成的，存在一个前缀0比1多的序列
- 由n-1个0与n+1个1排成的序列
根据组合数定义，后者有$C_{2n}^{n-1}$个
故$C{2n}^n-C{2n}^{n-1} = {C_{2n}^n\over n+1}$
$f(0) = f(1) = 1$
卡特兰数的其他例子
- 有 2n个人排成一行进入剧场。入场费 5 元。其中只有n 个人有一张 5 元钞票，另外 n人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
- 一个栈（无穷大）的进栈序列为 n有多少个不同的出栈序列？
- n个结点可够造多少个不同的二叉树？
- 一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
3. 斯特林数
第一类斯特林数
把n个不同的球分成r个非空循环排列的方法数
递推形式 : $s(n,r) = (n-1)s(n-1,r) + s(n-1,r-1),n>r \ge 1$
考虑最后一个球，他可以单独构成一个非空循环排列，也可以插入到前面一个球的一侧。
若单独，则$s(n-1,r-1)$ ，若放在某个球的一侧，则$(n-1)s(n-1,r)$
第二类斯特林数
把n个不同的球放到r个盒子里，假设没有空盒，则放球方案数记作S(n,r)，称为第二类Stirling数
$S(n,r) = rS(n-1,r) + S(n-1,r-1),n>r\ge 1$
http://acm.hdu.edu.cn/showproblem.php?pid=3625
4. 康托展开
求一个$1\sim n$的任意排列的排名
根据字典序排序，比如4的排列：[2,3,1,4] < [2,3,4,1]，因为第3位出现不同，则[2,3,1,4]的排名在[ 2,3,4,1]前面。
给定一个排列，求它的排名。例子:[2,5,3,4,1]
- 小于2 的数字为1，故有4!个排列在它前面
- 小于5的数字有1，2，3，4，但是2在前面用过了，所以有三个，故为3*3!
- 小于3的数字有1，2，2在前面用了，所以有一个，故为2！
- …
- 答案为4! + 3*3! + 2! + 1 + 1 = 46，因为是计算排名，所以要多加一个1
每次要用到当前有多少个小于它的数还没有出现，这里用树状数组统计比它小的数出现过的次数就行了。
那如何通过给定一个排名来求排列呢？（即逆康托展开）
如果我们知道一个排列的排名，就可以逆推出这个排列。因为4！是严格大于$3\times 3! + 2\times 2! + 1\times 1!$ 的，所以可以认为对于长度为5的排列，排名x除以4！向下取整就是有多少个数小于这个排列的第一位。
46-1 = 45
- $\lfloor{45\over 4!}\rfloor = 1$ ，有一个数小于它，所以第一位是2
- 45 - 4! = 21,$\lfloor{21\over 3!}\rfloor = 3$ ，有三个数小于它，去掉已经存在的2，这一位是5。
- $21-3\times 3! = 3$ $\lfloor {3\over 2!}\rfloor = 1$，有一个数小于它，那么这一位就是3
- …
暴力$O(n^2)$，用线段树二分可以优化到$O(nlogn)$
5. 容斥原理
$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$
设 U 中元素有 n 种不同的属性，而第 i 种属性称为 $P_i $, 拥有属性$P_i$ 的元素构成集合$S_i$，那么
即：
补集：
多重集的组合数（不定方程非负整数解计数）
给出不定方程$\Sigma_{i=1}^nx_i = m$ 和 n 个限制条件$x_i \leq b_i$，其中$m,b_i\leq N$,求方程的非负整数解的个数
若没有$xi \le b_i$的限制，那么答案是$C{m+n-1}^{n-1}$ 证明用插板法
容斥模型：
全集U ： 不定方程$\Sigma_{i=1}^nx_i = m$的非正整数解
元素：变量$x_i$
属性：$x_i$ 的属性即$x_i$满足的条件，即$x_i\leq b_i$的条件
目标：所有变量满足对应属性时集合的大小，即$|\bigcap_{i=1}^nS_i|$
$|U|$可以用组合数计算，后半部分用容斥定理计算
$\overline{S_i}$ 的含义是表示至少包含$b_i+1$个$a_i$的多重集。
则$\overline{Si}$的个数是：$C{n+m-b_i-2}^{n-1}$
进一地，$\overline{Si}\overline{S_j}$ 为：$C{n+m-b_i-b_j-3}^{n-1}$
由容斥定理
例题：Devu and Flowers（CF451E）
Devu有N个盒子，第 i 个盒子中有$A_i$枝花。同一个盒子内的花颜色相同，不同盒子内的花颜色不同。Devu要从这些盒子中选出M枝花组成一束，求共有多少种方案。若两束花每种颜色的花的颜色都相同，则认为这两束花是相同的方案。输出对$10^9+7$取模之后的结果即可。$1\leq N\leq20,1\le M\le 10^{14},0\leq A_i\leq 10^{12}$
- 二进制枚举
- N很小，M很小，计算组合数会爆ll
- Lucas，乘法逆元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll a[22],j[22],m,ans=0;
ll inv[22],n;
ll power(ll a,ll b){
ll res = 1;
for(;b;b>>=1){
if(b & 1)res = (res * a)%mod;
a = a*a%mod;
}
return res;
}
ll C(ll y,int x){
if(y < 0 || x < 0 || y < x)return 0;
y %= mod;
if(y == 0 || x == 0)return 1;
ll res = 1;
for(int i=0;i<x;i++){
res = res * (y-i) % mod;
}
//res = res * inv[x] % mod;
for(int i=1;i<=x;i++)
res = res * inv[i]%mod;
return res;
}
int main(){
j[0] = 1;
for(int i=1;i<=20;i++){
//j[i] = j[i-1] * i % mod;
inv[i] = power(i,mod-2);
}
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int x=0;x < (1<<n);x++){
if(x == 0)
ans = (ans + C(n+m-1,n-1)) % mod;
else{
ll t = n + m;
int p = 0;
for(int i=0;i<n;i++){
if(x >> i & 1){
p ++ ;
t -= a[i+1];
}
}
t -= p + 1;
if(p & 1) ans = (ans - C(t,n-1))%mod;
else ans = (ans + C(t,n-1))%mod;
}
}
printf("%lld\n",(ans + mod) % mod);
return 0;
}
例题：HAOI2008 硬币购物
https://www.luogu.org/problemnew/show/P1450
4种面值的硬币，第 i 种的面值是$C_i$。n次询问，每次询问给出每种硬币的数量$D_i$和一个价格S，问付款方式。$n\leq 10^3 ,S\leq 10^5$
如果用背包做的话，复杂度是O(4nS)，无法承受。
$\sum_{i=1}^4C_ix_i = S, x_i\leq D_i$的非负整数解的个数
采用同样的容斥方式，$x_i$的属性为$s_i\leq D_i$，套用容斥原理的公式
S可由无限背包来打表求，后面的用容斥定理
1 |
|
Mobius函数
$\mu$ 为莫比乌斯函数
通俗的讲，当n包含相等的质因子时，$\mu(N)=0$ 。当N的所有质因子各不相等时，若N有偶数个质因子，$\mu(N) = 1$，若N有奇数个质因子，$\mu(N)=-1$ 。
若只求一项Mobius函数，则分解质因数即可计算，若求 $1\sim N$的每一项Mobius函数，可以利用线性筛法来求mobius函数
1 | void getMu(){ |
6.抽屉原理（鸽巢原理）
就比如说，你有 n+1 个苹果，想要放到 n 个抽屉里，那么必然会有至少一个抽屉里有两个（或以上）的苹果。
这个定理看起来比较显然，证明方法考虑反证法：假如所有抽屉都至多放了一个苹果，那么 n个抽屉至多只能放n个苹果，矛盾。
概率&数学期望
1. 概率
定义
如果在相同条件下，进行了n次试验，事件A发生了$N_A$次，那么$N_A \over n$被称为事件A发生的概率
公理
- 非负性：对于一个事件A，有概率$P(A)\in [0,1]$
- 规范性：事件空间的概率值为1，$P(S) = 1$
- 容斥性：若$P(A+B) = P(A)+P(B)$，则 A 和 B 互为独立事件。
计算
全概率公式
若事件$A1,A_2,\cdots ,A_n$构成一个完备的事件且都有正概率，即$且\forall i,j,A_i\cap A_j=\varnothing 且\sum{i=1}^nAi=1$，有$P(B) = \sum{i=1}^nP(A_i)P(B|A_i))$
例子：参加比赛拿金概率0.1，拿银概率0.2，拿铜概率0.3，这三种情况下，你被妈妈表扬的概率是：1.0，0.8，0.6，那么你被妈妈表扬的总概率就是$0.1\times 1.0+0.2\times 0.8+0.3\times 0.6 = 0.44$
贝叶斯公式
2.期望
定义
在一定区间内变量取值为有限个，或数值可以一一列举出来的变量称为离散型随机变量。一个离散型随机变量的数学期望是在试验中每次可能的结果乘以其结果概率的总和。
性质
全期望公式 ：$E(Y) = E[E(Y|X)]$。可由全概率公式证明。
线性性质 ：对于任意两个随机事件$x,y$（不要求相互独立），有$E(X+Y) = E(X) + E(Y)$
例题
1. 麻球繁衍(UVA-11021)
有k只麻球，每只活一天就会死亡，临死之前可能会生出一些新的麻球。具体来说，生 i 个麻球的概率为$P_i$。给定m，求m天后所有麻球均死亡的概率。注意，不足m天时就已全部死亡的情况也算在内。
核心：递推，找出递推所依靠的东西
$f(i)$为一开始只有一个麻球的时候，在 i 天后所有麻球均死亡的概率。
则有：$f(i) = P0 + P_1 f(i-1) + P_2[f(i-1)]^2 + \cdots + P{n-1}*[f(i-1)]^{n-1}$
因为每个麻球死亡是独立的。所以答案为$f(m)^k$
1 |
|
2. 玩纸牌（UVA-11427）
每天晚上你都玩纸牌游戏，如果第一次就赢了就高高兴兴地去睡觉，如果输了就继续玩。假设每盘游戏你获胜地概率都是p，且各盘游戏的输赢都是独立的。你是一个固执的完美主义者，因此会一直玩到当晚获胜局面的比例严格大于p时才停止，然后高高兴兴地去睡觉。当然，晚上的时间有限，最多只能玩n盘游戏，如果获胜比例一直不超过p的话，你只能垂头丧气地去睡觉，以后再也不玩纸牌了。你的游戏是计算出平均情况下，你会玩多少个晚上的纸牌。
1 |
|
3. 得到1（UVA 11762)
给出一个整数N，每次可以在不超过N的素数中随机选择一个P6 ，如果P是N的约数，则把N变成N/P，否则N不变。问平均情况下需要多少次随机选择，才能把N变成1？比如N=3时答案为2，N=13时答案为6
1 |
|
4. 决斗（UVA-1636）
首先在枪里装一些子弹，然后扣了一枪，发现没有子弹。你希望下一枪也没有子弹，是应该直接再扣一枪（输出SHOOT）呢，还是随即转一下再扣（输出ROTATE)？如果这两种策略下没有子弹的概率相等，输出EQUAL.
手枪里的子弹可以看成一个循环序列，开枪一次以后对准下一个位置。例如子弹序列为0011时，第一次开枪前一定在位置1或2（因为第一枪没有子弹），因此开枪之后位于位置2或3。如果此时开枪，有一半的概率没有子弹。序列长度为2~100。
1 |
|
5. 奶牛和轿车(UVA-10491)
在a+b扇门，a扇后面是牛，b扇后面是车。在你选择一扇门后，主持人为你打开另外c个有奶牛的门（$1\le a\le 10000, 1\le b \le 10000, 0\le c < a$），输出此刻你选择换门之后赢得车的概率。
1 |
|
6. 条件概率(UVA-11181)
有 n 个人准备去超市逛，其中第 i 个人买东西的概率是$P_i$。 逛完以后你得知有 r 个人买了东西。根据这一信息，请计算每个人实际买了东西的概率。输入 n ($1\le n \le 20$) 和 r ($0\le r \le n$), 输出每个人买东西的概率。
1 |
|
7. 纸牌游戏(UVA-1637)
36张牌分成9堆，每堆4张牌。每次可以拿走某两堆顶部的牌，但需要点数相同。如果有多种拿法则等概率的随机拿。例如，9堆顶部的牌分别为KS,KH,KD,9H,8S,8D,7C,7D,6H，则有5种拿法(KS,KH),(KS,KD),(KH,KD),(8S,8D),(7C,7D)，每种拿法的概率均为1/5。如果最后拿完所有牌则游戏成功。按顺序给出每堆的四张牌，求成功概率。
1 |
|
8. 过河(UVA-12230)
你住在村庄A，每天需要过很多条河到另一个村庄B上班。B在A的右边，所有的河都在中间。幸运的是，每条河上都有匀速移动的自动船，因此每当到一条河的左岸时，只需等船过来，载着你过河，然后在右岸下船。你很瘦，因此上船之后船速不变。
从A到B，平均情况下需要多久时间？假设在出门时所有船的位置都是均匀随机分布的。如果位置不是在河的端点处，则朝向也是均匀随机。在陆地上行走的速度为1
给出AB之间河的个数，长度D，以及每条河的左端离A的距离p，长度L和移动速度v，输出A到B的数学期望。
1 |
|
9. 糖果(UVA-1639)
有两个盒子各有 n ($n\le 2\times 10^5$)个糖，每天随机选一个（概率分别为p，1-p），然后吃一颗糖。直到有一天，打开盒子一看，没糖了！输入n，p，求此时另一个盒子里糖的个数的数学期望。
1 |
|
10. 优惠券(UVA-10288)
大街上到处在卖彩票，一元钱一张。购买撕开它上面的锡箔，你会看到一个漂亮的图案。图案有n种，如果你收集到所有 n ($n\le 33$)种彩票，就可以得大奖。请问，在平均情况下，需要买多少张彩票才能得到大奖呢？如 n = 5 时答案为137/12。
1 |
|
11. 危险的组合(UVA-580)
有一些装有铀（U）和铅（L）得盒子，数量均足够多。要求把n($n\le 30$) 个盒子放在一行，但至少有3个U放在一起，有多少种方法？
1 |
|
12. 比赛名次(UVA-12034)
A，B两人赛马，最终名次有3种可能：并列第一；A第一B第二；B第一A第二。输入n($1\le n\le 1000$)，求n人赛马时最终名次的可能性的个数除以10056的余数
1 |
|
13. 杆子的排列(UVA-1638)
有高为$1,2,3,\cdots n$的杆子各一根排成一行。从左边能看到 $l$ 根，从右边能看到$r$ 根，求有多少种可能。
1 |
|
