$n$ 个球放入 $d$ 个盒子中，一共有多少种放置方案？

# 解释如下

注意，以下 $16$ 种方案中，其中是球不会全部放完的，需要注意

# 1. 球可区分、盒子可区分、允许多球同盒、允许空盒

每个球都有 $d$ 种选择，最终答案是

$$d^n$$

# 2. 球可区分、盒子可区分、允许多球同盒、不允许空盒

如果没有限制空盒子，那么答案是 $d^n$，现在我们希望把至少一个盒子空的情况排除掉
利用容斥原理（见下方介绍）：

• 对于每个子集 $k \subseteq \{1, ..., d\}$ 假设 $k$ 个盒子是空的
• 剩下 $d-k$ 个盒子可以用，球的数量仍然为 $n$

至少存在一个空盒的总方案数是：

$$\sum\limits_{k=0}^{d}((-1)^{k+1}·C_d^k·(d-k)^n)$$

所以最终答案为

$$d^n - \sum\limits_{k=0}^{d}((-1)^{k+1}·C_d^k·(d-k)^n)=\sum\limits_{k=0}^{d}((-1)^k·C_d^k·(d-k)^n)$$

• 必须满足 $d \ge 1$ 和 $n \ge d$，否则无法满足无空盒

# 3. 球可区分、盒子可区分、不允许多球同盒、允许空盒

分别选出 $k$ 个球和 $k$ 个盒子，然后 $A_k^k$ 的顺序放球

$$\sum\limits_{k=0}^{min(n,d)}(C_n^k ·C_d^k·A_k^k)$$

• 必须满足 $n \ge 1, d \ge 1$

# 4. 球可区分、盒子可区分、不允许多球同盒、不允许空盒

选出 $d$ 个球，排列在 $d$ 个盒子即可

$$A_n^d$$

• 必须满足 $n \ge d$

# 5. 球可区分、盒子不可区分、允许多球同盒、允许空盒

$$\sum\limits_{k=1}^{d}S(n,k)$$

• $1 \le d \le n$

# 6. 球可区分、盒子不可区分、允许多球同盒、不允许空盒

答案即为第二类斯特林数

$$S(n,d)$$

# 7. 球可区分、盒子不可区分、不允许多球同盒、允许空盒

从 $n$ 个盒子里，选出 $k$ 个盒子放入一个球（不一定全部放完，所以 $k \in [0, min(n,d)]$），答案求和即可

$$\sum\limits_{k=0}^{min(n,d)}C_n^k$$

# 8. 球可区分、盒子不可区分、不允许多球同盒、不允许空盒

因为不允许空盒，不允许多球同盒，所以必定一个球一个盒，又因为盒子不可区分，所以答案为，$n$ 个球中，选 $d$ 个球放

$$C_n^d$$

# 9. 球不可区分、盒子可区分、允许多球同盒、允许空盒

反过来想，$n+d-1$ 个球，选取其中 $d-1$ 个球当板
或者正着想，插第一个板的时候，有 $n+1$ 种方案，插第二个的时候，有 $n+2$ 种，以此类推，插到 $m-1$ 个板的时候，有 $n+m-1$ 种方案，但是板本身是没有顺序的，故答案要除以 $A_{m-1}^{m-1}$，即为
$(n+1)···(n+m-1) / A_{m-1}^{m-1}$ 即为下方式子

天才 $HYC$ 的天才思想

$$C_{n+d-1}^{d-1}$$

这个比较重要，也是考试中常出现的， $a$ 个苹果和 $b$ 个香蕉排序，结果有多少种？

# 10. 球不可区分、盒子可区分、允许多球同盒、不允许空盒

简单插板法，$n-1$ 个空插 $d-1$ 个板

$$C_{n-1}^{d-1}$$

• $n \ge d \ge 1$

# 11. 球不可区分、盒子可区分、不允许多球同盒、允许空盒

这题其实就是放入 $k$ 个球进入 $k$ 个盒子（因为没有说球要全部放完）

$$\sum\limits_{k=0}^{min(n,d)}C_n^k$$

# 12. 球不可区分、盒子可区分、不允许多球同盒、不允许空盒

$n$ 个球选 $d$ 个球去放即可，方案数即为

$$C_n^d$$

# 13. 球不可区分、盒子不可区分、允许多球同盒、允许空盒

因为允许空盒，所以选 $k$ 个盒子出来放球，答案是整数分拆数的和（下方有介绍）

$$\sum\limits_{k=1}^{d} p(n,k)$$

# 14. 球不可区分、盒子不可区分、允许多球同盒、不允许空盒

不允许空盒，所以每个盒子都至少放一个，故答案为整数分拆数

