一个Merca恒等式的组合证明

Combinatorial Proof of an Identity of Merca

摘要: 本文基于Merca研究中提出的一个恒等式，Merca通过代数方法对其进行了证明，而我们从组合数学的角度入手，给出了该恒等式的一个全新的组合证明。相比代数证明，我们发现组合证明过程更加直观和简洁，提供了对该恒等式更深层次的结构性理解。

Abstract: This paper is based on an identity proposed by Merca, which was originally proved by using algebraic method. From the perspective of combinatorics, we present a new combinatorial proof of this identity. Compared to the algebraic approach, our combinatorial proof is more intuitive and concise, which offers a deeper structural understanding of the identity.

1. 引言

整数分拆是组合数学的一个基本问题，它与计数问题密切相关。分拆恒等式揭示了整数分拆在不同组合结构下的对称性和规律性，是组合数学和数论中的重要研究课题。

定义1.1 整数分拆是指将一个正整数表示为若干正整数的无序和。

一个正整数$n$ 的分拆是指一个由正整数组成的序列$\lambda =\left({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_k\right)$ ，该序列中各元素之和为$n$ ，即

$n={\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k$

这个序列中的正整数被称为分拆的一个部分。其中分拆的方式不考虑顺序，即不同的排列视为同一种分拆方式，$n$ 的整数分拆还可以写为：

$n=t_1+2t_2+\cdots +n{t}_n$

其中$t_i$ 表示正整数$i$ 在分拆中出现的次数。

定义1.2 设分拆函数$p\left(n\right)$ 表示将一个正整数$n$ 拆分为若干个正整数之和的所有不同方式的数量。即

$p\left(n\right):={\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}1}$

为了保持一致性，$n$ 的分拆以降序排列的方式书写。例如正整数4有以下五种不同的分拆方式：

$\left(4\right),\left(3,1\right),\left(2,2\right),\left(2,1,1\right),\left(1,1,1,1\right)$

所以$p\left(4\right)=5$ 。

定义1.3 q-级数公式作为代数、分析学中的主要内容，与各个学科结合有非常良好的性质。设$a,q$ 为复数，且$q$ 满足$q<1$ ，标准的q-级数公式表示如下：

${\left(a;q\right)}_{\infty }:={\displaystyle \prod _{k=0}^{\infty }\left(1-a{q}^k\right)}$

由此$p\left(n\right)$ 的生成函数可以表示为[1]：

${\displaystyle \sum _{n=0}^{\infty }p\left(n\right)q^n}=\frac{1}{{\left(q;q\right)}_{\infty }}={\displaystyle \sum _{n_1=0}^{\infty }{q}^{1\cdot n_1}}{\displaystyle \sum _{n_2=0}^{\infty }{q}^{2\cdot n_1}}\cdot \cdot \cdot {\displaystyle \sum _{n_k=0}^{\infty }{q}^{k\cdot n_k}}\cdot \cdot \cdot$ (1)

其中${\left(q;q\right)}_{\infty }={\displaystyle \prod _{k=1}^{\infty }\left(1-q^k\right)}$ 。

Euler是历史上最杰出的数学家之一，在其众多成就中，有一条关于整数分拆的著名恒等式尤为突出，被称为Euler恒等式。该恒等式的组合证明为我们提供了启发。

定理1.4 (Euler恒等式)将整数分拆为奇数部分的分拆个数，与将整数分拆为互不重复的分拆个数相等。

Euler用生成函数的方法证明了该结果，但该结果的组合证明更简洁易懂[2]。一方面，对每个部分都是奇数的分拆进行合并操作：若一个分拆$\lambda$ 包含相同的部分，则将两个相同的部分合并为一个大小为其两倍的部分。重复此操作，直到所有部分都不同。由于每次合并都会减少一个部分，所以这个过程会终止得到一个非重复分拆。例如：

$\begin{array}{c}3+3+3+1+1+1+1\to \left(3+3\right)+3+\left(1+1\right)+\left(1+1\right)\\ \to 6+3+2+2\\ \to 6+3+\left(2+2\right)\\ \to 6+3+4\end{array}$

相反，对于$n$ 的都是不同部分的分拆，将偶数部分分拆为两个相等的部分，重复这个步骤直到每个部分都是奇数，显然这个过程会终止最终得到一个每个部分都是奇数的分拆。例如：

$\begin{array}{c}6+3+4\to 6+3+\left(2+2\right)\\ \to 6+3+2+2\\ \to \left(3+3\right)+3+\left(1+1\right)+\left(1+1\right)\\ \to 3+3+3+1+1+1+1\end{array}$

定理1.5 (Euler五边形数定理)

${\left(q;q\right)}_{\infty }={\displaystyle \sum _{s=-\infty }^{\infty }{\left(-1\right)}^s{q}^{s\left(3s-1\right)/2}}$ (2)

其中${\left(q;q\right)}_{\infty }=\left(1-q\right)\left(1-q^2\right)\left(1-q^3\right)\cdots$

Legendreg对这个定理给出了一个漂亮的组合解释[3]：设$D_e\left(n\right)$ 表示将$n$ 进行非重复的整数分拆，并且部分个数为偶数的分拆个数；设$D_o\left(n\right)$ 表示将$n$ 进行非重复的整数分拆，并且部分个数为奇数的分拆个数。有以下结论：

$D_e\left(n\right)-D_o\left(n\right)=\{\begin{array}{ll}{\left(-1\right)}^j,\hfill & n=\frac{j\left(3j+1\right)}{2},j=1,2,\cdots ,\hfill \\ 0,\hfill & 其他\hfill \end{array}$

1881年F. Franklin给出了欧拉五边形数定理的双射证明[4]。他利用Ferrers图构造了一个$D_e\left(n\right)$ 和$D_o\left(n\right)$ 之间的双射，该双射除了五角数分拆以外都存在。

Merca在[3]中引入了这样一个恒等式，令$z$ 是一个复数，对于任意的正整数$m$ 和$n$ 有：

$a_{m,z}^{\pm }\left(n\right)={\displaystyle \sum _{t_1+2t_2+.\cdots +n{t}_n=n}\left(\lfloor \frac{t_1}{m}\rfloor \pm 2^z\lfloor \frac{t_1}{2m}\rfloor +\cdots +{\left(\pm 1\right)}^{n+1}{\left(n\right)}^z\lfloor \frac{t_1}{nm}\rfloor \right)}$ (3)

$\lfloor x\rfloor$ 表示$x$ 向下取整的部分，其中

$a_{m,z}^{\pm }\left(n\right)={\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}\left(t_m\pm 2^z{t}_{2m}+3^z{t}_{3m}\pm \cdots \right)}$ (4)

这个恒等式的提出源自于Merca对整数的正因数的研究，对于一个复数$z$ ，正因数和函数${\sigma }_z^{\pm }\left(n\right)$ 被定义为$n$ 的正因数的$z$ 次幂之和如下：

${\sigma }_z^{\pm }\left(n\right):={\displaystyle \sum _{d|n}{\left(\pm 1\right)}^{d+1}{d}^z}$

根据生成函数有：

${\displaystyle \sum _{n=1}^{\infty }np\left(n\right)q^n}=\frac{1}{{\left(q;q\right)}_{\infty }}{\displaystyle \sum _{n=1}^{\infty }\frac{n{q}^n}{1-q^n}}=\frac{1}{{\left(q;q\right)}_{\infty }}{\displaystyle \sum _{n=1}^{\infty }{\sigma }_1^{+}\left(n\right)q^n}$ (5)

反过来根据欧拉五边形数定理给出了计算${\sigma }_1^{+}\left(n\right)$ 的方法：

${\sigma }_1^{+}\left(n\right)={\displaystyle \sum _{j=-\infty }^{\infty }{\left(-1\right)}^j\left(n-j\left(3j-1\right)/2\right)p\left(n-j\left(3j-1\right)/2\right)}$ (6)

经过思考，Merca考虑${\sigma }_z^{\pm }\left(n\right)$ 可能有无穷族，(6)式只是一个非常特殊的情况，经过研究得到如下定理。

定理1.6 令$z$ 是一个复数，对于任意的正整数$m$ 和$n$ 有

${\sigma }_z^{\pm }\left(n\right)={\displaystyle \sum _{j=-\infty }^{\infty }{\left(-1\right)}^j{a}_{m,z}^{\pm }\left(mn-j\left(3j-1\right)/2\right)}$ (7)

其中$a_{m,z}^{\pm }\left(n\right)$ 的定义见(4)式。可以看出$a_{m,z}^{\pm }\left(n\right)$ 是$n$ 的分拆和，这些分拆至少包含一个模$m$ 为0的部分，在此背景下，他得到如下定理。

定理1.7 令$z$ 是一个复数，对于任意的正整数$m$ 和$n$ 有

$a_{m,z}^{\pm }={\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}\left(\lfloor \frac{t_1}{m}\rfloor \pm 2^z\lfloor \frac{t_2}{m}\rfloor +\cdots +{\left(\pm 1\right)}^{n+1}{n}^z\lfloor \frac{t_n}{m}\rfloor \right)}$ (8)

