排列组合可以抽象成的模型
| 小球 \ 盒子 | 有区别 | 无区别 |
|---|---|---|
| 有区别 | $P_n^m$ | $C_n^m$ |
| 无区别 | 1 | 1 |
每个小球可以无限重复（对应采样中的有放回、replacement）。同样的，盒子也可以无限重复。
另外，无区别的对象无限重复后还是无区别的。
| 小球 \ 盒子 | 有区别 | 无区别 | 有区别（可重） |
|---|---|---|---|
| 有区别 | 同上 | 同上 | $m^n$ |
| 无区别（等效于无重复） | 同上 | 同上 | $C_{n+m-1}^{m-1}$：隔板法 |
| 有区别（可重） | $n^m$ | $C_{n+m-1}^{n-1}$：隔板法 | 无穷 |
注意上表的对称性。
每个小球$i$有各自的重复次数$a_i$，每个盒子$i$有各自的重复次数$b_i$。
一下统一称有限重复为“多重”，无限重复为“可重”。
| 小球 \ 盒子 | 有区别 | 无区别 | 有区别（可重） | 有区别（多重） |
|---|---|---|---|---|
| 有区别 | 同上 | 同上 | 同上 | $dp(n,m)=\sum_{0<=k<=b_m} C_n^k dp(n-k,m-1)：内嵌一个模型$ |
| 无区别（等效于无重复） | 同上 | 同上 | 同上 | $dp(n,m)=\sum_{0<=k<=b_m} dp(n-k,m-1)$ |
| 有区别（可重） | 同上 | 同上 | 同上 | $dp(n,m)=\sum_{0<=k<=b_m} C_{n+k-1}^{n-1} dp(n-k,m-k)$：内嵌一个模型 |
| 有区别（多重） | 动态规划：$dp(n,m)=\sum_{0<=k<=a_n} C_m^k dp(n-1,m-k)$：内嵌一个模型 | 母函数或动态规划：$dp(n,m)=\sum_{0<=k<=c_n} dp(n-1,m-k)$ | $dp(n,m)=\sum_{0<=k<=a_n} C_{n+k-1}^{m-1} dp(n-k,m-k)$：内嵌一个模型 | 内嵌一个（多重小球到可重盒子）模型，比较复杂 |
小球模型在计数要注意怎么构造递推式，而不是最终的解析解。因为会出现模型套模型的情况，这样就没有简单的解析解了。
在构造递推式的时候，可以从小球和盒子两个角度考虑，其中可能某个角度更简单一些。
小球模型有比较复杂的扩展，比如盒子有容量等。这些扩展往往是模型套模型的，至于这些模型是怎么套的？逃不开分步和分组。
这样的目的是子问题可以独立计算，往往可以降低时间复杂度。
比如$\sum_n {A_n - B_n}$，这个计数问可以分解为两个子问题：$\sum_n {A_n}$和$\sum_n {B_n}$。组合方式是相减。
比如$\sum_n {A_n * B_n}$，分解为$\sum_m {A_m}$和$\sum_m {B_m}$，组合方式是相乘。
原问题数目＝总数－反问题数目。其中反问题有时候好计算。
组合数学的计数问题有分组、分类两种思想，由于是思想（比如动态规划思想），而不是具体的算法，所以他的应用千变万化。具体的说，比如我们求解$\sum{\{a_1,a_2,...,a_m\}}$，发现这个计数比较耗时，我们可以转换思路求$\sum{\{b_1,b_2,...,b_n\}}$。其中a和b是对问题答案全体（样本空间）的不同划分方式。更具体的说，比如样本空间构成一个矩阵，我们可以以行分组，也可以以列分组，从而有两种计数方法。
主要用来解决多元恒等系数的非负整数解问题。还可以用来解决不相邻选择的计数问题。
计算多事件全集空间的大小，其中多事件间重叠。其中事件的并集好计算。
In [ ]: