十二重计数法

Link，限制依次为：

\(1\)：球之间互不相同，盒子之间互不相同。

\(2\)：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。

\(3\)：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。

\(4\)：球之间互不相同，盒子全部相同。

\(5\)：球之间互不相同，盒子全部相同，每个盒子至多装一个球。

\(6\)：球之间互不相同，盒子全部相同，每个盒子至少装一个球。

\(7\)：球全部相同，盒子之间互不相同。

\(8\)：球全部相同，盒子之间互不相同，每个盒子至多装一个球。

\(9\)：球全部相同，盒子之间互不相同，每个盒子至少装一个球。

\(10\)：球全部相同，盒子全部相同。

\(11\)：球全部相同，盒子全部相同，每个盒子至多装一个球。

\(12\)：球全部相同，盒子全部相同，每个盒子至少装一个球。

---

\[5.[n\le m] \]

可否把所有球都扔进去。

\[11.[n\le m] \]

同。

\[1.m^n \]

每个球依次选盒子。

\[8.\binom mn \]

选 \(n\) 个盒子装球。

\[2.A\binom mn \]

选 \(n\) 个盒子，塞完球然后排列。

\[9.\binom{n-1}{m-1} \]

插板法。

\[7.\binom{n+m-1}{m-1} \]

插板法，先给每个盒子塞一个球保证正整数。

\[6.\begin{Bmatrix}n\\m\end{Bmatrix} \]

第二类斯特林数定义。

\[4.\sum_{k=1}^m\begin{Bmatrix}n\\k\end{Bmatrix} \]

枚举非空盒子个数。把第二类斯特林数·行贺过来即可。

\[3.\sum_{k=0}^m (-1)^k\binom mk (m-k)^n \]

容斥，枚举 \(k\) 表示至多有 \(k\) 个有球的盒子。

---

记 \(p(n,m)\) 表示将 \(n\) 分拆成至多 \(m\) 个正整数的方案数。那么

\[10.p(n,m) \]

\[12.p(n-m,m) \]

\(n-m\) 意为事先给每个盒子扣掉一个球。

把 \(p(n,m)\) 的方案用点阵表示出来（此处 \(n=7,m=3\)）：

\[\begin{bmatrix}1&1&1&1\\1&1\\1\end{bmatrix} \]

其行数 \(\le m\)。将其转置（顺时针转 \(90^\circ\) 然后水平翻转）：

\[\begin{bmatrix}1&1&1\\1&1\\1\\1\end{bmatrix} \]

那么其列数 \(\le m\)。这个矩阵还是表示一种拆分方案，且容易知道新矩阵和原矩阵一一对应。

于是 \(p(n,m)\) 变成了：将 \(n\) 分拆成任意多个 \(\le m\) 的正整数的方案数。

这个是付公主的背包。记

\[\operatorname{princess}(n,m)=\prod_{i=1}^m \frac 1{1-x^i} \]

按照原题，可以对每个 \(i\) 求 \(\ln\) 之后一通操作 \(O(m\ln n)\) 得到答案的 \(\ln\) 值，然后 \(\exp\) 回来即可。然后有

\[p(n,m)=[x^n]\operatorname{princess}(n,m) \]

于是

\[10.[x^n]\operatorname{princess}(n,m) \]

\[12.[x^{n-m}]\operatorname{princess}(n,m) \]