分拆数趣题一则

@duya 提供了这么一道题目：

\( n,k \) 是正整数，\( p \) 是 \( n \) 的一个分拆，\( a(p) \) 表示分拆 \( p \) 中 \( k \) 的个数，\( b(p) \) 表示分拆 \( p \) 中 \( k \) 的倍数的种类数，求证
$$ A=\sum_p a(p)=\sum_p b(p)=B $$其中求和号表示对 \( n \) 的全体可能的分拆求和

注：\( n \) 的一个分拆是指把 \( n \) 表示为若干个正整数的和， 不考虑顺序，可以重复

---

解法一：

这个解法来自渡鸦

从分析 \( A \) 开始，任取一个分拆 \( p \)，比如 $$ n=u+v+k+k+k $$它含有 \(3\ 个\ k \)

将它对应到三个拆分
$$\begin{split}
n&=u+v\\
n&=u+v+k\\
n&=u+v+k+k
\end{split}$$

这样，我们可以将一个含有 \( h \) 个 \( k \) 的拆分对应到 \( h \) 个拆分，我们只需要对这些拆分计数

根据我们的对应方法，有
$$ A=P(n-k)+P(n-2k)+P(n-3k)+\cdots $$其中 \( P(n) \) 表示 \( n \) 的全体分拆的个数

而 \( P(n-s\cdot k) \) 是含至少一个 \( s\cdot k \) 的分拆的数目
对于一个含 \( l \) 种 \( k \) 的倍数的分拆，它恰好被计数了 \( l \) 次
因此上式的右侧等于 \( B \)

证毕

---

解法二：

这个解法用到了生成函数，参见 渡鸦——生成函数趣题三则
或许我之后写一篇关于生成函数更多性质和技巧的文章(咕咕咕咕咕咕咕咕咕)

众所周知，\( P(n) \) ，也就是 \( n \) 的分拆数的生成函数是
$$ G=\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x^3}\cdots=\prod_{i=1}^\infty\frac{1}{1-x^i} $$

这是因为
$$ \frac{1}{1-x^i}=1+x^i+x^{2i}+x^{3i}+\cdots $$ 将这些项乘在一起时，每个单项来自从每个括号里面取出一项相乘，比如 \( x^u\cdot x^v\cdot x^{3k}=x^n \) 就代表了分拆 \( n=x+y+k+k+k \)
所以 \( G \) 中 \( x^n \) 的系数就是 \( n \) 的分拆个数 \( P(n) \)

因为这道题目和 \( n \) 的分拆有关，我们可以通过局部修改 \( G \) 来计算 \( A(n)\ 和\ B(n) \) 的生成函数，只要计算结果相同就可以证明结论

首先计算 \( A \)

将 \( G \) 中 \( \frac{1}{1-x^k} \) 一项替换为
$$ 0+1\cdot x^k+2\cdot x^{2k}+3\cdot x^{3k}+\cdots=\frac{x^k}{(1-x^k)^2} $$就得到 \( A(n) \) 的生成函数
$$ G_A=\frac{x^k}{1-x^k}\cdot G $$

然后是 \( B \)

为了给 \( k \) 的倍数的种类数计数，需要向生成函数中引入新变量 \( y \)

将 \( \frac{1}{1-x^{sk}} \) 替换为
$$ 1+yx^{sk}+yx^{2sk}+yx^{3sk}+\cdots=\frac{1+(y-1)x^{sk}}{1-x^{sk}} $$也就是说在一个单项中 \( y \) 的指数表示对应的分拆中 \( k \) 的倍数的种数

我们得到 $$ G’=G\cdot\prod_{s=1}^\infty(1+(y-1)^{sk}) $$

现在需要把 \( y \) 的指数变成系数，这只需要对 \( y \) 求偏导
然后再令 \( y=1 \) 就可以消除这个多余的变量

根据求导的乘法法则，我们有
$$\begin{split}
G_B&=\frac{\partial}{\partial y}G’|_{y=1}\\
&=G\cdot\frac{\partial}{\partial y}\prod_{s=1}^\infty(1+(y-1)^{sk}|_{y=1})\\
&=G\cdot (x^k+x^{2k}+x^{3k}+\cdots)\\
&=G_A
\end{split}$$

证毕