I：球之间互不相同，盒子之间互不相同。
对于这部分的计数，很显然方案总数是 \(nm\)
II：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
对于这部分的计数，每个盒子只有 \(0/1\) 两种状态
对于每种都需要在没选出来的里做出选择，方案数也就是 \(\prod_{i=0}^{n-1}(m-i)\)
III：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。
我们考虑进行容斥，结果就是：\((0个盒子空置的方案数)−(1个盒子空置的方案数)+(2个盒子空置的方案数)-.... = \sum_{i=0}^{m}(-1)^i \dbinom{m}{i}(m-i)^n\)
IV：球之间互不相同，盒子全部相同。
我们考虑吧枚举有多少个空盒子，那么我们就可以列出以下式子
\[\begin{align} ans&=\sum_{i=1}^{n}\frac{\sum_{j=0}^{i}(-1)^j \dbinom{i}{j}(i-j)^n}{i!} \\ &=\sum_{i=1}^{n}\frac{\sum_{j=0}^{i}(-1)^j \frac{i!}{j!(i-j)!}(i-j)^n}{i!}\\ &=\sum_{i=1}^{n}{\sum_{j=0}^{i}(-1)^j \frac{1}{j!(i-j)!}(i-j)^n}\\ &=\sum_{i=1}^n\frac{(-1)^n}{j!}\sum_{j=0}^{i}\frac{(i-j)^n}{(i-j)!}\\ &=\sum_{j=0}^n\frac{(-1)^n}{j}\sum_{i=j}^{m}\frac{(i-j)^n}{(i-j)!}\\ &=\sum_{j=0}^n\frac{(-1)^n}{j}\sum_{i=0}^{m-j}\frac{i^n}{i!} \end{align} \]V：球之间互不相同，盒子全部相同，每个盒子至多装一个球
考虑看 \(n\) 是否大于 \(m\)，\(ans = [n\le m]\)
VI：球之间互不相同，盒子全部相同，每个盒子至少装一个球。
我们发现我们在推 IV 时相当于是对空的盒子枚举，只要我们去掉枚举这一步就是 VI 了
\[ans=\frac{\sum_{j=0}^{i}(-1)^j \dbinom{i}{j}(i-j)^n}{i!} \]VII：球全部相同，盒子之间互不相同。
隔板法直接求解，\(ans = \dbinom{n+m-1}{m-1}\)
VIII：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
这个明显是最基础的 \(m\) 选 \(n\)，所以是 \(ans = \dbinom{n}{m}\)
X：球全部相同，盒子全部相同。
我们考虑问题可以转化为：将 \(n\) 拆成 \(m\) 个无序整数的方案数
直接做好像比较困难，那么我们可以根据 Ferrers 图 来转化
\[\begin{align} ans&=p(n,m)\\ &=\prod_{j=1}^{n}\frac{1}{1-x^j} \end{align} \]然后考虑使用 付公主的背包 同款做法来求即可
XI：球全部相同，盒子全部相同，每个盒子至多装一个球。
和 V 同理，\(ans = [n\le m]\)
XII：球全部相同，盒子全部相同，每个盒子至少装一个球。
这个就相当于让我们把 X 那里的自然数变为正整数，要求每个盒子都要有起码一个球
这种情况下结果很明显是 \(p_{n-m,m}\)
标签：十二重,盒子,相同,sum,ans,计数法,解题,互不,frac From： https://www.cnblogs.com/Vsinger-LuoTianYi/p/18373573