十二重计数法
十二重计数法
有 \(n\) 个球，\(m\) 个盒子。在如下限制条件下求出把球放进盒子的方案数：
\(\mathrm{I.}\) 球不同，盒不同，无其他限制。
\(\mathrm{II.}\) 球不同，盒不同，每盒至多放 \(1\) 个。
\(\mathrm{III.}\) 球不同，盒不同，每盒至少放 \(1\) 个。
\(\mathrm{IV.}\) 球不同，盒相同，无其他限制。
\(\mathrm{V.}\) 球不同，盒相同，每盒至多放 \(1\) 个。
\(\mathrm{VI.}\) 球不同，盒相同，每盒至少放 \(1\) 个。
\(\mathrm{VII.}\) 球相同，盒不同，无其他限制。
\(\mathrm{VIII.}\) 球相同，盒不同，每盒至多放 \(1\) 个。
\(\mathrm{IX.}\) 球相同，盒不同，每盒至少放 \(1\) 个。
\(\mathrm{X.}\) 球相同，盒相同，无其他限制。
\(\mathrm{XI.}\) 球相同，盒相同，每盒至多放 \(1\) 个。
\(\mathrm{XII.}\) 球相同，盒相同，每盒至少放 \(1\) 个。
我们考虑解决这些问题。
\(\mathrm{I.}\) 球不同，盒不同，无其他限制。
显然，每个球都能放进任意盒子里，于是方案数目为 \(m^n.\)
\(\mathrm{II.}\) 球不同，盒不同，每盒至多放 \(1\) 个。
依次考虑每个球挑一个盒放进去，之后，下一个球可以放的盒就少了一个。这个就是下降幂：\(m^{\underline n}.\)
或者相当于一个排列问题，那么答案显然为 \(A_m^n\)，等价于下降幂形式 \(m^{\underline n}.\)
\(\mathrm{III.}\) 球不同，盒不同，每盒至少放 \(1\) 个。
考虑容斥原理，在钦定有 \(i\) 个空盒之后转化为 \(\mathrm{I.}\)
那么有：\(\displaystyle \sum_{i = 0}^m (-1)^i \dbinom{m}{i} (m - i)^n.\)
或者考虑：当盒子相同时，转化为 \(\mathrm{VI.}\)，答案为第二类斯特林数：\(\displaystyle {n \brace m}.\)
那么我们这里盒子不同，需要乘上一个 \(m!\)，于是答案为 \(\displaystyle m! {n \brace m}.\)
由一个关于第二类斯特林数的组合恒等式：\(\displaystyle m! {n \brace m} = \sum_k \binom{m}{k} k^n (-1)^{m-k}.\)
就可以计算答案了。
\(\mathrm{IV.}\) 球不同，盒相同，无其他限制。
考虑有几个盒子非空。若有 \(i\) 个非空盒子，那么根据第二类斯特林数定义，答案为 \(\displaystyle {n \brace i}.\)
枚举所有的 \(i\)，那么就是对于第二类斯特林数按行求和：\(\displaystyle \sum_{i = 1}^n {n \brace i}.\)
\(\mathrm{V.}\) 球不同，盒相同，每盒至多放 \(1\) 个。
仔细想想，球放到哪个盒子都一样。考虑盒子能不能放下所有球即可。答案是 \([n \le m].\)
\(\mathrm{VI.}\) 球不同，盒相同，每盒至少放 \(1\) 个。
根据第二类斯特林数的定义，是 \(\displaystyle {n \brace m}.\)
\(\mathrm{VII.}\) 球相同，盒不同，无其他限制。
根据隔板法，答案显然为 \(\dbinom{n + m - 1}{m - 1}.\)
\(\mathrm{VIII.}\) 球相同，盒不同，每盒至多放 \(1\) 个。
根据组合数定义，有：\(\dbinom{m}{n}.\)
\(\mathrm{IX.}\) 球相同，盒不同，每盒至少放 \(1\) 个。
根据隔板法，答案显然为 \(\dbinom{n - 1}{m - 1}.\)
\(\mathrm{X.}\) 球相同，盒相同，无其他限制。
相当于把 \(n\) 划分为 \(m\) 个自然数的方法数目，也就是“划分数” \(P(n,m).\)
我们考虑对于划分数有一个经典的递推：\(P(i,j) = P(i - j, j) + P(i, j - 1).\)
也就是维护一个多重集，每次可以给所有 \(j\) 个数加一，或者加一个零到多重集。这样就可以对“划分数”进行计数。
\(\mathrm{XI.}\) 球相同，盒相同，每盒至多放 \(1\) 个。
这个和 \(\mathrm{V.}\) 是一样的，球放到哪个盒子都一样，答案为 \([n \le m].\)
\(\mathrm{XII.}\) 球相同，盒相同，每盒至少放 \(1\) 个。
考虑隔板法里面经典的“给每个盒子先放一个”，来把“无其他限制”转化为“至少放一个”。
我们这里也可以选用类似的方法，先给所有盒子各强制塞一个球进去，转化为“划分数”计数。
那么答案为 \(P(n - m, m).\)