十六种盒子放球问题的集合

大概是组合计数问题的基础，因此稍微写一下。

或者说，尝试复习，发现自己都不会了，所以应该写一下。

约定

这一类问题都可以在问题确定是，用两个参数 (n,r) 来描述。其中 (n) 表示球数， (r) 表示盒数。

为了方便描述，以下用一串二进制码表示问题的状态。例如 0101 ：

1. 第一位表示球是否相同。 0 表示相同， 1 表示不同；
2. 第二位表示盒是否相同。 0 表示相同， 1 表示不同；
3. 第三位表示球可否不放。 0 表示不可， 1 表示可以；
4. 第四位表示盒可否为空。 0 表示不可， 1 表示可以；

因此状态 0101 就表示：球相同，盒不同，球不可不放，盒可以为空，此时的方案数。

另外，由于有些问题是笔者自己 yy 的，因此正确性存疑，该类问题用 * 标注。如果发现该部分有问题，请及时留言。

11--

球不同、盒不同问题求解的基本途径是乘法原理。

1101

对于每一个球，它都有 (r) 种选择。由于每个球不同，因此它们的选择相互独立，可以直接乘起来。

因此可以得到总方案数为 (r^n) ，求解的时间复杂度是 (O(log_2n)) 。

1100

此时盒子不可以为空，但是直接乘法原理我们会得到盒子为空的方案。

注意乘法原理求到的是 " 至少有 0 个盒子为空 " 的方案数。因此不难想到用容斥原理计算。枚举一下空盒子的数量，就可以方案数是：

[sum_{i=0}^r(-1)^iinom{r}{i}(r-i)^n ]

求解的时间复杂度是 (O(rlog_2n)) 。

在 (r) 比较小的情况下，可以 (O(r)) 预处理自然数幂，然后求式子，时间复杂度是 (O(r)) 。

还可以发现，如果用指数型生成函数描述这个式子，我们可以在 (O(rlog_2r)) 的时间批量求出不同的 (r) 的解。

你会在之后再见到它的。

1110

这个时候，每个球就多了一个 " 不放 " 的选择。因此每个球有 (r+1) 种选择。总方案数是 ((r+1)^n) 。

1111

继续容斥：

[sum_{i=0}^r (-1)^iinom{r}{i}(r+1-i)^n ]

01--

球相同、盒不同问题求解的基本原理是隔板法。

0101

想象 (n) 个球排成一列。此时由于盒子是有区别的，因此我们可以将球分成 (r) 组，然后第一组放进第一个盒子里，第二组放进第二盒......第 (r) 组放进第 (r) 盒。因此我们就考虑计算将 (n) 个球分成 (r) 组的方案数。

显然这是隔板法的问题。 (n) 个球有 (n-1) 个缝，从 (n-1) 个缝中选出 (r-1) 个来插板的方案数是 (inom{n-1}{r-1}) 。

0100

盒子可以为空，因此直接放板子不太对头。经典的思想是：

我们给每个盒子先放一个 " 假球 " ，这样总共有 (n+r) 个球，并且每个盒子至少有一个球（包括 " 假球 " ）。现在再进行隔板法就没有问题了，方案就是 (inom{n+r-1}{r-1}) 。

0110*

由于球本身没有区别，因此有球没放就相当于球的数量变少了。于是就可以直接枚举球的数量：

[egin{aligned} &sum_{i=1}^ninom{i-1}{r-1}\ =&sum_{i=1}^nfrac{(i-1)^{underline{r-1}}}{(r-1)!}\ =&frac{1}{(r-1)!}sum_{i=0}^{n-1}i^{underline{r-1}}\ =&frac{1}{(r-1)!}sum olimits_0^{n}x^{underline{r-1}}delta x\ =&frac{1}{(r-1)!}frac{n^{underline{r}}}{r}\ =&inom{n}{r} end{aligned} ]

这个组合含义也比较显然。我们同样可以假想一个盒子，用来装 " 没放 " 的球。由于最后这个盒子可以为空，因此总共有 (n) 个缝， (r) 个板。

注意，盒子不能为空，因此这里不考虑不放球的情况。

0111*

同理易得：

[egin{aligned} &sum_{i=0}^n inom{i+r-1}{r-1}\ =&sum_{i=0}^nfrac{(i+r-1)^{underline{r-1}}}{(r-1)!}\ =&frac{1}{(r-1)!}sum_{i=0}^{n}(i+r-1)^{underline{r-1}}\ =&frac{1}{(r-1)!}sum olimits_{r-1}^{n+r}x^{underline{r-1}}delta x\ =&frac{1}{(r-1)!}frac{(n+r)^{underline{r}}-(r-1)^{underline{r}}}{r}\ =&inom{n+r}{r} end{aligned} ]

组合意义请自行思考。

注意，盒子可以为空，因此这里需要考虑球都不放的情况。

10--

球不同、盒相同问题求解的基本途径是第二类斯特林数。

1000

此时直接推导难度比较大，因此我们考虑使用 DP 。

(f(i,j)) ：有 (i) 个球， (j) 个盒子，且球不同，盒相同时，球必须放，盒不能空的放球的方案数。

考虑转移：

