组合数学-当小球遇上盒子（转

[orz原址](https://www.luogu.org/blog/chengni5673/dang-xiao-qiu-yu-shang-he-zi) （**转载自洛谷日报** 对其中对**斯特林数**的讲解进行了扩展） 以下： 小球和盒子是非常经典（烂大街）的一种模型，以小球和盒子的爱恨情仇为背景，对把小球放到这个盒子里还是那个盒子里进行的一系列哲学问题探讨以及珂学形态分析，其中基本会涉及到组合数学（雾）和计数DP（雾）。 其实这种问题应该有很多博客进行过讲解，可能会大同小异，我尽量说的稍微详细一点，并补充一些其他内容。 文章有部分借鉴于其他大佬的博客和学长的题解，但主要内容都是我自己写的 可能会有一些错误，还请指出 作者很菜，本文可能过于基础，仅供萌新学习巩固，大佬愉悦身心 特别感谢 @ComeIntoPower 对本文的宝贵意见 前置技能 **组合数公式** （这东西应该大家都会吧）$C_{n}^{m}=\frac{n!}{(n-m)!m!}$ 也可以使用**递推式**(杨辉三角) $C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}$ 从$n$个不同的数中取$m$个，第$n$个数如果取的话有$C_{n-1}^{m-1}$种取法，如果不取则有$C_{n-1}^{m}$中取法 ```cpp C[1][0]=C[1][1]=1; for (register int i=2;i<N;i++){ C[i][0]=1; for (register int j=1;j<N;j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]); } ``` ~~组合数裸题（逃）~~[组合数问题](https://www.luogu.org/problemnew/show/P2822) **插板法** (隔板法?) (插空法?)：主要运用于组合数学中，是排列组合的推广，主要用于解决不相邻组合与追加排列的问题。 就是在 $n$物品之间插上 $m$板，将其分为$m+1$组。  用组合数可以轻松求出答案。 **捆绑法**：在解决对于某几个元素要求相邻的问题时，先整体考虑，将相邻元素视作一个大元素进行排序，然后再考虑大元素内部各元素间顺序的解题策略就是捆绑法． 感觉有点类似于物理的整体法与隔离法？ 例子：有8本不同的书；其中数学书3本，外语书2本，其它学科书3本．若将这些书排成一列放在书架上，求数学书和外语书都放在一起的方案数 把3本数学书“捆绑”在一起看成一个整体，2本外语书也“捆绑”在一起看成一个整体，与其它3本书一起看作5个元素，然后就可以求了 **容斥原理**：在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理 也就是我们小学学过的数学问题：一个班级里有a个人会打篮球，有b个人会踢足球，有c个人既会打篮球又会踢足球，询问这个班里会打篮球或会踢足球的有多少人？ ans=a+b−c 化成式子为$A∪B=A+B-A∩B$以此类推 (奇数个集合为正 偶数个集合为负） 接下来我们回到正题，默认问题为$n$个小球放到 $m$盒子里，题型共有三项要求，球是否相同，盒子是否相同，能否有空盒。 **1.球相同，盒子不同，不能有空盒** 我们经过一波巧妙地的分析之后，发现这个问题的实质就是把$n$个小球分为$m$组（不能空），然后就这么转化成了一个组合数问题 $ans=C_{n-1}^{m-1}$ 其实这就是一个插板法，就是在 n 个小球的 n-1 个空隙当中刚好插入 m-1 个板子，即恰好分为不为空的 m 组。 因为盒子不相同，所以$(1,2)$ 和$(2,1)$是不同的。 **2.球相同，盒子不同，可以有空盒** 对于每个盒子，我们都给他一个球，那么上一个问题就和这问题一样了，所以我们可以看做自己有 n+m 个小球，然后我们在排列完之后在每一组都删去一个小球，这样就能枚举出有空盒的情况了。于是答案为 $ans=C_{n+m-1}^{m-1}$ **3.球不同，盒子不同，可以有空盒** 对于每一个球，你都可以放到 1~m 的任意一个位置,由于球不同，所以球与球之间是独立的。因为每个球有 m 种情况，所以我们得出 $ans=m^{n}$ 4.球不同，盒子相同，不能有空盒 对于这个问题有一种神奇的东西叫做第二类斯特林数（不是加特林） 在数学领域，斯特林数分为第一类斯特林数和第二类斯特林数，我们在这里只说第二种 第二类斯特林数（简称为S2）的定义为将n个物体划分成k个非空的没有区别的集合的方法数，大致就是把 n 个不同的小球放入m个相同的盒子中（且盒子不能为空）的方案数。递推公式为 $S2[i][j]=S2[i-1][j]*j+S2[i-1][j-1]$ ($S2[i][j]$表示前$i$个小球放到前$j$个盒子里的方案数） 我们可以这样理解：对于一个$S2[i][j]$，你接下来要再放一个小球，你可以放到前jj个盒子里，方案数为$j*S2[i][j]$ ，也可以放到下一个盒子里，方案数为$S2[i][j+1]S2[i][j+1]$ 于是我们就可以得出上面的递推公式了，代码如下： 然后呢 我的解释是这样的 对于第i个小球 i可以单独构成一个非空集合，此时前$i-1$ 个物品构成$j-1$个非空的 不可辨别的集合，方法数为$S(i-1,j-1)$； 也可以前$i-1$种物品构成$j$个非空的不可辨别的集合， 第i个物品放入任意一个中，这样有$j*S2(i-1,j)$ 种方法。 ```cpp int n=read(),m=read(); S2[0][1]=1; for(int i=0;i<=n;i++){ for(int j=1;j<=i;j++){ S2[i][j]=(S2[i-1][j]*j+S2[i-1][j-1]); } } cout<<S2[n][m]<<endl; ``` 这个公式是 $n^{2}$的 ，斯特林数还有一个公式 $S2(n,m)=\frac{1}{m!}*\sum_{k=0}^{m}(-1)^{k}(_{k}^{m})*(m-k)^{n}$ 如果集合没有非空的限制，方法有$n^{m}$种 我们枚举为空的盒子，可得出$(_{k}^{m})*(m-k)^{n}$这部分是多出来的 但可能会重复，我们需要套一个容斥即 $(-1)^{k}$ 最后除一个$m!$消掉有序性，如果不除就是有序的 据说可以用FFT（快速傅里叶变换）加速，但是我太菜了不会，于是不提  **第一类斯特林数** 1.定理 第一类斯特林数$1(n,m)$表示的是将$n$个不同元素构成 m 个圆排列的数目。 2.递推式 设人被标上$1,2,.....p$，则将这$p$个人排成$m$个圆有两种情况： ①第一种排法是在一个圆圈里只有标号为$p$的人自己，排法有$S1(n-1,m-1)$个。 ②第二种排法中，$p$至少和另一个人在一个圆圈里。这些排法可以通过把$1,2....n-1$排成$m$个圆圈再把$n$放在$1,2....n-1$任何一人的左边得到，因此第二种类型的排法共有$(n-1)*S1(n-1,m)$种排法。 我们所做的就是把${1,2,...,p}$划分到k个非空且不可区分的盒子，然后将每个盒子中的元素排成一个循环排列。 综上，可得出第一类Stirling数定理： 边界条件： $S1(n,m)=1 n>=0$//有n个人和n个圆圈，每个圆圈就只有一个人 $S1(n,0)=0 n>=1$//如果至少有1个人，那么任何的安排都至少包含一个圆圈 **5.球不同，盒子也不同，不能有空盒** 事实上这种情况与上面唯一的不同就是有序性，我们只需要在那个公式里不除$m!$即在第二类斯特林数上乘上一个$m!$ 就可以了。 $ans=m!S2[n][m]$ **6.球不同，盒子相同，可以有空盒** 因为可以有空盒，我们可以枚举每次一共用了几个盒子，然后把相应的第二类斯特林数加起来就可以了 $ans=\sum_{i=1}^{m}S2[n][i]$ 似乎这种数的名字叫做贝尔数 Bell数的定义：第$n$个Bell数表示集合${1,2,3,...,n}$的划分方案数 看起来是不是和第二类斯特林数有点像。 可以说贝尔数就是其对应的第二类斯特林数之和。 贝尔数的相应公式为$ B_{n+1}=\sum_{k=0}^{n}$ ，即枚举包含最后一个元素的集合大小 也可以通过对应的第二类斯特林数求和得到，公式如下 $B_n=\sum_{k=1}^nS2(n,k)$ **7.球相同，盒子相同，可以有空盒** 设 $f[n][m]$为 $n$个球放到$m$个盒子里的方案数 如果只有一个盘子或者没有小球，方案数自然为$1$ 如果小球比盒子要少，小球肯定是放不满盒子的，由于盒子相同，可以得到转移$ f[i][j]=f[i][i]$ 如果小球比盒子要多，就分为将盘子放满和没放满两种情况，即$f[i][j]=f[i-j][j]+f[i][j-1]$ 总结上面三种情况就可以得出转移方程了，代码如下 ```cpp int n=read(),m=read(); for(int i=0;i<=n;i++){ for(int j=1;j<=m;j++){ if(j==1 || i==0) f[i][j]=1; else if(i<j) f[i][j]=f[i][i]; else if(i>=j) f[i][j]=f[i-j][j]+f[i][j-1]; } } printf("%d\n",f[n][m]); ``` 实际上这个问题等价于自然数拆分问题，按管理大大的说法可以用五边形数解决，但是我太菜了不会五边形数。[五边形数](https://baike.baidu.com/item/%E4%BA%94%E8%BE%B9%E5%BD%A2%E6%95%B0/9459853?fr=aladdin) 8.球相同，盒子相同，不能有空盒 有点类似于第一、二种情况之间的关系。 我们先假设在每一个盒子里都放上了一个球，就跟上面的情况一样了。 $ans=f[n-m][m]$ 以上应该是盒子小球最基础的八种情况了， 例题1[盒子与球](https://www.luogu.org/problemnew/show/P1287)，这道题就是前面的一种情况的裸题。 例题2[放苹果](https://www.luogu.org/problemnew/show/P2386)，又一道 例题3[数的划分](https://www.luogu.org/problemnew/show/P1025)，又一道 这几道题都不是很难，用 dfs 也可以过，但还是建议打个DP理解一下