本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-22 14:56:11

组合数学

放球问题

规定 $n\geq m$

• $1$. $n$ 球 $m$ 盒均有区别，允许空盒

方案数 $m^n$

• $2$. $n$ 球有区别，$m$ 盒无区别，无空盒

设 $S_{n,m}$ 为答案，则 $S_{n,m}=S_{n-1,m-1}+m\times S_{n-1,m}$，$S_{n,m}=0(n<m),S_{1,1}=1$

$S$ 即为第二类斯特林数。

• $3$. $n$ 球有区别，$m$ 盒有区别，无空盒

把盒子排列，答案为 $S_{n,m}\times m!$

为第二类斯特林数的扩展。

• $4$. $n$ 球有区别，$m$ 盒无区别，允许空盒

答案为 $\sum_{i=1}^{m} S_{n,i}$，即为贝尔数。

• $5$. $n$ 球无区别，$m$ 盒有区别，插板法

$1$. 无空盒方案数 $C_{n-1}^{m-1}$，

$2$. 允许空盒方案数 $C_{n+m-1}^{m-1}$

• $6$. $n$ 球 $m$ 盒均无区别，推式子（DP）

设 $f_{n,m}$ 为无空盒，$g_{n,m}$ 为允许空盒。

则有 $f_{n,m}=g_{n-m,m}=\sum_{i=1}^mf_{n-m,i}=g_{n-m,m-1}+f_{n-m,m}$，

即 $f_{n,m}=f_{n-1,m-1}+f_{n-m,m}$（DP式子）

P5824 十二重计数法

• $I$ 对应 $1$，$m^n$
• $II$ $C_m^n\times n!(n\leq m)$；$0(n>m)$
• $III$ 对应 $3$，$S_{n,m}\times m!$
• $IV$ 对应 $4$，$\sum_{i=1}^{m} S_{n,i}$
• $V$ $1(n\leq m)$；$0(n>m)$
• $VI$ 对应 $2$，$S_{n,m}$
• $VII$ 对应 $5.2$，$C_{n+m-1}^{m-1}$
• $VIII$ $C_{m}^n$
• $IX$ 对应 $5.1$，$C_{n-1}^{m-1}$
• $X$ 对应 $6.g$，为 $g_{n,m}$
• $XI$ $1(n\leq m)$；$0(n>m)$
• $XII$ 对应 $6.f$，为 $f_{n,m}$