咕咕咕
这期注释比正文还长。
【算法漫笔006】浅谈盒子与球
这篇写了很久，主要原因是我比较懒这篇太长太难写了。
注释最多的一集。写的最长的一集。
盒子与球
盒子与球主要是一种排列组合，其问题形式为：将 nnn 个球放入 mmm 个盒子中，根据球是否相同[1]、盒子是否相同、盒子中至少一个球/至多一个球/无限制的放球，组合成不同的计数问题。我们来一个个解析这些问题。
为了方便，我们将每个问题编码，第一位表示球相同（111）/不同（000），第二位表示盒子相同（111）/不同（000）。第三位表示盒子中无限制的放球（AAA）/至少一个球（BBB）/至多一个球（CCC）。
如果你对排列组合不太熟悉，以下的内容请配合注释理解。
00A
即球不同，盒子不同，无限制。
此时每个球都是独立的，可以放入任何一个盒子当中。根据乘法原理[2]，此时总方案数为：
mnm^n mn
00B
即球不同，盒子不同，每个盒子至少放一个球。
此时我们可以先将 nnn 个球分成 mmm 个非空的无序集合，显然方案数为 S(n,m)S(n,m)S(n,m)[3]。此时我们已经将 nnn 个不同的球分成了 mmm 个非空的无序集合，但题目要求盒子是不同的，所以我们还需要把这 mmm 个集合分配给 mmm 个不同的盒子。这相当于对 mmm 个集合进行全排列[4]，方案数为 m!m!m!。再次根据乘法原理得到：
S(n,m)×m!S(n,m) \times m! S(n,m)×m!
特别的，当 n<mn<mn<m 时，我们无法保证每个盒子至少放一个球，故方案数为 000。
00C
即球不同，盒子不同，每个盒子至多放一个球。
因为每个盒子最多只能放一个球，所以先从 mmm 个盒子中选出 nnn 个来放球，方案数为(mn)\binom{m}{n}(nm )[5]。然后将 nnn 个不同的球与选出的 nnn 个不同盒子一一对应（即全排列[4:1]），方案数为 n!n!n!。根据乘法原理[2:1]，总方案数为：
(mn)×n!=m!(m−n)!\binom{m}{n} \times n!=\frac{m!}{(m-n)!} (nm )×n!=(m−n)!m!
特别的，当 n>mn>mn>m 时，我们无法保证每个盒子至多放一个球，故方案数为 000。
01A
即球不同，盒子相同，无限制。
此时盒子不可区分，但球仍可区分。我们需要将 nnn 个不同的球分成不超过 mmm 个非空[6]无序集合。
此时我们可以枚举非空盒子的数量 kkk，其中 kkk 从 111 到 min(m,n)\min(m,n)min(m,n)，对于每个 kkk，方案数为第二类斯特林数 S(n,k)S(n,k)S(n,k)[3:1]。根据加法原理[7]，总方案数为：
∑k=1min(n,m)S(n,k)\sum_{k=1}^{\min(n,m)} S(n,k) k=1∑min(n,m) S(n,k)
特别的，当 n=0n=0n=0 时，方案数为 111（全空盒）；当 m=0m=0m=0 时，若 n=0n=0n=0 则方案数为 111，否则为 000。
01B
即球不同，盒子相同，每个盒子至少放一个球。
根据 S(n,m)S(n,m)S(n,m)[3:2]的定义，答案为：
S(n,m)S(n,m) S(n,m)
特别的，当 n<mn<mn<m 时，我们无法保证每个盒子至少放一个球，故方案数为 000。
01C
即球不同，盒子相同，每个盒子至多放一个球。
因为盒子相同，且每个盒子最多放一个球，所以实际上只有两种可能，即盒子能够放下和无法全部放下，即：
{1n≤m0n>m\begin{cases} 1&n\le m\\ 0&n>m \end{cases} {10 n≤mn>m
10A
即球相同，盒子不同，无限制。
此时球完全相同，但盒子可区分。也就是将 nnn 个无区别的球放入 mmm 个有编号的盒子，允许空盒。使用隔板法[8]解决，答案为：
(n+m−1m−1)\binom{n+m-1}{m-1} (m−1n+m−1 )
特别的，当 n=0n=0n=0 时，方案数为 111（全空盒）；当 m=0m=0m=0 时，若 n=0n=0n=0 则方案数为 111，否则为 000。
10B
即球相同，盒子不同，每个盒子至少放一个球。
依然使用隔板法[8:1]。先想象：给每个盒子放 111 个球，此时这些盒子都欠我 111 个球。剩下 n−mn-mn−m 个球，问题转化为将 n−mn-mn−m 个相同球放入 mmm 个不同盒子（允许空盒），即 10A 的情形。因此方案数为：
((n−m)+m−1m−1)=(n−1m−1)\binom{(n-m)+m-1}{m-1}=\binom{n-1}{m-1} (m−1(n−m)+m−1 )=(m−1n−1 )
特别的，当 n<mn<mn<m 时，我们无法保证每个盒子至少放一个球，故方案数为 000。
10C
即球相同，盒子不同，每个盒子至多放一个球。
因为球相同且每个盒子最多一个，所以实际上就是从 mmm 个不同的盒子中选出 nnn 个来放球（每个盒子恰好一个球）。符合组合数[5:1]的定义，答案为：
(mn)\binom{m}{n} (nm )
特别的，当 n>mn>mn>m 时，我们无法保证每个盒子至多放一个球，故方案数为 000。
11A
即球相同，盒子相同，无限制。
此时球完全相同，盒子也完全相同。问题转化为：将整数 nnn 拆分为至多 mmm 个正整数之和[9]。我们定义 dp 表示 n,mn,mn,m 的整数拆分数[10]，则答案为：
dpm,ndp_{m,n} dpm,n
特别的，当 n=0n=0n=0 时，方案数为 111（全空盒）；当 m=0m=0m=0 时，若 n=0n=0n=0 则方案数为 111，否则为 000。
11B
即球相同，盒子相同，每个盒子至少放一个球。
依然先让每个盒子欠债一颗球，剩下 n−mn-mn−m 个球。问题转化为将 n−mn-mn−m 个相同球放入 mmm 个相同盒子（允许空盒），即 11A 的情形。因此方案数为：
dpm,n−mdp_{m,n-m} dpm,n−m
特别的，当 n<mn<mn<m 时，我们无法保证每个盒子至少放一个球，故方案数为 000。
11C
即球相同，盒子相同，每个盒子至多放一个球。
因为球相同且盒子相同，每个盒子最多一个球，所以实际只有两种可能，若盒子够用为 111，不够用为 000。
{1n≤m0n>m\begin{cases} 1&n\le m\\ 0&n>m \end{cases} {10 n≤mn>m
题目
总的来看还是有一定的套路的，我自己认为我写的还比较好懂。
洛谷P5824 十二重计数法
诶诶怎么是黑题？诶诶怎么要用 FFTFFTFFT！前面的区域以后再来探索吧。
洛谷T188453 十二重计数法【弱化版】
还是弱化版更适合我们！我们来写一下这个青题吧！
还不算很难！
题外话
好想写 DP 但是不知道怎么写，DP 这个东西太多变了，没有完整的流程，所以还是单开一个专题比较好，算法漫笔的第六篇还是写盒子与球吧。总之就是我还是写数论了
注释&致谢
感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 相同：在盒子与球模型里，相同和不同指的是物体本身是否可区分，例如，在球不同的情况下，将两个盒子中分别放入一个球，是一种方案，而将两个盒子中的球调换则是另一种方案。而在球相同的情况下，我们视以上两种方案为一种。 ↩︎
2. 乘法原理：即如果完成一件事需要 nnn 个步骤，第 iii 个步骤有 aia_iai 种不同的方法，且这些步骤互不影响，那么完成这件事总共有 a1×a2×⋯×ana_1 \times a_2 \times \dots \times a_na1 ×a2 ×⋯×an 种方法。 ↩︎ ↩︎ ↩︎ ↩︎
3. S(n,m)S(n,m)S(n,m)：S(n,m)S(n,m)S(n,m) 为第二类斯特林数，S(n,m)S(n,m)S(n,m) 表示将 nnn 个不同元素划分为 mmm 个非空无序集合的方案数，满足递推：S(n,m)=S(n−1,m−1)+m×S(n−1,m)。S(n,m)=S(n-1,m-1)+m \times S(n-1,m)。S(n,m)=S(n−1,m−1)+m×S(n−1,m)。其中：S(n,1)=S(n,n)=1S(n,1)=S(n,n)=1S(n,1)=S(n,n)=1公式的推导也很简单：考虑第 nnn 个元素，其有两种情况：
自己单独作为一个非空集合：那么剩余的 n−1n-1n−1 个元素就要划分成 mmm 个非空集合，根据定义方案数为：S(n−1,m−1)S(n-1,m-1)S(n−1,m−1)加入已有集合：先将前 n−1n-1n−1 个元素划分成 mmm 个非空集合，根据定义方案数为 S(n−1,m)S(n-1,m)S(n−1,m)。然后第 nnn 个元素可以放入这 mmm 个集合中的任意一个，有 mmm 种选择。根据乘法原理[2:2]得到：m×S(n−1,m)m \times
S(n-1,m)m×S(n−1,m)最后根据加法原理[7:1]得到递推公式：S(n,m)=S(n−1,m−1)+m×S(n−1,m)。S(n,m)=S(n-1,m-1)+m \times S(n-1,m)。S(n,m)=S(n−1,m−1)+m×S(n−1,m)。
边界情况也很好理解，S(n,1)=1S(n,1)=1S(n,1)=1（全部元素只能放在一个集合里），S(n,n)=1S(n,n)=1S(n,n)=1（每个元素各自成一组）。 ↩︎ ↩︎ ↩︎
4. 全排列：即把 mmm 个不同的元素按任意顺序排成一列，方案数为 m!m!m!。其定义是：从 mmm 个不同元素中取出 mmm 个，按顺序排列，共有 m×(m−1)×⋯×1=m!m \times(m-1)\times\dots\times 1=m!m×(m−1)×⋯×1=m! 种方法。 ↩︎ ↩︎
5. 组合数：(mn)\binom{m}{n}(nm ) 表示组合数，即从 mmm 个不同元素中选出 nnn 个的方案数，计算公式为 m!n!(m−n)!\frac{m!}{n!(m-n)!}n!(m−n)!m! 。公式的推导为：先从 mmm 个元素中选 nnn 个按顺序排列（排列数[11] m!(m−n)!\frac {m!} {(m−n)!}(m−n)!m! ），但组合不考虑顺序，而 nnn 个元素的内部顺序有 n!n!n! 种，因此需要除以 n!n!n!，即：m!n!(m−n)!\frac{m!}{n!(m-n)!}n!(m−n)!m! ↩︎ ↩︎
6. 非空：因为空盒在盒子相同时没有区别。 ↩︎
7. 加法原理：即在两种情况互不重叠时，总可能数就是两种情况的可能数相加。 ↩︎ ↩︎
8. 隔板法：即将问题转化为在多个球中插入隔板，计算隔板的排列。此时由于两个隔板不可能重合，所以可以保证每个集合非空。 ↩︎ ↩︎
9. 问题转化：因为盒子相同，空盒没有区别，所以只需关注非空盒子的个数。 ↩︎
10. 整数拆分数：这里定义的整数拆分数 dpm,ndp_{m,n}dpm,n ，表示将正整数 nnn 拆分为至多 mmm 个正整数之和的方案数。可以依靠递推公式 dpm,n=dpm−1,n+dpm,n−mdp_{m,n}=dp_{m-1,n}+dp_{m,n-m}dpm,n =dpm−1,n +dpm,n−m 。很好理解的递推公式此处不再解释。其中 dpm ,0=1dp_{m ,0}=1dpm ,0 =1，当 n<0n<0n<0 时 dpm,n=0dp_{m,n}=0dpm,n =0。 ↩︎
11. 排列数：即从 mmm 个不同元素中取出 nnn 个，按顺序排成一列，方案数为 m!(m−n)!\frac{m!}{(m-n)!}(m−n)!m! 。它与组合数的区别在于：排列考虑顺序，组合不考虑顺序。第一个位置有 mmm 种选择，第二个位置有 m−1m-1m−1 种选择，……，第 nnn 个位置有 m−n+1m-n+1m−n+1 种选择，根据乘法原理[2:3]，总方案数为 m×(m−1)×⋯×(m−n+1)=m!(m−n)!m \times(m-1) \times \dots \times
(m-n+1)=\frac{m!}{(m-n)!}m×(m−1)×⋯×(m−n+1)=(m−n)!m! 。 ↩︎
