球盒问题

按照球是否相同,盒子是否相同,盒中可放球的数量的限制讨论12种常见情况。

球盒问题专题

nn 个球和 mm 个盒子,要全部装进盒子里。
还有一些限制条件,那么有多少种方法放球?(与放的先后顺序无关)

限制条件如下:

I\text{I}:球之间互不相同,盒子之间互不相同。
II\text{II}:球之间互不相同,盒子之间互不相同,每个盒子至多装一个球。
III\text{III}:球之间互不相同,盒子之间互不相同,每个盒子至少装一个球。

IV\text{IV}:球之间互不相同,盒子全部相同。
V\text{V}:球之间互不相同,盒子全部相同,每个盒子至多装一个球。
VI\text{VI}:球之间互不相同,盒子全部相同,每个盒子至少装一个球。

VII\text{VII}:球全部相同,盒子之间互不相同。
VIII\text{VIII}:球全部相同,盒子之间互不相同,每个盒子至多装一个球。
IX\text{IX}:球全部相同,盒子之间互不相同,每个盒子至少装一个球。

X\text{X}:球全部相同,盒子全部相同。
XI\text{XI}:球全部相同,盒子全部相同,每个盒子至多装一个球。
XII\text{XII}:球全部相同,盒子全部相同,每个盒子至少装一个球。

数据范围,1n,m2×1051\leq n,m\leq 2\times10^5

X

球全部相同,盒子全部相同。

T(n,m)T(n,m)为上述问题的结果,则T(n,m)=T(nm,m)+T(n,m1)T(n,m) = T(n - m, m) + T(n,m - 1),等号右边第一项表示的是T(n,m)T(n,m)中没有空盒子的方案的数量,T(n,m1)T(n, m - 1)表示T(n,m)T(n,m)中至少有一个空盒子的方案数量。这种思路是背包的思路。

容易发现,T(0,0)=1,T(n,0)=0(n>0)T(0,0) = 1,T(n,0) = 0(n > 0),由此可以进行递推计算。使用dp的话时间复杂度为O(nm)O(nm)。对于组合数学期末考试来说,这算是手算友好型算法了。

在算法竞赛中求这种情况的方案数,需要用生成函数(利用生成函数做背包问题,和容量无关)

利用XII\text{XII}T(nm,m)T(n - m, m)pnmp_n^m的关系,可以知道T(n,m)=pn+mmT(n, m) = p_{n + m}^m,然后利用pn+mm{p_{n + m}^m}的生成函数,可知T(n,m)T(n, m)就是

i=1m11xi\prod_{i = 1}^{m}\frac{1}{1 - x ^i}

xn+mx^{n + m}次方的项的系数,然后使用多项式乘法快速求出答案。

XI

每个盒子至多装一个球,盒子又一样,那么只要nmn\leq m,就有1种方案,如果n>mn > m,就没有方案了。

XII

球全部相同,盒子全部相同,每个盒子至少装一个球。

在组合数学中,有一个和这个问题类似的一个问题:将一个正整数拆分成多个正整数的无序和的方案数。这个问题叫做整数拆分问题。可以看出来,球全部相同对应着整数分拆时每个1都是相同的,盒子全部相同对应着无序和。

整数拆分问题有两个子问题:

  • 不限制拆分块数的方案计数pnp_n,又叫nn分拆数
  • 限制拆分块数的方案计数(比如nn拆分成恰好mm部分就是pnmp_n^m,易知i=1npni=pn\sum\limits_{i = 1}^np_n^i = p_n

本球盒问题要求必须分成mm个部分,且每个部分非空(至少一个),所以要求的是pnmp_n^m

可以看出,pnp_n就是关于aia_i的方程

i=1niai=n\sum_{i = 1}^nia_i = n

的所有非负整数解的个数。

下面考虑如何计算pnp_n。要想计算它,首先我们得学会计算pnmp_n^m

  • m>nm > n时,显然pnm=0p_n^m = 0

  • m=nm = n时,pnn=1p_n^n = 1

  • m=1m = 1时,pn1=1p_n^1 = 1

  • 1<m<n1 < m < n时,我们先考虑将nn个数分成mm个部分,可以有部分为0的方案数为T(n,m)T(n, m),这个问题计数比较简单,可以分两类对此计数:

    • 分成mm个非空的部分,则可以先给每个部分分配一个,然后再分配剩下的,所以为T(nm,m)T(n - m, m)(当然,nn不小于mm
    • 至少有一个空盒子,则可以去掉11个盒子,所以方案数为T(n,m1)T(n, m - 1)

    所以T(n,m)=T(nm,m)+T(n,m1)T(n,m) = T(n - m, m) + T(n, m - 1)

    容易发现,T(nm,m)=pnmT(n - m, m) = p_n^m ,所以pn+mm=T(n,m)p_{n + m}^{m} = T(n, m),考虑到T(n,1)=1T(n, 1) = 1T(0,0)=1T(0, 0) = 1T(n,0)=0(n>0)T(n, 0) = 0(n > 0) ,所以递推一下就能算出来结果。

    其实T(n,m)T(n, m)是可以用pnkp_n^k的形式表示出来的。考虑pn+mmp_{n+m}^m,其等于T(n,m)T(n,m)。由T(n,m)T(n,m)的定义可以知道,T(n,m)T(n,m)包含的方案中有无空盒,有一个空盒,有两个空盒....有m1m - 1个空盒的情况,他们其实就是pnm,pnm1...pn1p_n^{m}, p_n^{m - 1}...p_n^{1} 。把他们加起来就是T(n,m)T(n,m)了,也就是pn+mmp_{n + m}^{m},所以:

    pn+mm=i=1mpnip_{n + m}^m = \sum_{i = 1}^{m}p_n^{i}

    通俗来讲,求pnmp_n^m就是把dp三角形中的第nmn - m行的前mm个值相加。

    事实上,要严格证明T(n,m)T(n,m)pnmp_n^m的关系,需要建立二者之间的映射,证明这是一个双射,这里可以看组合数学书或者课件进行学习。

    这个计算方法也是手算友好型算法,时间复杂度也是O(nm)O(nm)

    要想快速计算出pnmp_n^m,还是要依托生成函数和FFT等科技。

    我们考虑数列{pn}\{p_n\}的生成函数:

    (1+x+x2+...)(1+x2+x4+...)...()...()=11x11x2...=i=111xi(1 + x + x^2 + ...)(1 + x^2 + x^4 + ...)...()...()\\ =\frac{1}{1 - x}\frac{1}{1 - x^2}...\\ =\prod_{i = 1}^{\infin}\frac{1}{1 - x ^i}

    这个函数的意义是:考虑所有的正整数1,2,....n....1,2,....n....,使用x,x2,x3...x,x^2,x^3...作为基项表征一个数的贡献。我们使用(1+xk+x2k+...)(1 + x^k + x^{2k} + ...)表示数kk可以出现0,1,2,....0,1,2,....次。将所有数的贡献乘起来,那么得到结果中xnx^n的系数,就是整数nn的拆分数,所以上式就是数列{pn}\{p_n\}的生成函数。

    再考虑pnmp_n^m的生成函数。根据共轭理论,nn拆分的最大部分为mm的拆分方案数,等于nn拆分成mm部分的方案数。这样就好说了,{pnm}\{p_n^m\}可以使用前一种解释进行计数:

    i=1m11xi\prod_{i = 1}^{m}\frac{1}{1 - x ^i}

    取其中的xnx^n项的系数,就是方案数了。要快速计算这个数需要使用高效的多项式乘法。