和

$a_{m,z}^{\pm }\left(n\right)={\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}\left(\lfloor \frac{t_1}{m}\rfloor \pm 2^z\lfloor \frac{t_1}{2m}\rfloor +\cdots +{\left(\pm 1\right)}^{n+1}{\left(n\right)}^z\lfloor \frac{t_1}{nm}\rfloor \right)}$ (9)

Merca在[5]中给出了(3)式恒等式的代数证明，我们通过分析恒等式两边的组合意义发现用组合证明的方法可以更加直观、简便的理解和证明这个恒等式，组合证明的过程将在第三节给出。下面先介绍Merca给出的代数证明过程。

2. Merca恒等式的代数证明

Merca分别计算(3)式左右两边的生成函数，计算等式左边的生成函数：

$\begin{array}{c}{\displaystyle \sum _{n=0}^{\infty }{a}_{m,z}^{\pm }\left(n\right)q^n}={\displaystyle \sum _{n=0}^{\infty }{q}^n}{\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}\left(t_m\pm 2^z{t}_{2m}+3^z{t}_{3m}\pm \cdots \right)}\\ ={\displaystyle \sum _{i=1}^{\infty }{\displaystyle \sum _{t_1,t_2,t_3,\cdots \ge 0}{\left(\pm 1\right)}^{i+1}{i}^z{t}_{im}{q}^{t_1+2t_2+3t_3+\cdots }}}\\ ={\displaystyle \sum _{i=1}^{\infty }\left({\displaystyle \sum _{\begin{array}{l}j=1\\ j\ne im\end{array}}^{\infty }{\displaystyle \sum _{t_j\ge 0}{q}^{j{t}_j}}}\right){\displaystyle \sum _{t_{im}\ge 0}{\left(\pm 1\right)}^{i+1}{i}^z{t}_{im}{q}^{im{t}_{im}}}}\\ ={\displaystyle \sum _{i=1}^{\infty }\left({\displaystyle \prod _{\begin{array}{l}j=1\\ j\ne im\end{array}}^{\infty }\frac{1}{1-q^j}}\right)}\frac{{\left(\pm 1\right)}^{i+1}{i}^z{q}^{im}}{{\left(1-q^{im}\right)}^2}\\ =\frac{1}{{\left(q;q\right)}_{\infty }}{\displaystyle \sum _{i=1}^{\infty }\frac{{\left(\pm 1\right)}^{i+1}{i}^z{q}^{im}}{1-q^{im}}}\end{array}$ (10)

