组合数学
题单介绍
## 斯特林数
### 第二类斯特林数
也可以记做$S_{n,k}$，表示将$n$个两两不同的元素，划分为$k$个互不区分的非空子集的方案数。
递推式$S_{n,k}=S_{n-1,k-1}+k*S_{n-1,k}$
边界$S_{n,0}=0$
考虑组合意义证明。
* 将新元素单独放入一个子集，有$S_{n-1,k-1}$种方案。
* 将新元素放入一个现有的非空子集，有$k*S_{n-1,k}$种方案。
### 应用
* $n$个**不同**的球放入$m$个**相同**的盒子，**不允许**有空盒子。正是第二类斯特林数
第$i$个球，单独放入第$j$个或者，和前面$i-1$个球放入前$j$个里由于不同所有乘上了$j$。
```cpp
f[0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j];
}
}
cout << f[n][m];
```
* $n$个**不同**的球放入$m$个**不同**的盒子，**不允许**有空，答案是$S_{n,m}*m!$
因为盒子也不同因此乘上盒子的阶乘。
```cpp
ans = 1;
for (int i = 1; i <= m; i++) ans *= i;
f[0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j];
}
}
cout << ans * f[n][r];
```
* $n$个**不同**的球放入$m$个**相同**的盒子，**允许**盒子有空，答案是$\sum_{i=1}^mS(n,i)$
也就是在$i$个盒子的方案数的和
```cpp
f[0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j];
}
}
ans = 1;
for (int i = 1; i <= m; i++) ans += f[n][i];
```
* $n$个**不同**的球放入$m$个**不同**的盒子，**允许**有空。每个球都有$m$种选择，是$m^n$
```cpp
int ans = 1;
for (int i = 1; i <= n; i++) ans *= m;
```
* $n$个**相同**的球放入$m$个**相同**的盒子，**允许**有空。
链接:$\text{luoguP2386}$
```cpp
for (int i = 0; i <= m; i++) f[0][i] = f[1][i] = 1;
for (int i = 0; i <= n; i++) f[i][0] = f[i][1] = 1;
for (int i = 2; i <= n; i++){
for (int j = 2; j <= m; j++){
if (j > i) f[i][j] = f[i][i];
else f[i][j] = f[i][j - 1] + f[i - j][j];
}
}
```
* $n$个**相同**的球放入$m$个**相同**的盒子，**不允许**有空。
```cpp
for (int i = 1; i <= n; i++) f[i][1] = 1;
for (int i = 1; i <= n; i++){
for (int j = 2; j <= m; j++){
if (i >= j) f[i][j] = f[i - 1][j - 1] + f[i - j][j];
}
}
cout << f[n][m];
```
* $n$个**相同**的球放入$m$个**不同**的盒子，**允许**有空。
插板法：$C_{n-1}^{m-1}$
* $n$个**相同**的球放入$m$个**不同**的盒子，**允许**有空。
给每个盒子一个球，然后插板。$C_{n+m-1}^{m-1}$
### 第一类斯特林数
也可以记做$S_{n,k}$，表示将$n$个两两不同的元素，划分为$k$个互不区分的非空**轮换**的方案数。轮换就是环形排列
递推式$S_{n,k}=S_{n-1,k-1}+(n-1)S_{n-1,k}$
边界$S_{n,0}=0$
考虑组合意义证明。
* 将新元素单独放入一个子集，有$S_{n-1,k-1}$种方案。
* 将新元素放入一个现有的非空子集，有$k*S_{n-1,k}$种方案。
## 错位排列
递推公式：$f_i=(i-1)*(f_{i-1}+f_{i-2})$
## 二项式定理
$(a+b)^n=\sum_{i=0}^nC_n^ia^{n-i}b^i$
可以用数学归纳法$C_n^k+C_n^{k-1}=C_{n+1}^k$证明。
$P1655$ 也是一个球盒问题的模板题(第二类斯特林数)，只不过此题需要对递推关系式做高精度。
$P2822$ 由于$n,m$范围不大.所以可以杨辉三角预处理组合数，然后求一个二维前缀和的问题。
## 8要写几次题解
因为$k$最多是$16$，我们不可能枚举所有的$16$位数字去计算出现几次$8$会超时
考虑组合数学求解，答案为$1$位为$8$的情况+$2$位为$8$的情况$+\dots +k$位为$8$的情况
每一位为$8$的方案可以由**总的减去不合法**的，不合法的就是**最高位**为$0$的情况.
* 考虑只有**一位**有$8$
首先$C_k^1$选择**一个**位置为$8$，然后**剩余**的$k-1$个位置我们直接从$0\sim 9$的数字中选择即可注意**不能**选择$8$，所以每一位都是$9$个选择，$k-1$位一共$9^{k-1}$种，.此时总方案为$C_k^1*9^{k-1}$
然后**减去不合法**的，此时固定最高位就是$0$,首先$C_{k-1}^1$选择一个位置为$8$，然后**剩余的**$k-2$个位置我们直接从$0\sim 9$的数字中选择即可注意**不能**选择$8$，所以每一位都是$9$个选择，$k-2$位一共$9^{k-2}$种，此时不合法总方案为$C_{k-1}^1*9^{k-2}$
因此某一位是$8$，**其余不是**$8$的方案即为$C_k^1*9^{k-1}-C_{k-1}^1*9^{k-2}$
* 考虑**两位**有$8$
首先$C_k^2$选择**两个**位置为$8$，然后剩余的$k-2$个位置我们直接从$0\sim 9$的数字中选择即可注意**不能**选择$8$，所以每一位都是$9$个选择，$k-2$位一共$9^{k-2}$种，.此时总方案为$C_k^2*9^{k-2}$
然后**减去不合法**的，此时固定最高位就是$0$,首先$C_{k-1}^1$选择二个位置为$8$，然后**剩余的**$k-3$个位置我们直接从$0\sim 9$的数字中选择即可注意**不能**选择$8$，所以每一位都是$9$个选择，$k-3$位一共$9^{k-3}$种，此时不合法总方案为$C_{k-1}^2*9^{k-2}$
因此某两位是$8$，**其余不是**$8$的方案即为$C_k^2*9^{k-2}-C_{k-1}^2*9^{k-2}$
* 如果有$i$个位置都是$8$
方案数即为$C_k^i*9^{k-i}-C_{k-1}^i*9^{k-i-1}$
上述式子只是求有$8$的个数，由于是有$i$个$8$，还得给式子乘以$i$
方案数即为$(C_k^i*9^{k-i}-C_{k-1}^i*9^{k-i-1}) * i$
答案即为$\sum_{i=1}^k (C_k^i*9^{k-i}-C_{k-1}^i*9^{k-i-1}) * i$