十二重计数法 Revisit

最近感觉做计数的时候脑子不太清醒，有时候无脑拍生成函数把脑子弄坏了。故重新回归一下最普通的是否区分的球盒计数。

“$n$ 个球放入 $m$ 个盒子”的问题，根据球和盒子是否带标号区分，我将其分为四个类：序列类（球盒都有标号），划分类（球标号，盒不标号），定和序列计数类（球不标号，盒标号），分拆类（球盒都不标号）。

序列类

球不同，盒不同。

任意装

等价于为每个球设置一个盒子的编号，因此其数量与长度为 $n$，元素从 $[m]$ 中选取的序列数一一对应。即 $m^n$。

每个盒子至多一个球

等价于为每个球设置一个盒子的编号，且编号不重，因此其数量与长度为 $n$，元素从 $[m]$ 中选取，且没有重复元素的序列数一一对应。即 $m^{\underline{n}}$。

每个盒子至少一个球

等价于为每个球设置一个盒子的编号，且编号不重，因此其数量与长度为 $n$，元素从 $[m]$ 中选取，且值域中每个数都出现过。

一般可以容斥去描述这个“必须出现”，钦定 $i$ 个元素不出现值域就被缩到等价 $[m-i]$，因此答案是 ${\sum }_{i=0}^m(-1{)}^i(\genfrac{}{}{0ex}{}{m}{i})(m-i{)}^n=\left\{\genfrac{}{}{0ex}{}{n}{m}\right\}m!$

划分类

球不同，盒相同

每个盒子至少一个球

我们不关心每个球被放到了哪些盒子里，只关心它和那些球在一起。

根据第二类斯特林数的定义，答案是 $\left\{\genfrac{}{}{0ex}{}{n}{m}\right\}$。

第二类斯特林数有递推 $\left\{\genfrac{}{}{0ex}{}{n}{m}\right\}=\left\{\genfrac{}{}{0ex}{}{n-1}{m-1}\right\}+m\left\{\genfrac{}{}{0ex}{}{n-1}{m}\right\}$，表示最后一个球是单独成盒还是放入之前的某个盒。

同样的，根据序列计数的“至少一个球”与这个问题的等价形式，我们可以得到第二类斯特林数的通项公式 $\left\{\genfrac{}{}{0ex}{}{n}{m}\right\}=\frac{1}{m!}{\sum }_{i=0}^m(-1{)}^{m-i}(\genfrac{}{}{0ex}{}{m}{i})i^n$

任意装

枚举装了几个盒子，答案就是斯特林数的行和 ${\sum }_{i=0}^n\left\{\genfrac{}{}{0ex}{}{n}{i}\right\}=Bell(n)$。

每个盒子至多一个球

注意到需要学会识别这种春竹问题。每个球都独自呆在盒子里，所有方案等价，答案即 $[n\le m]$

定和序列计数类

球相同，盒不同。

只关心每个盒子里球的个数。

等价于对序列 $x_1\dots x_m$ 计数，满足 $\sum x_i=n$

每个盒子至少一个球

组合意义，排一列球，每个盒子选一段球，最后一个球一定是最后一个盒子的结尾球，前面 $n-1$ 个球要选出 $m-1$ 个盒子的结尾球。

$\left(\genfrac{}{}{0ex}{}{n-1}{m-1}\right)$

任意装

组合意义，插板，等价于前一个问题再给 $m$ 个球的版本。因此 $\left(\genfrac{}{}{0ex}{}{n+m-1}{m-1}\right)$。

另一种解释是插 $m-1$ 个板子进去把球分成 $m$ 段，因此是 $n+m-1$ 个位置选 $m-1$ 个板。

每个盒子至多一个球

等价于长 $n$ 的 01 序列，和为 $m$，即 $\left(\genfrac{}{}{0ex}{}{m}{n}\right)$

分拆类

球相同，盒相同

只关心“盒子中球的数量”构成的可重集，即把一个数拆成一个可重集的数的和。

任意装

$P(n,m)$ 为将 $n$ 拆为 $m$ 个无序自然数的和的方案数。

直接想不重不漏地生成这个东西的方式可能会是去 dp 一个递增的序列，但是这样强制要求之后的数更大，状态数较难接受，因此常见的方法就是使用 Ferrers 图像，我们不尝试从左到右生成这个，而是从上到下垫高。

$p(n,m)=p(n-m,m)+p(n,m-1)$

分别表示，新开一个 $0$ 加入集合，或是对所有数加 $1$。

如果想要快速求这个可以用生成函数，令 $m$ 拆分的生成函数为（关于被拆分数 $n$） $F_m(x)={\sum }_{i=0}^{n}p(i,m)x^i$

根据组合和符号化推导有 $F_m(x)=F_{m-1}(x)\ast (1+x^m+x^{2m}+\dots )$

$F_m(x)=F_{m-1}(x)\ast SEQ(x^m)={\prod }_{i=1}^{m}SEQ(x^i)$。

然后直接把所有 $SEQ(x^i)$ log 令加起来再 exp 回去就行。

每个盒子至多一个球

堂食问题，答案要么是0要么是1

每个盒子至少一个球

同任意装，正整数分拆，答案为 $P(n-m,m)$。