文档章节

关于几类放球问题的总结

o
 osc_wws45aot
发布于 2019/08/20 19:31
字数 3345
阅读 5
收藏 0

总览: 球入盒问题

  1. 无->无  (1) 放苹果问题;  (2) 不降序列计数问题;  (3) 要求无一空盒的拓展;
  2. 无->有  (1) 不定方程非负整数解;  (2) 可重组合;  (3) 要求无一空盒的拓展;
  3. 有->无  (1) 集合无序划分;  (2) 第二类斯特林数(要求无一空盒);  (3) bell数;  (4) 斯特林数求和;
  4. 有->有  (1) 集合有序划分、可重排列; $S(n,m)=m^n$  (2) 结论(1)的两种证明方法(代数证明,生成函数证明);  (3) 盒子可以为空:第二类斯特林数*排列系数再求和;  (4) 要求无一空盒:无标号盒子方案数*m! = 有标号盒子方案数;  (5) 盒子中的球有顺序的拓展;

放球问题,指的是这样一类问题:给你n个球和m个盒子,球和盒子可以有标号也可以没有标号,问将这n个球放入这m个盒子有多少种不同方案?默认情况下允许存在空盒,但有的类型会要求无一空盒,下面我们会讨论到。

我们把把n个有/无标号的球放入m个有/无标号的盒子中的问题记作 n有/无->m有/无 ,例如,n有->m无 表示将n个有标号的球放入m个无标号的盒子的问题,其方案数记为F(n,m),在此基础上,要求无一空盒的方案数记为F'(n,m)。

##第一类:n无->m无

也即把整数n拆分成m个无序非负整数的和的方案数

这是经典的放苹果问题,有递推式F(n,m)=F(n,m-1)+F(n-m,m),相当于讨论是否存在空的盘子,如果有则方案数为F(n,m-1),没有则为F(n-m,m)。 这个问题也等价于求有多少个不降的非负整数序列${a_m}$,使得$\sum_{i=1}^{m}a_i=n$,可以设一个略微复杂的dp方程:设f[i][j][k]为序列前i个数的总和为j,且第i个数为k的方案数,有转移方程:$$f[i][j][k]=\sum_{l=0}^{k} f[i-1][j-k][l]$$ 但是发现这样dp实在太傻了,因为如果我们像上面放苹果那样设f[i][j]为长度为i且总和为j的不降序列方案数的话,就只需要讨论序列第一个数是是不是0就可以了,如果是0,就可以从f[i-1][j]转移过来,如果不是0,就可以考虑将序列每一个数减去一个1,就可以从放f[i][j-i]转移过来了。于是我们得到一个简单得多的式子: $$f[i][j]=f[i-1][j]+f[i][j-i]$$ 和上面的放苹果问题一模一样。 Update: 这个问题也等价于一个完全背包问题,其中物品的体积分别为0~n,要求从中选择m个物品,恰好填满大小为n的背包的方案数。

若在此基础上要求无一空盒,因为每个盒子中的球数都>0,所以可以考虑将每一个盒子中的球数减1,就变成了允许空盒的情况,设不允许空盒的方案数为F'(n,m),则有F'(n,m)=F(n-m,m)。

##第二类:n无->m有

即求满足$\sum_{i=1}^{m}a_i=n$的非负整数序列${a_m}$的数量,是经典的不定方程非负整数解问题,用可重组合数直接求出方案数为$F(n,m)=\overline{C}{n+1}^{m-1}=C{n+m-1}^{m-1}$

从另一个角度考虑,F(n,m)也可以看作是从m个数中不计顺序的取n个数,允许重复的方案数,即从m个数中取n个数的可重组合数$\overline{C}m^n$,又因为将n个数放入m个盒子中可以看作是将这n数分成m分,又可以转化为将m-1个板子插到这n个数之间,也即将m-1个板子和n个数交叉混合,问题就变成了给定(n+m-1)个位置,从中选出n个位置放数字,其他位置放板子的方案数,方案数就等于$C{n+m-1}^{n}$,这就证明了$\overline{C}m^n=C{n+m-1}^{n}$,同时也证明了$F(n,m)=C_{n+m-1}^{n}$

至于要求无一空盒的方案数,可以用类似于第一类问题的方法处理。

##第三类:n有->m无

这相当于一个n元集合的m无序划分数(允许划分出来的集合为空)。 一看到这个就想到了第二类斯特林数,第二类斯特林数S(n,m)指的是将n个有标号的球放入m个无标号的盒子中,要求无一空盒的方案数,接下来的讨论中会经常用到它,要详细了解第二类斯特林数的话可以参考gzy学长的总结,这里只简单写一个它的递推公式: $$S(n,m)=S(n-1,m-1)+mS(n-1,m)$$ 其中$S(0,0)=1,S(0,i)=0(i>0),S(i,0)=0(i>0)$,这个式子的意思是考虑第一个球是否单独占一个盒子,若单独一个盒子,那么剩下n-1个球就可以放入剩下m-1个盒子里,方案数S(n-1,m-1),若和其他球在同一个盒子里,就可以先让剩下n-1个球放入m个盒子里,再把第一个球放入m个盒子中的任意一个,方案数mS(n-1,m),两种情况加起来就得到了这个递推式。

让我们再考虑另一种特殊情况,即没有限定多少个盒子,也就是这n个球可以放入任意多个盒子中,可以发现这种情况等价于有n个盒子(n个球最多占用n个盒子),且允许盒子为空,这时的方案数就是F(n,n),且它等于Bell(n),其中Bell数为集合划分数,它和第二类斯特林数之间有公式$Bell(n)=\sum_{i=0}^n S(n,i)$,这很好理解,就是枚举非空盒的数量,然后累加即可。

于是我们可以得出F(n,m)的计算式了: $$F(n,m)=\sum_{i=0}^m S(n,i)$$ 和上面一样,枚举非空盒的数量即可。

要求无一空盒的方案数就是S(n,m)

##第四类:n有->m有

这相当于一个n元集合的m有序划分数,容易发现这n个球之间是相互独立的,且每个球可以放入m个盒子中的任意一个,所以方案数$F(n,m)=m^n$

这东西用组合意义很好证明,但是我在用代数证明时却发生了一些很有趣的事。 首先我们用代数式子来表示这个东西,我们可以先枚举一个序列${a_m}$表示每个盒子中球的数量,再将n个球按照这个数量填入盒子中,就像这样: $$F(n,m)=\sum_{a_1+a_2...+a_m=n}C_{n}^{a_1}C_{n-a_1}^{a_2}...C_{n-a_1-a_2...-a_{m-1}}^{a_m}$$ 化一下式子得到 $$\sum_{a_1+a_2...+a_m=n}\frac{n!}{a_1!a_2!...a_m!}$$ 也即 $$n!\sum_{a_1=0}^{n}\frac{1}{a_1!}\sum_{a_2=0}^{n-a_1}\frac{1}{a_2!}...\sum_{a_{m-1}=0}^{n-a_1-a_2...-a_{m-2}}\frac{1}{a_{m-1}!}\frac{1}{(n-a_1-a_2...-a_{m-1})!}$$ 设 $$G(n,m)=\sum_{a_1=0}^{n}\frac{1}{a_1!}\sum_{a_2=0}^{n-a_1}\frac{1}{a_2!}...\sum_{a_{m-1}=0}^{n-a_1-a_2...-a_{m-2}}\frac{1}{a_{m-1}!}\frac{1}{(n-a_1-a_2...-a_{m-1})!}$$ 可以得出递推式 $$G(n,m)=\sum_{i=0}^{n}\frac{1}{i!}G(n-i,m-1)$$ 其中$G(n,1)=\frac{1}{n!}$ 接下来让我们归纳证明$G(n,m)=\frac{m^n}{n!}$ 当m=1时,$G(n,1)=\frac{1}{n!}=\frac{1^n}{n!}$,显然成立。 假设m < k时命题成立,试证m=k时,$\forall n$,命题也成立: $$G(n,m)=\sum_{i=0}^{n}\frac{1}{i!}G(n-i,m-1)$$ $$=\sum_{i=0}^{n}\frac{1}{i!}\frac{(m-1)^{n-i}}{(n-i)!}$$ $$=\frac{1}{n!}\sum_{i=0}^{n}C_{n}^{i}1^i(m-1)^{n-i}$$ $$=\frac{1}{n!}m^n=\frac{m^n}{n!}$$ 命题得证。 所以$G(n,m)=\frac{m^n}{n!}$,那么$F(n,m)=n!*G(n,m)=m^n$

一旁的神仙Itst看我证的那么辛苦,当即给了我一个简单的生成函数证法: 考虑$G(n,m)=\sum_{a_1+a_2...+a_m=n}\frac{1}{a_1!a_2!...a_m!}$的生成函数,容易发现$G(n,m)$就等于$(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...)^m$的第${x^n}$项系数,而$(1+\frac{x}{1!}+\frac{x^2}{2!}+...)=e^x$,所以$(1+\frac{x}{1!}+\frac{x^2}{2!}+...)^m=e^{mx}$,展开后就是$1+\frac{m}{1!}x+\frac{m^2}{2!}x^2+\frac{m^3}{3!}x^3...$,第$x^n$项系数就是$\frac{m^n}{n!}$,所以$F(n,m)=m^n$

这就证完了。。。(被虐爆了

另一方面,我们同样可以用第二类斯特林数计算F(n,m),同样枚举非空盒的数量,然后对于有i个非空盒的情况,要乘以一个排列系数$P_m^i$,即要将i个划分出来的无序集按顺序填入m个盒子中,所以可以得到 $$F(n,m)=\sum_{i=0}^{m}P_m^iS(n,i)$$ 又$F(n,m)=m^n$ 所以$$\sum_{i=0}^{m}P_m^iS(n,i)=m^n$$ 这东西可以用来求第二类斯特林数通项公式,这里暂不深究。

如果要保证无一空盒怎么办?直接$F'(n,m)=m!*S(n,m)$即可(就是将所有无序划分做一个全排列就得到了所有有序划分)

还有一个这类问题的变种:将n个有标号的球放入m个有标号的盒子里,允许有空盒,且盒子里的球是有顺序的,即将n个球划分到m个盒子里后还可以将每个盒子里的球按任意顺序排列,例如2个球2个盒子就有${}{1,2},{}{2,1},{1,2}{},{2,1}{},{1}{2},{2}{1}$这六种方案,求这样的方案数$F_1(n,m)$。

根据组合意义,我们可以一个一个球依次考虑,第一个球有m个位置可以放,第二个有(m+1)个位置(除了可以放在m个盒子的末尾,还可以放在第一个球的前面),第三个可以放在第一、第二个的前面,有(m+2)个位置可以放......以此类推,第i个球有(m+i-1)个位置可以放,于是有: $$F_1(n,m)=m*(m+1)...*(m+n-1)=m^{\overline{n}}$$

这个式子也可以用上面证$F(n,m)=m^n$的代数方法类似地证明

      Update: 发现上面写的东西好无聊啊,这里补充一点有意思的:

例1 求将整数n划分为若干个无序正整数和的方案数。n<=1e5

这个问题可以从两方面来思考:

  1. 设$f[i][j]$为将j划分为1~i中的若干个数的和的方案数,那么这就是一个背包问题,转移方程$f[i][j]=f[i-1][j]+f[i][j-i]$
  2. 设$f[i][j]$为将i划分为恰好j个数的方案数,这就是一个放苹果问题,考虑方案中有没有1出现,有方程$f[i][j]=f[i-1][j-1]+f[i-j][j]$

但是这两种dp都是$n^2$级别的,怎么优化这个复杂度呢?

我们可以使用分块技巧来解决 ,我们先用第一种dp算出将n划分为$1 ~ \sqrt n$中的若干个数的方案,再用第二种dp算出将n划分为$\sqrt n+1 ~ n$中的若干个数的方案,因为最多能划分出$\sqrt n$个大于$\sqrt n$ 的数,所以第二种dp 的复杂度是$O(n\sqrt n)$的,最后对两种dp的结果进行卷积合并即可,总复杂度$O(n\sqrt n)$。

当然第二种dp的转移方程也要有所变化,具体的,设$t=\sqrt n$,那么有$f[i][j]=f[i-t-1][j-1]+f[i-j][j]$。

例2 求将n个有标号的求放入m个有标号的盒子中,且每个盒子中的球的数量不超过k个的方案数。

设$f[i][j]$为将i个球放入j个盒子中,且每个盒子不超过k个的方案数,通过巧妙的容斥得到$f[i][j]=jf[i-1][j]-jC_{i-1}^kf[i-k-1][j-1]$

乍一看好像是$O(nm)$的,但是仔细一看有用的状态数其实并不满,比如当j=m时,有用的i的范围为1~n ,而当j=m-1时,有用的i的范围就只有1~n-k-1了,以此类推,这是一个等差数列,根据等差数列求和公式可以得到总的有用状态数为$O( n*\lfloor\frac{n}{k}\rfloor)$ ,通过记忆化搜索就可以达到$O(\frac{n^2}{k})$的复杂度,有的时候题目会隐含$\lfloor\frac{n}{k}\rfloor$的范围较小的条件,这时这个算法的复杂度就比较低了。

其实这个问题是从这道题里来的。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

ftp-ftps-sftp的关系

Ftp FTP 是File Transfer Protocol(文件传输协议)的英文简称,而中文简称为“文传协议”。用于Internet上的控制文件的双向传输。同时,它也是一个应用程序(Application)。基于不同的操作...

独钓渔
39分钟前
12
0
使Vim将所有空格显示为字符 - Make Vim show ALL white spaces as a character

问题: I can't find a way to make Vim show all white spaces as a character. 我找不到让Vim将所有空白显示为字符的方法。 All I found was about tabs, trailing spaces etc. 我发现的只......

富含淀粉
50分钟前
23
0
RN 接入高德地图遇到的一些问题

react-native-amap-geolocation、react-native-amap3d 1、iOS Geolocation.getCurrentPosition 获取坐标后,没有返回 address 信息? 逆地理编码 Android 默认返回逆地理编码,而 iOS 需要手...

Jack088
52分钟前
14
0
如何正确清理Excel互操作对象? - How do I properly clean up Excel interop objects?

问题: I'm using the Excel interop in C# ( ApplicationClass ) and have placed the following code in my finally clause: 我在C#( ApplicationClass )中使用Excel互操作,并将以下代......

javail
今天
10
0
java版Spring Cloud Spring Boot b2b2c 直播带货 短视频带货 分销 小程序 电子商务 分布式 微服务

海哇 B2B2C多租户电子商务平台(自营+多商家入驻+分销分佣+直播带货+短视频带货) 管理平台+商家平台+消费端微服务+消费端小程序 使用技术 Spring Cloud、Spring Boot、Mybatis、小程序、Vue...

SpringCloud关注者
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部