等式右边的生成函数计算过程：

$\begin{array}{l}{\displaystyle \sum _{n=0}^{\infty }{q}^n}{\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}\left(\lfloor \frac{t_1}{m}\rfloor \pm 2^z\lfloor \frac{t_1}{2m}\rfloor +\cdots +{\left(\pm 1\right)}^{n+1}{\left(n\right)}^z\lfloor \frac{t_1}{nm}\rfloor \right)}\\ ={\displaystyle \sum _{i=1}^{\infty }{\displaystyle \sum _{t_1,t_2,t_3,\cdots \ge 0}{\left(\pm 1\right)}^{i+1}{i}^z\lfloor \frac{t_1}{im}\rfloor q^{t_1+2t_2+3t_3+\cdots }}}\\ ={\displaystyle \sum _{i=1}^{\infty }\left({\displaystyle \sum _{j=2}^{\infty }{\displaystyle \sum _{t_j\ge 0}{q}^{j{t}_j}}}\right){\displaystyle \sum _{t_1\ge 0}{\left(\pm 1\right)}^{i+1}{i}^z\lfloor \frac{t_1}{im}\rfloor q^{t_1}}}\\ =\frac{1-q}{{\left(q;q\right)}_{\infty }}{\displaystyle \sum _{i=1}^{\infty }{\left(\pm 1\right)}^{i+1}{i}^z{\displaystyle \sum _{t_1\ge 0}\lfloor \frac{t_1}{im}\rfloor q^{t_1}}}\\ =\frac{1-q}{{\left(q;q\right)}_{\infty }}{\displaystyle \sum _{i=1}^{\infty }{\left(\pm 1\right)}^{i+1}{i}^z}{\displaystyle \sum _{t_1\ge 0}{\displaystyle \sum _{r=0}^{im-1}{t}_1{q}^{im{t}_1+r}}}\\ =\frac{1-q}{{\left(q;q\right)}_{\infty }}{\displaystyle \sum _{i=1}^{\infty }{\left(\pm 1\right)}^{i+1}{i}^z}\left({\displaystyle \sum _{r=0}^{im-1}{q}^r}\right)\left({\displaystyle \sum _{t_1\ge 0}{t}_1{q}^{im{t}_1}}\right)\\ =\frac{1-q}{{\left(q;q\right)}_{\infty }}{\displaystyle \sum _{i=1}^{\infty }{\left(\pm 1\right)}^{i+1}{i}^z}\frac{1-q^{im}}{1-q}\frac{q^{im}}{{\left(1-q^{im}\right)}^2}\\ =\frac{1-q}{{\left(q;q\right)}_{\infty }}{\displaystyle \sum _{i=1}^{\infty }\frac{{\left(\pm 1\right)}^{i+1}{i}^z{q}^{im}}{1-q^{im}}}\end{array}$ (11)