$$p(n,d)$$

• 前置条件为 $1 \le d \le n$

# 15. 球不可区分、盒子不可区分、不允许多球同盒、允许空盒

情况其实就是看，球和盒子谁少，谁少选谁，再加上一个都不放的情况，答案为

$$min(n,d)+1$$

# 16. 球不可区分、盒子不可区分、不允许多球同盒、不允许空盒

就一种结果，$n=d$ 时成立，方案数为

$$1$$

# 容斥原理

$$|A_1 \cup \dots \cup A_n |=\sum\limits_{k=1}^{d}((-1)^{k+1}·\sum\limits_{1 \le i_1 < ... < i_k \le d} |A_{i1} \cap \dots \cap A_{ik}|)$$

对应到上方问题，即 $A_i$ 为第 $i$ 个盒子是空的，答案是求等式左边，最终答案即为等式右边

# 第二类斯特林数

$S_2(n,k)$ （其实是记作 $S(n,k)$，但为了两类斯特林数间做区分，此处添加了下标）表示将 $n$ 个两两不相同的元素，划分为 $k$ 个互不区分的非空子集的方案数
递推式如下

$$S(n, k)=S(n-1,k-1) + k·S(n-1,k)$$

边界是 $S(n,0) = 0,S(0,0)=1,S(0,k)=0$

参考 Oi-Wiki
利用组合意义证明，当插入一个新元素时，有两种方案

1. 将新元素单独放入一个子集，一共有 $S(n-1, k-1)$ 种方案
2. 将新元素放入现有的非空子集，一共有 $k·S(n-1,k)$ 种方案

故答案为两式相加

通项公式为

$$S(n,m)=\sum\limits_{i=0}^{m}\frac{(-1)^{m-i}·i^n}{i!(m-i)!}$$

# 不妨也介绍一下第一类斯特林数

$S_1(n,k)$ 表示将 $n$ 个两两不相同的元素，划分为 $k$ 个互不区分的非空轮换的方案数

一个轮换定义为首尾相接的一个环形排列，认为 $[A,B,C,D] = [B,C,D,A] = ...$
注意，不认为两个通过翻转得到的轮换等价，即 $[A,B,C,D] \neq [D, C, B, A]$

递推式如下

$$S_1(n, k)=S(n-1,k-1)+(n-1)·S_1(n-1,k)$$

边界为 $S_1(0,0)=1,S_1(n,0)=0,S_1(0,k),S_1(n,n)=1,S_1(n,1)=(n-1)!$

如何理解 $S_1(n, 1) = (n - 1)!$
$n$ 个数如果不考虑环的话，有 $n!$ 种排列，而一个长度为 $n$ 个环，有 $n$ 种表示方式，故答案为 $\frac{n!}{n}=(n-1)!$

利用组合意义证明，当插入一个新元素时，有两种方案

1. 将新元素单独放入一个新轮换，一共有 $S(n-1, k-1)$ 种方案
2. 将新元素放入现有的轮换，一共有 $(n-1)·S(n-1,k)$ 种方案（$n-1$ 代表在 $n-1$ 个缺口中插入，$S(n-1,k)$ 代表 $n-1$ 个元素形成 $k$ 个轮换的个数）

故答案为两式相加

第一类斯特林数不存在通项公式

# 分拆数

分拆：将自然数 $n$ 拆分为递降正整数和的表示

$$n = r_1+...+r_k,~r_1 \ge r_2\ge...\ge1$$

分拆数：$p_n$ 表示自然数 $n$ 的分拆方法数
自 $0$ 开始，自然数 $n$ 的分拆数如下表所示

$k$ 部分拆数：将 $n$ 拆分为 $k$ 个正整数的和，记为 $p(n, k)$ 其是下面方程的解数

$$n=(y_1+1)+...+(y_k+1), y_1 \ge ... \ge y_k \ge 0$$

两边均减 $k$ 有

$$n-k=y_1+...+y_k,~y_1 \ge ... \ge y_k \ge 0$$

如果方程里，$y_i$ 恰有 $j$ 个为 $0$，则

$$p(n,k)=\sum\limits_{j=0}^{k}p(n-k,j)$$

相邻两个和式作差有，其递归式为

$$p(n,k) = p(n-1,k-1)+p(n-k,k)$$

递归边界为

$$p(n, k) = \begin{cases} 1 & \text{如果 } n = 0 \text{ 且 } k = 0 \\ 0 & \text{如果 } k = 0 \text{ 且 } n > 0 \\ 0 & \text{如果 } n < k \\ 1 & \text{如果 } n = k \\ 1 & \text{如果 } k = 1 \text{ 且 } n \ge 1 \\ \end{cases}$$