来自讨论组：将 101, 202, 303 拆成四个不等的正整数，求方法数之和

kuing

生如夏花 2025-3-14 23:37
母函数法还熟悉吗？
将101，202，303拆成四个不等的正整数之和，各自方法数为a,b,c，求a+b+c

没看出 101，202，303 这三数有啥玄机……还是用老方法吧

设将 `n` 拆分成四个不等的正整数由小到大分别为 `x`, `x+y`, `x+y+z`, `x+y+z+w`，则分拆方法数为 `4x+3y+2z+w=n` 的正整数解的解数，设
\[F=(x^4+x^8+x^{12}+\cdots)(x^3+x^6+x^9+\cdots)(x^2+x^4+x^6+\cdots)(x+x^2+x^3+\cdots),\]
则解数为 `F` 的 `x^n` 的系数。

`a`, `b`, `c` 分别是 `F` 的 `x^{101}`, `x^{202}`, `x^{303}` 的系数，于是 `a+b+c` 是 `(x^{202}+x^{101}+1)F` 的 `x^{303}` 的系数。

emmmm... 虽然理论上将 `F` 化为分式再作一些变形再展开可以实现人工计算，但计算量还是挺大的，还是不写了，直接开挂算了吧……

在 MMA 输入

1. G = (x^202 + x^101 + 1)*Sum[x^(4 k), {k, Floor[303/4]}]*Sum[x^(3 k), {k, Floor[303/3]}]*Sum[x^(2 k), {k, Floor[303/2]}]*Sum[x^k, {k, 303}];
2. Coefficient[G, x^303]

Copy the Code

运行一分多钟后得出结果为 242975。

---

还是写一下人工计算的方法吧😁：
\begin{align*}
\frac F{x^{10}}&=(1+x^4+x^8+\cdots)(1+x^3+x^6+\cdots)(1+x^2+x^4+\cdots)(1+x+x^2+\cdots)\\
&=\frac1{(1-x^4)(1-x^3)(1-x^2)(1-x)},
\end{align*}
`1`, `2`, `3`, `4` 的最小公倍数是 `12`，所以可以将分母化为 `(1-x^{12})^4`，有
\[\frac1{(1-x^4)(1-x^3)(1-x^2)(1-x)}=\frac{K(x)}{(1-x^{12})^4},\]
其中
\[K(x)=(1+x^4+x^8)(1+x^3+x^6+x^9)(1+x^2+x^4+\cdots+x^{10})(1+x+x^2+\cdots+x^{11}),\]
再根据公式
\[\frac1{(1-x)^{n+1}}=\sum_{k=0}^\infty C_{n+k}^nx^k,\]

上式的证明（导数证法）

令
\[f(x)=\frac1{1-x}=1+x+x^2+\cdots,\]
对它求 `n` 阶导数，一方面看分式的，易知是
\[f^{(n)}(x)=\frac{n!}{(1-x)^{n+1}},\]
另一方面看级数的，`x^k` 的 `n` 阶导数，当 `k<n` 时为零，当 `k\geqslant n` 时为 `k(k-1)\cdots(k-n+1)x^{k-n}`，即 `n!C_k^nx^{k-n}`，因此有
\[f^{(n)}(x)=n!(C_n^n+C_{n+1}^nx+C_{n+2}^nx^2+\cdots),\]
比较两式，即得那个公式。

即得
\[\frac F{x^{10}}=K(x)\cdot\sum_{k=0}^\infty C_{3+k}^3x^{12k},\]
这里免不了要展开 `K(x)`（先前说的计算量大就在于此，但毕竟是人工可行的），有
\[K(x)=a_0+a_1x+a_2x^2+\cdots+a_{38}x^{38},\]
其中
\[\{a_0,a_1,a_2,\ldots,a_{19}\}=\{1,1,2,3,5,6,9,11,15,18,23,27,30,35,39,42,44,48,48,50\},\]
（由 `K(1/x)=K(x)/x^{38}` 知系数是左右对称的，即 `a_k=a_{38-k}`，所以 `a_{20}` 后的不必写出）
然后可以分别计算 `a`, `b`, `c`：
由 `101-10=91=5\times12+31=6\times12+19=7\times12+7` 知
\[a=C_{3+5}^3a_{31}+C_{3+6}^3a_{19}+C_{3+7}^3a_7=6136;\]
由 `202-10=192=13\times12+36=14\times12+24=15\times12+12=16\times12` 知
\[b=C_{3+13}^3a_{36}+C_{3+14}^3a_{24}+C_{3+15}^3a_{12}+C_{3+16}^3a_0=53089;\]
由 `303-10=293=22\times12+29=23\times12+17=24\times12+5` 知
\[c=C_{3+22}^3a_{29}+C_{3+23}^3a_{17}+C_{3+24}^3a_5=183750,\]
所以
\[a+b+c=6136+53089+183750=242975.\]

kuing

差点忘了这帖，群里有后续：

生如夏花  2025/03/17 22:27
@kuing 我要跟你道歉，母函数这题是我自己理解错了。

已知 `a`, `b`, `c`, `d\in\{1,2,3,\dots,101\}`
且 `a<b<c<d`，`a+b+c+d` 是 `101` 的倍数，
求 `\{a,b,c,d\}` 的个数。

原题是这个
不一定用母函数做，这是我原来自己认为的

kuing  2025/03/18 00:12
原来 101、202、303 这样来的……
那你有啥方法

生如夏花  2025/03/18 06:54
`\dfrac{C_{101}^4}{101}`

原题和 1# 转化后的区别在于：
1# 的 202 和 303 拆出来的数可以大于 101，而原题限定了四个数均不超过 101，所以转化错误。

不过，最后这个 `C_{101}^4/101` 怎么来的？我当时一下没反应过来，后来不知咋地就忘记了……到现在才想起来😥

