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)insum_{i=0}^m(-1)^{m-i}inom{m}{i}i^ni=0∑m(−1)m−i(im)in
IV：球之间互不相同，盒子全部相同。
直接写成第二类斯特林数求和的形式，枚举非空盒子数，答案为∑i=1m{ni}sum_{i=1}^megin{Bmatrix}n\iend{Bmatrix}i=1∑m{ni}
第二类斯特林数{nm}egin{Bmatrix}n\mend{Bmatrix}{nm}满足mn=∑i=0m{ni}i!(mi)m^n=sum_{i=0}^megin{Bmatrix}n\iend{Bmatrix}i!inom{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)!egin{Bmatrix}n\mend{Bmatrix}=frac{1}{m!}sum_{i=0}^m(-1)^{m-i}inom{m}{i}i^n = sum_{i=0}^mfrac{(-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}egin{Bmatrix}n\mend{Bmatrix}{nm}
VII：球全部相同，盒子之间互不相同。
(n+m−1m−1)inom{n +m -1}{m - 1}(m−1n+m−1)
VIII：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
(mn)inom{m}{n}(nm)
IX：球全部相同，盒子之间互不相同，每个盒子至少装一个球。
(n−1m−1)inom{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}^mfrac{1}{1 - x^j} = exp(sum_{j = 1}^m-log(1-x^j)) = exp(sum_{j=1}^msum_ifrac{x^{ij}}{i}Fi(x)=∏j=1m1−xj1=exp(∑j=1m−log(1−xj))=exp(∑j=1m∑iixij)。直接计算即可。
XI：球全部相同，盒子全部相同，每个盒子至多装一个球。
[n≤m][n le m][n≤m]
XII：球全部相同，盒子全部相同，每个盒子至少装一个球。
将nnn变为n−mn-mn−m，每个盒子先装一个球，情况就变得与第101010条等价。