通过计算发现(3)式左右两边具有相同的生成函数，从而证明了等式成立。下面给出(3)式的组合证明方法。

3. Merca恒等式的组合证明

通过观察恒等式的结构，我们只需证

${\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}{t}_{km}}={\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}\lfloor \frac{t_1}{km}\rfloor }$ (12)

其中$k=1,2,\cdots ,n$ 。

对一个正整数$m\ge 1$ ，取每一个不同的$k$ ，相乘可以得到唯一确定的$km$ 。正整数$n$ 的一个分拆$n:{\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_r$ 可以表示为多重集合$M=\left\{{\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_r\right\}$ ，多重集合$M$ 可以唯一分解成两个多重集合：

$M=M_1\cup M_2$

其中$M_1$ 是正整数$n$ 的分拆中部分是1或者$km$ 的集合。$M_2$ 是$n$ 的分拆中不是1或者$km$ 的部分的集合。例如：令$m=3$ ，$k=2$ ，则$km=6$ ，则对于一个分拆有

$\left\{{\left(1\right)}^{14},2,3,{\left(6\right)}^3,7\right\}=\left\{{\left(1\right)}^{14},{\left(6\right)}^3\right\}\cup \left\{2,3,7\right\}$

其中${\left(a\right)}^b$ 代表部分$a$ 在分拆中出现$b$ 次。

接着我们构造一个映射$\phi$ ：将$M_1$ 中的部分$km$ 全部拆分为1，将部分1合并成若干个$km$ ，直到1出现的次数小于$km$ ，$M_2$ 中的元素不做改变。例如：

$\begin{array}{l}{\left(6\right)}^3\to {\left(1\right)}^{18}\\ {\left(1\right)}^{14}\to \left\{{\left(1\right)}^2{\left(6\right)}^2\right\}\end{array}$

则有：

$\left\{{\left(1\right)}^{14},2,3,{\left(6\right)}^3,7\right\}=\left\{{\left(1\right)}^{14},{\left(6\right)}^3\right\}\cup \left\{2,3,7\right\}\to \left\{{\left(1\right)}^{20},{\left(6\right)}^2\right\}\cup \left\{2,3,7\right\}=\left\{{\left(1\right)}^{20},2,3,{\left(6\right)}^2,7\right\}$

因为映射$\phi$ 使得原始分拆中部分1的个数小于$km$ ，所以等式右边中对$\lfloor t_1/km\rfloor$ 有贡献的1的个数取决于原始分拆中的$km$ 的个数。

所以对于$n$ 的所有的分拆，恒等式(12)的组合意义可以概括为：等式左边表示$n$ 的所有的分拆中部分$km$ 出现的次数，等式右边也表示$n$ 所有分拆中部分$km$ 出现的次数。

$\phi$ 的逆映射规则与$\phi$ 相同，故该映射可逆，所以我们构造了一个双射$\phi$ 证明了恒等式成立。

4. 总结

本文针对Merca的一个恒等式，提出了一种基于双射的组合证明方法，为理解这一恒等式提供了全新视角。研究首先解析恒等式两边的组合意义，在此基础上，核心工作是构造可逆的双射变换，将左侧分拆与右侧组合意义建立一一对应，从而证明两边分拆个数相等。

运用该双射还可以尝试证明有类似结构的恒等式恒等式：

$a_m^z\left(n\right)={\displaystyle \sum _{t_1+2t_2+\cdots +k{t}_k=k}{\displaystyle \sum _{j=1}^{1+\lfloor t_1/m\rfloor }{\left(\pm 1\right)}^{j+1}{j}^z\lfloor \frac{m+t_1}{jm}\rfloor }}$ (13)

其中$k=n-m$ 。

$\begin{array}{l}{\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}{\left(\pm 1\right)}^{t_2+t_4+t_6+\cdots }\left(t_2+2t_4+3t_6+\cdots \right)}\\ ={\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}{\left(\pm 1\right)}^{\lfloor t_1/2\rfloor +\lfloor t_2/2\rfloor +\cdots +\lfloor t_n/2\rfloor }\left(\lfloor \frac{t_1}{2}\rfloor +2\lfloor \frac{t_2}{2}\rfloor +\cdots +n\lfloor \frac{t_n}{2}\rfloor \right)}\end{array}$ (14)

$\begin{array}{l}{\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}{\left(\pm 1\right)}^{t_2+t_4+t_6+\cdots }\left(t_1+3t_3+5t_5+\cdots \right)}\\ ={\displaystyle \sum _{t_1+2t_2+\cdots +n{t}_n=n}{\left(\pm 1\right)}^{\lfloor t_1/2\rfloor +\lfloor t_2/2\rfloor +\cdots +\lfloor t_n/2\rfloor }\left({\widehat{t}}_1+2{\widehat{t}}_2+\cdots +n{\widehat{t}}_n\right)}\end{array}$ (15)

其中$\widehat{t}$ 表示$t$ 模2的余数。

相较于传统的代数证明，这一组合证明不仅直观地验证了恒等式的正确性，更重要的是清晰揭示了等式两侧组合结构之间的深层关联，使其本质更易于理解和把握。该研究为相关恒等式的证明提供了新的组合思路和方法借鉴，丰富了组合数学领域的研究手段。

基金项目

本文受国家自然科学基金面上项目(项目编号：12171370)资助。