高二上数学期末压轴题
Published:
题目
$n$ 个小球放入 $m$ 个盒子。求以下五种情况分别的方案数：
- 小球不同，盒子不同，盒子不空「III」
- 小球不同，盒子不同，盒子可空「I」
- 小球不同，盒子相同，盒子不空「VI」
- 小球不同，盒子相同，盒子可空「IV」
- 小球相同，盒子不同，盒子可空「VII」
求出 $n=5, m=3$ 的答案。
符号
组合数
\[\binom n m = \frac {n!} {m! (n-m)!}\]第二类 Stirling 数
我们把第三小题「小球不同，盒子相同，盒子不空」的答案称为第二类 Stirling 数 (Stirling number of the second kind)，记作
\[n \brace m\]具体计算公式留给第三小题。
解法
按难度从小到大排序。
第二小题「I」
「小球不同，盒子不同，盒子可空」
小球的选择是互相独立的，每个小球有 $m$ 个盒子可选，选 $n$ 次。答案为
\[\boxed{ m^n }\]答案为 $\boxed{243}$。
第五小题「VII」
「小球相同，盒子不同，盒子可空」
等价于在 $n$ 个小球之间插入 $m-1$ 个隔板。答案为
\[\boxed{ \binom {n+m-1} n }\]答案为 $\boxed{21}$。
第一小题「III」
本题为难度分水岭。
「小球不同，盒子不同，盒子不空」
这题和第三小题的区别仅仅在于区分了盒子，因此这一题的答案就是第三小题的答案乘上 $m!$。答案为
\[\boxed{ m! {n \brace m} }\]接下来具体计算。
Solution 1：容斥原理
钦定 $i$ 个盒子必须空，剩下盒子随便。对于剩下的 $m-i$ 个盒子就是第二小题，答案为 $(m-i)^n$。
答案为「钦定 $0$ 个空盒」减「钦定 $1$ 个空盒」加「钦定 $2$ 个空盒」……：
\[\boxed{ \sum_{i=0}^m (-1)^i \binom m i (m-i)^n }\]Solution 2：二项式反演
选择 $i$ 个盒子必须放，剩下 $m-i$ 个盒子必须空。枚举所有的选法将方案数求和，得到的就是第二小题：
\[m^n = \sum_{i=0}^m \binom m i i! {n \brace i}\]作二项式反演：
\[\boxed{ m! {n \brace m} = \sum_{i=0}^m (-1)^i \binom m i (m-i)^n }\]答案为 $\boxed{150}$。
第三小题「VI」
「小球不同，盒子相同，盒子不空」
根据第二类 Stirling 数的定义，答案为：
\[\boxed{ n \brace m }\]即第一小题的答案除以 $m!$：
\[\boxed{ \frac 1 {m!} \sum_{i=0}^m (-1)^i \binom m i (m-i)^n }\]答案为 $\boxed{25}$。
第四小题「IV」
「小球不同，盒子相同，盒子可空」
枚举非空盒子的个数 $i$，化为第三小题答案为 $n \brace i$。因此总答案为：
\[\boxed{ \sum_{i=1}^m {n \brace i} }\]答案为 $\boxed{41}$。
根据生成函数的知识还可以得到一个理论上计算量更小的答案，但是考场上不实用：
\[\boxed{ \sum_{k=0}^m \frac {k^n} {k!} \sum_{i=0}^{m-k} \frac {(-1)^i} {i!} }\]