【学习记录】组合数学

KSCD_ · 2024-02-22 14:56:11 · 个人记录

组合数学

放球问题

规定 n\geq m

方案数 m^n

设 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

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

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

设 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}