luogu P5824 十二重计数法

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!1​i=0∑m​(−1)m−i(im​)in=i=0∑m​i!(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,j​x+⋯+fi,j​xi+⋯。
[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=1m​1−xj1​=exp(∑j=1m​−log(1−xj))=exp(∑j=1m​∑i​ixij​)。直接计算即可。

XI：球全部相同，盒子全部相同，每个盒子至多装一个球。
[n≤m][n \le m][n≤m]
XII：球全部相同，盒子全部相同，每个盒子至少装一个球。
将nnn变为n−mn-mn−m，每个盒子先装一个球，情况就变得与第101010条等价。