现在再想，莫非“生如夏花”想说的是：
对于所有 `k\inN\land k<101`，满足 `a+b+c+d\equiv k\pmod{101}` 的 `\{a,b,c,d\}` 的个数都相等？
而总数是 `C_{101}^4`，因此每一个 `k`，个数都是 `C_{101}^4/101`？
怎么证明全都相等呢？

===== 第二天 =====
我问了一下他，得到的回复是：

生如夏花  
任取其中四个，a,b,c,d，加起来模101=r，则这四个数都加k（k依次取遍0到100），模101，得到一个101的完全剩余系。
理由是4与101互质，101本身是质数
也就是这101组中只有一组是101的倍数
kuing
O，难怪我试过改成 10 结果不是 C(10,4)/10
所以将“是101的倍数”改成“模101余k”都是这个结果
生如夏花  
对

现在我明白了😇

hbghlyj

对于所有 \( k \in \mathbb{N} \) 且 \( k < 101 \)，满足 \( a + b + c + d \equiv k \pmod{101} \) 的四元组 \( \{a, b, c, d\} \) 的个数均相等。

证明：
由于模数 101 是质数，且 4 与 101 互质，因此 4 在模 101 下有唯一的逆元 \( 4^{-1} \)。  
对任意固定的目标余数 \( k \)，存在唯一的 \( t \equiv (k - S) \cdot 4^{-1} \pmod{101} \)（其中 \( S \) 是原四元组的和），使得将每个元素加上 \( t \) 后，新四元组的和模 101 余 \( k \)。

变换 \( a \mapsto (a + t) \pmod{101} \) 是双射：若原四元组元素互异，则变换后仍互异，且每个目标余数 \( k \) 均可通过唯一 \( t \) 达到。因此，每个 \( k \) 对应的四元组数目相同。

总四元组数为组合数 \( \binom{101}{4} \)，均匀分配至 101 个余数类，故每个余数对应的数目为 \( \frac{\binom{101}{4}}{101} \)。

hbghlyj

见 modular forms p48

Dimension of $\mathcal{M}_k\left(\mathrm{SL}_2(\mathbb{Z})\right)$
We first consider the simplest case, applying the above results to $\Gamma=\mathrm{SL}_2(\mathbb{Z})$.
Theorem 31: [23, p. 88] Let $k$ be an integer and consider $\mathcal{M}_k\left(\mathrm{SL}_2(\mathbb{Z})\right)$, the space of modular forms of weight $k$ for $\mathrm{SL}_2(\mathbb{Z})$. The dimension of $\mathcal{M}_k\left(\mathrm{SL}_2(\mathbb{Z})\right)$ can be given as
\[
\operatorname{dim} \mathcal{M}_k\left(\mathrm{SL}_2(\mathbb{Z})\right)= \begin{cases}0 & \text { if } k<0 \text { or } k \text { is odd } \\ \left\lfloor\frac{k}{12}\right\rfloor & \text { if } k \geq 0, k \equiv 2 \bmod 12 \\ \left\lfloor\frac{k}{12}\right\rfloor+1 & \text { if } k \geq 0, k \not \equiv 2 \bmod 12\end{cases}
\]

该公式又见 MF_Lectures p24

Example 3.4 For the full modular group $\mathrm{SL}_2(\mathbb{Z})$ we have $g=0, \sigma=1$ and "distinct" elliptic points have periods 2 (for $i$) and 3 (for $\rho$) (recall $\rho^2$ is just the translate of $\rho$ by $T$). So $\operatorname{dim}\left(M_k(\Gamma)\right)=0$ for $k<0$ and for $k \geq 2$ and even the dimension of the space of weight $k$ forms is
\[
(k-1)(-1)+\frac{k}{2}+\left[\frac{k}{4}\right]+\left[\frac{k}{3}\right]= \begin{cases}{\left[\frac{k}{12}\right]} & \text { if } k \equiv 2 \bmod 12 \\ {\left[\frac{k}{12}\right]+1} & \text { if } k \not \equiv 2 \bmod 12\end{cases}
\]

hbghlyj

kuing 发表于 2025-3-16 07:55
化为分式再作一些变形再展开可以实现人工计算

例如 k 拆成 4,6 的方法数为 $\frac{1}{(1-x^4)(1-x^6)}$ 中 $x^k$ 的系数

1. Series[1/(1 - x^4)/(1 - x^6), {x, 0, 36}]

Copy the Code

1 + x^4 + x^6 + x^8 + x^10 + 2 x^12 + x^14 + 2 x^16 + 2 x^18 + 2 x^20 + 2 x^22 + 3 x^24 + 2 x^26 + 3 x^28 + 3 x^30 + 3 x^32 + 3 x^34 + 4 x^36 + O(x^37)

hbghlyj

k 拆成 4,6 的方法数为 $\frac{1}{(1-x^4)(1-x^6)}$ 中 $x^k$ 的系数
\begin{equation}\label1
\frac{1}{\left(1-x^4\right) \left(1-x^6\right)}=\frac{x^{12}}{(1-x^2)(1-x^{12})}+\frac{1}{1-x^2}-\frac{x^2}{1-x^{12}}\end{equation}
因此 k 拆成 4,6 的方法数为 $\begin{cases}0 & \text { if } k<0 \text { or } k \text { is odd } \\ \left\lfloor\frac{k}{12}\right\rfloor & \text { if } k \geq 0, k \equiv 2 \bmod 12\\ \left\lfloor\frac{k}{12}\right\rfloor+1 & \text { if } k \geq 0, k \not \equiv 2 \bmod 12\end{cases}$

hbghlyj

问：\eqref{1}式是如何得到的？
用WolframAlpha也得不到\eqref{1}式