WanderOvO

WanderOvO's blog.

首页 归档 标签 关于

球盒问题

2021-10-16 9 min read # 数学

按照球是否相同，盒子是否相同，盒中可放球的数量的限制讨论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}：球全部相同，盒子全部相同，每个盒子至少装一个球。

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

X

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

设T(n,m)T(n,m)为上述问题的结果，则T(n,m)=T(n−m,m)+T(n,m−1)T(n,m) = T(n - m, m) + T(n,m - 1)，等号右边第一项表示的是T(n,m)T(n,m)中没有空盒子的方案的数量，T(n,m−1)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(n−m,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=1m11−xi\prod_{i = 1}^{m}\frac{1}{1 - x ^i}

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

XI

每个盒子至多装一个球，盒子又一样，那么只要n≤mn\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(n−m,m)T(n - m, m)（当然，nn不小于mm）
    • 至少有一个空盒子，则可以去掉11个盒子，所以方案数为T(n,m−1)T(n, m - 1)。

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

    容易发现，T(n−m,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) = 1，T(0,0)=1T(0, 0) = 1，T(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)包含的方案中有无空盒，有一个空盒，有两个空盒....有m−1m - 1个空盒的情况，他们其实就是pnm,pnm−1...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三角形中的第n−mn - 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+...)...()...()=11−x11−x2...=∏i=1∞11−xi(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=1m11−xi\prod_{i = 1}^{m}\frac{1}{1 - x ^i}

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

Powered by Gridea RSS