[f(i,j)= egin{cases} 1&i=0,j=0\ 0&i<j\ 0&i>0,j=0\ f(i-1,j-1)+jf(i-1,j)&otherwise end{cases} ]

最后一个转移是在讨论，在放最后一个球时，是否要新拿盒子。如果新拿一个，就是 (f(i-1,j-1)) 。如果不新拿，就从前 (j) 个盒子中挑一个放进去。

如果你有所了解，你就会发现，这是第二类斯特林数的递归式。这里我们记 ({nrace r}=f(n,r)) 。

因此这个问题的答案是 (nrace r) 。

另一种推导方式 是，考虑容斥。我们先给盒子标号，然后枚举空盒子的数量，最后把标号除掉：

[{nrace r}=frac{1}{r!}sum_{k=0}^r(-1)^kinom{r}{k} (r-k)^n ]

可以发现，后面的容斥式实际就是 1100 的解。因此 1100 的解也可以表述为 (r!{nrace r}) 。

另外，根据这个容斥式也可以使用 NTT 在 (O(nlog_2n)) 的时间内求出 ({nrace 0},{nrace 1},dots,{nrace k}) 。

补充内容：

斯特林数原本用于描述阶乘幂和幂之间的系数关系。第一类斯特林数 (egin{bmatrix}n\kend{bmatrix}) 用于描述 (x^{underline{n}}) 展开中 (x^k) 的系数，第二类 (nrace k) 用于描述 (x^n) 展开中 (x^{underline{k}}) 的系数。以此，幂和阶乘幂就可以很方便地进行转换。
因此可以得到关系式：

[ x^{underline{n}}=sum_{k=0}^negin{bmatrix}n\kend{bmatrix} x^k\ x^n=sum_{k=0}^n{nrace k} x^{underline k} ]

当然，两种数都有其对应的组合含义。

1001

不难想到，可以直接枚举有球的盒子的数量：

[sum_{i=0}^r {nrace i} ]

补充说明：

当 (r=n) 的时候，问题就变成了，对于大小为 (n) 的集合 (S) ，将它划分成任意多个非空子集的方案数是多少？
专门有一个数列 ({b_n}) 来描述它。这类数就叫 " 贝尔数 " 。
简单推导（考虑第 (n) 个元素所在集合大小）可以得出贝尔数的转移：

[egin{aligned} b_n&= egin{cases} 1&n=0\ sum_{k=1}^{n} inom{n-1}{k-1}b_{n-k}& otherwise end{cases}\ b_n&=sum_{k=0}^n{nrace k} end{aligned} ]

可以定义 (B(x)) 为贝尔数的指数型生成函数，那么就有 (B(x)=e^{e^x-1}) 。具体推导可以参考 洛谷日报 等资料。

1010*

同样可以枚举球的数量：

[sum_{k=0}^n inom{n}{k}{krace r} ]

你发现这个式子仍然可以使用 NTT 批量计算。甚至此情况的答案可以直接写成生成函数形式。

1011*

同样可以枚举球和空盒子的数量：

[sum_{j=0}^ninom{n}{j}sum_{k=0}^r {jrace k} ]

00--

球相同、盒相同问题求解的基本原理是动态规划。

0001

不难发现，此时我们可以直接用每个盒子的球数组成的序列来描述一种方案。

那么我们只枚举单调不减的序列就好了，也就是说，原问题的等价于求自然数序列的数量：

[egin{cases} sum_{i=1}^r a_i=n\ forall 1<ile r, a_{i-1}le a_i end{cases} ]

这里有一个很常见的转化：枚举单调不降序列，就相当于枚举全是 1 的后缀的和。
具体来说，我们可以定义

[s_i={underbrace{0 0 dots 0}_{i-1个0} overbrace{1 1 dots 1}^{n-i+1个1}} ]

那么一个单调不降的序列就必然可以拆分成多个 (s) 的对应位的和。比如 (n=4) 时， ({1 2 3 3}=s_1+s_2+s_3) 。

于是不难想到一个完全背包：

(g(i,j))：在考虑完 (s_1sim s_j) 后，所有后缀的和为 (i) 的方案数。

可以得到转移为：

[g(i,j)= egin{cases} 1&i=0\ 0&i>0,j=0\ g(i-j,j)+g(i-1,j)&othewise end{cases} ]

此时的答案就是 (g(n,r)) 。

0000

此时盒子不能为空，我们可以直接给每个盒子分配一个球。当 (n<r) 时，答案是 (0) 。当 (nge r) 时，答案就是 (g(n-r,r)) 。

0011*

球没有区别，因此可以直接枚举数量：

[sum_{k=0}^n g(k,r) ]

0010*

基本同上：

[sum_{k=r}^n g(k-r,r) ]

总结

盒子放球问题虽然模型简单，但是你可以发现，在 16 种问题中，我们用了 4 种主要的思路：乘法原理、隔板法、斯特林数、动态规划，以及一些常见的技巧，比如容斥。每种主要思路下， 4 个子问题的方法不尽相同。不同主要思路下，处理子问题的限制的方法各自有些相似。

所以说，深入学习盒子放球，对于学习计数是比较有意义的。它的确可以帮助你熟悉一些基础的计数方法。