当前位置：首页 > news >正文

luogu P5824 十二重计数法

news 2026/7/8 21:12:26

luogu P5824 十二重计数法

有nnn个球和mmm个盒子，球要全部装进盒子里，计数。

I：球之间互不相同，盒子之间互不相同。
nmn^mnm
II：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
∏i=1n(m+1−i)\prod_{i=1}^n(m+1-i)i=1∏n(m+1−i)
III：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。
∑i=0m(−1)m−i(mi)in\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^ni=0∑m(−1)m−i(im)in
IV：球之间互不相同，盒子全部相同。
直接写成第二类斯特林数求和的形式，枚举非空盒子数，答案为∑i=1m{ni}\sum_{i=1}^m\begin{Bmatrix}n\\i\end{Bmatrix}i=1∑m{ni}
第二类斯特林数{nm}\begin{Bmatrix}n\\m\end{Bmatrix}{nm}满足mn=∑i=0m{ni}i!(mi)m^n=\sum_{i=0}^m\begin{Bmatrix}n\\i\end{Bmatrix}i!\binom{m}{i}mn=i=0∑m{ni}i!(im)
（mmm个集合中任选的方案数等于其中挑iii个非空的，剩余全空的方案数）
即{nm}=1m!∑i=0m(−1)m−i(mi)in=∑i=0m(−1)m−iini!(m−i)!\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n = \sum_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}{nm}=m!1i=0∑m(−1)m−i(im)in=i=0∑mi!(m−i)!(−1)m−iin

V：球之间互不相同，盒子全部相同，每个盒子至多装一个球。
[n≤m][n \le m][n≤m]
VI：球之间互不相同，盒子全部相同，每个盒子至少装一个球。
{nm}\begin{Bmatrix}n\\m\end{Bmatrix}{nm}
VII：球全部相同，盒子之间互不相同。
(n+m−1m−1)\binom{n +m -1}{m - 1}(m−1n+m−1)
VIII：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
(mn)\binom{m}{n}(nm)
IX：球全部相同，盒子之间互不相同，每个盒子至少装一个球。
(n−1m−1)\binom{n - 1}{m - 1}(m−1n−1)
X：球全部相同，盒子全部相同。
拆分数：把nnn拆成mmm个数的和的方案。
fi,j=fi,j−1+fi−j,jf_{i, j} = f_{i, j - 1} + f_{i - j, j}fi,j=fi,j−1+fi−j,j。
构造生成函数Fj(x)=f0,j+f1,jx+⋯+fi,jxi+⋯F_j(x) = f_{0, j} +f_{1, j}x + \cdots + f_{i, j} x^i + \cdotsFj(x)=f0,j+f1,jx+⋯+fi,jxi+⋯。
[xi]Fj(x)=[xi−j]Fj(x)+[xi]Fj−1(x)[x^i]F_j(x) = [x^{i-j}]F_j(x) + [x^i]F_{j-1}(x)[xi]Fj(x)=[xi−j]Fj(x)+[xi]Fj−1(x)。
Fj(x)=Fj−1(x)+xjFj(x)F_j(x) = F_{j-1}(x) +x^jF_j(x)Fj(x)=Fj−1(x)+xjFj(x)，即Fj(x)=Fj−1(x)1−xjF_j(x) = \frac{F_{j-1}(x)}{1-x^j}Fj(x)=1−xjFj−1(x)。
F0(x)=1F_0(x) = 1F0(x)=1代入得Fi(x)=∏j=1m11−xj=exp⁡(∑j=1m−log⁡(1−xj))=exp⁡(∑j=1m∑ixijiF_i(x) = \prod_{j=1}^m\frac{1}{1 - x^j} = \exp(\sum_{j = 1}^m-\log(1-x^j)) = \exp(\sum_{j=1}^m\sum_i\frac{x^{ij}}{i}Fi(x)=∏j=1m1−xj1=exp(∑j=1m−log(1−xj))=exp(∑j=1m∑iixij)。直接计算即可。