十二重计数法

标签：十二重 盒子 每个 区分 互相 计数法 答案 之间

\(n\) 个球，\(m\) 个盒子，求在一定限制条件下把小球放入盒子的方案数。

1. 球之间互相区分，盒子之间互相区分。

每个球能放 \(m\) 个盒子，显然是:

\[m^n \]

2. 球之间互相区分，盒子之间互相区分，每个盒子至多放一个球。

先选出装了球的盒子，然后排列球的顺序。
答案为：

\[\binom{m}{n} n! = m^{\underline{n}} \]

3. 球之间互相区分，盒子之间互相区分，每个盒子至少放一个球。

容斥，答案为：

\[\sum_{i = 0}^n (-1)^i \binom{m}{i} (m - i)^n \]

4. 球之间不互相区分，盒子之间互相区分。

插板，答案为：

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

5. 球之间不互相区分，盒子之间互相区分，每个盒子至多放一个球。

答案为:

\[\binom{m}{n} \]

6. 球之间不互相区分，盒子之间互相区分，每个盒子至少放一个球。

可以先每个盒子都放一个，然后就变成了 4.。
答案为：

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

7. 球之间互相区分，盒子之间不互相区分。

发现每个盒子只由它装了哪些球来区分，没有装球的盒子是没有区别的。
所以可以先枚举装了球的盒子数，答案就是斯特林子集数的行前缀和：

\[\sum_{i = 1}^m \begin{Bmatrix} n \\ i \end{Bmatrix} \]

8. 球之间互相区分，盒子之间不互相区分，每个盒子至多放一个球。

显然答案为：

\[[n \le m] \]

9. 球之间互相区分，盒子之间不互相区分，每个盒子至少放一个球。

斯特林子集数，答案为：

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

10. 球之间不互相区分，盒子之间不互相区分。

分拆数。

转置一下，问题就从 有 \(m\) 个盒子，每个盒子中放任意个球 变成了 有任意个非空盒子，每个盒子可以放至多 \(m\) 个球。
所以答案为：

\[[z^n] \prod_{i = 1}^m \dfrac{1}{1 - z^i} \]

可以通过先 \(\ln\) 再 \(\exp\) 的方式快速求出。

11. 球之间不互相区分，盒子之间不互相区分，每个盒子至多放一个球。

答案为：

\[[n \le m] \]

12. 球之间不互相区分，盒子之间不互相区分，每个盒子至少放一个球。

每个盒子先放一个球后就变成了 10.。
答案为：

\[[z^{n - m}] \prod_{i = 1}^m \dfrac{1}{1 - z^i} \]

标签：十二重,盒子,每个,区分,互相,计数法,答案,之间
From： https://www.cnblogs.com/definieren/p/18211289