# 放球问题及排列相关

组合数学

https://www.zybuluo.com/scrolllock/note/1304942

八种基本放球问题

1球相同,盒相同,可以为空

• 等价于整数拆分
• 性质: 将$N$拆分乘不超过$M$个数的方案数,等同于拆分成最大不超过$M$的方案数

将整数$N$分解为不超过$M$个整数的方案数:

设$dp[i][j]$为$i$分为$j$个数(带0)的方案

• 先规定选出的数非严格递增
• 可以发现最后的序列是一些后缀区间$+k*1$得到的
• 于是所有的状态可以从一些子状态整体+1或不变转移, 这样不会破坏非严格递增的性质

即:

• 子状态增加一个0(空盒), $dp[i][j-1]$
• 子状态整体$+1$, $dp[i-j][j]$

$dp[i][j]=dp[i][j-1]+dp[i-j][j]$
$ans = dp[N][M]$

将整数$N$分解为不超过$M$的方案数:

类似

分类讨论:

• 当前状态没有$j$, $dp[i][j-1]$
• 当前状态由子状态增加$1$个$j$得到, $dp[i-j][j]$

$dp[i][j]=dp[i][j-1]+dp[i-j][j]$
$ans=dp[N][M]$
发现和上一个问题相同

如果求分成不超过$M$且不重复的方案数,则稍作修改:
$dp[i][j]=dp[i][j-1]+dp[i-j][j-1]$

另一种简单的思想

设$dp[i][j]$为将

2球相同,盒相同,不可以为空

与前一种情况类似, 且更加简单

• 思路相同, 由于不可以为空, 不能从子状态加一个空盒转移
• 根据性质, 可以用子状态加一个单独的$1$(最小单位)转移

即:

• 子状态加一个单独$1$, $dp[i-1][j-1]$
• 子状态整体$+1$, $dp[i-j][j]$

$dp[i][j]=dp[i-1][j-1]+dp[i-j][j]$
$ans=dp[N][M]$
同样, 球同盒同可以为空也可用$\sum_{i=1}^{M}dp[N][i]$计算

3球不同,盒不同,可以为空

对于每一个球, 都有$N$个盒子任意选择
$ans=M^N$

4球不同,盒相同,不可以为空

考虑递推, 设$dp[i][j]$为前$i$个球放入前$j$个盒子的方案数
对于当前的球$i$:

• 可以并入子状态的任意一个盒子中, $j*dp[i-1][j]$
• 可以自己新开一个盒子, $dp[i-1][j-1]$

$dp[i][j]=j*dp[i-1][j]+dp[i-1][j-1]$
$ans=dp[N][M]$

5球不同,盒不同,不可以为空

将球不同盒不同不空全排即可
$ans=dp[N][M]*M!$

6球不同,盒相同,可以为空

对第4种情况求和
$ans=\sum_{i=1}^{M}dp[N][i]$

7球相同,盒不同,不可以为空

组合数

在$N$个球中插入$M-1$个隔板,即$C_{N-1}^{M-1}$

递推

$dp[i][j]$代表前$i$个球放入前$j$个盒子的方案数
则当前处理第$i$个球时有两种策略:

• 将$i$放入当前盒子$j$中,$dp[i-1][j]$

• $j$为新开的盒,$dp[i-1][j-1]$

8球相同,盒不同,可以为空

组合数计算

可以转化为不空,将球数量增加$M$个,在每个盒子中先放一个
在进行插板, 即$C_{n+m-1}^{m-1}$(最后在拿掉原先的$M$个)

递推+组合数

或者$DP$推,先推出不空的$DP$,$ans=sigma(DP[n][j]*C_m^{m-j})$,比较烦

总结

放球问题
​ -> 3
​ -> 2
​ -> 1
​ -> 4
​ -> 5
​ -> 6
​ -> 7
​ -> 8
​ -> 重复组合

错位排列

考虑递推, 设$f[i]$为前$i$个数的错排方案数:

• 由于第$i$个数不能放在自己的位置上, 只能放在$[1,i-1]$的某个位置$j$上
• 那么原先$j$上的数要重新选择位置
• 由于$j$本身是无限制的, 可以随便放, 但是$[1,i-1]$中的其他数不能随便放

所以不能单纯由$f[i-1]$(即剩下$i-1$个错排)转移过来, 需要分类讨论:

• 位置$j$上的数放在$i$上, 现在剩下$(i-2)$个数都有限制, $(i-1)*f[i-2]$

• 位置$j$上的数不放在$i$上, 相当于给$j$加了一个限制, 现在$(i-1)$个数有限制, $(i-1)*f[i-1]$

$f[i]=(i-1)*(f[i-1]+f[i-2])$

圆排列

两种思路:

• 固定一个点, 剩下的全排列, $(n-1)!$
• 先全排列, 因为在圆上, 转一圈都相同, $n!/n$

重复排列

有$k$种物品, 每一种有$a[i]$个, 总共$N$个,求排列的方案数

即全排列的方案数, 除以每一种内部排列的方案数

$N!/(\prod_{i=1}^{k}a[i]!)$

重复组合

$n$种不同的球, 每种球无限个, 从中选$k$个的方案数

等价于将$k$次选择(相同)分配到$n$种球上

即$k$个球放到$n$个不同的盒子, 可以为空的情况

$C_{k-1+n}^{n-1}$