与有序分拆的分部量1 相关的恒等式及组合证明

郭育红

（河西学院 数学与统计学院，甘肃 张掖 734000）

0 引言

在整数分拆理论中，MACMAHON［1］首次定义了正整数的有序分拆，即把正整数n 表示成正整数的有序和，分拆中的各项称为分部量。如果不考虑分部量的顺序，则为无序分拆。例如，4 的有序分拆有8 个，即4，3+1，1+3，2+2，1+1+2，1+2+1，2+1+1，1+1+1+1，也可表示为（4）（3，1）（1，3）（2，2）（1，1，2）（1，2，1）（2，1，1）（1，1，1，1），无序分拆有5 个，即（4）（3，1）（2，2）（2，1，1）（1，1，1，1）。有序分拆的反分拆是将分部量的顺序倒置产生的分拆。例如，（1，1，2）的反分拆为（2，1，1），二者互为反分拆。

有序分拆的图表示Zig-Zag 图［1］，类似于无序分拆的Ferrers 图，即将有序分拆的每个分部量λi依次用含有λi个点的行来表示，但要求下一行的第一个点与上一行的最后一个点对齐。例如，14 的有序分拆（6，3，1，2，2）的Zig-Zag 图如图1 所示。

图1 14 的有序分拆（6，3，1，2，2）的Zig-Zag 图Fig.1 Zig-Zag graph of compositions for 14

利用有序分拆的Zig-Zag 图可得到有序分拆的共轭分拆，将Zig-Zag 图从左向右按列读取的分拆即为原分拆的共轭分拆。例如，图1 按列读取的有序分拆（1，1，1，1，1，2，1，3，2，1）为（6，3，1，2，2）的共轭分拆。有序分拆α 的共轭分拆用表示，反分拆用α'表示。

在经典的分拆理论中，分拆恒等式一直是研究热点［1-3］，并取得了丰富的成果［4-9］。如关于带约束的有序分拆的恒等式［10-15］。

文献［6］给出了关于正整数的分部量带约束的一些有序分拆与Fibonacci 数之间的关系式。Fibonacci 数满足

定理1［6］设正整数n 的分部量为1 或2 的有序分拆数为C1-2(n)，则

其中，Fn为第n 个Fibonacci 数。

定理2［6］设正整数n 的分部量是奇数的有序分拆数为Codd(n)，则

定理3［6］设正整数n 的分部量大于1 的有序分拆数为C＞1(n)，则

通常，将正整数n 的分部量为1 或2 的有序分拆记为1-2 有序分拆；将正整数n 的分部量为奇数的有序分拆记为奇有序分拆。

借助正整数的带约束的有序分拆数与特殊数列的关系，可产生一些有趣的分拆恒等式。如正整数n 的1-2 有序分拆数等于正整数n+1 的奇有序分拆数。寻找分拆恒等式一直是整数分拆理论研究中重要且有趣的内容，但是获得分拆恒等式或给出分拆恒等式的组合双射证明仍较为困难。

定义1正整数n 的分部量1 在首、末两端的有序分拆是指分部量1 出现且只出现在首端或末端。

定义2正整数n 的分部量2 在首、末两端的1-2 有序分拆是指在n 的1-2 有序分拆中，首端或末端出现分部量2。

例1设n=7，则7 的分部量1 在首、末两端的有序分拆有13 个，即为（1，6），（1，5，1），（1，4，2），（1，2，2，2），（1，2，4），（1，3，3），（1，2，3，1），（3，3，1），（4，2，1），（2，2，2，1），（2，4，1），（6，1），（1，3，2，1）。

设n=5，则5 的分部量2 在首、末两端的1-2 有序分拆有5 个，即为（2，2，1），（2，1，2），（1，2，2），（2，1，1，1），（1，1，1，2）。

首先，考察正整数的分部量1 在首、末两端的有序分拆，给出此类有序分拆数与Fibonacci 数之间的关系式。然后，利用与Fibonacci 数相关的有序分拆恒等式，得到新的分拆恒等式，并给出组合双射证明。

1 主要结果

定理4设C1(n)表示正整数n 的分部量在首、末两端的有序分拆数，则

证明由于分部量1 只能出现在首、末两端，故可分3 种情形：（1）首端分部量为1，其余分部量均大于1；（2）末端分部量为1，其余分部量均大于1；（3）首、末端分部量均为1，其余分部量均大于1。

情形（1）和（2）中的分拆数等于n-1 的分部量大于1 的有序分拆数，而情形（3）中的分拆数等于n-2 的分部量大于1 的有序分拆数，从而由定理3，得

证毕！

下面通过构造组合双射来证明。

证明对于正整数n 的分部量1 在末端的任意有序分拆α=(b1，b2，…，bk-1，1)，若b1=2，则用b1-1 替换b1，且删掉末端的分部量1，得到分拆β=(1，b2，b3，…，bk-1)，则分拆β 为n-2 的末端分部量大于1 的相应分拆；若b1＞2，则用b1-2 替换b1，可得n-2 的末端分部量为1 的相应分拆。

反之，对于n-2 的分部量1 在首、末两端的任意有序分拆δ=(r1，r2，…，rt)，若rt＞1，则r1=1，用r1+1=2 替换r1，并在末端添加分部量1，得到分拆σ=(2，r2，r3，…，rt，1)，那么分拆σ 是n 的首端分部量为2、末端分部量为1 的有序分拆；若rt=1，则用r1+2 替换r1，得到n 的首端分部量大于2、末端分部量为1 的有序分拆。因此证明了正整数n 的分部量1 在末端的有序分拆与n-2 的分部量1 在首、末两端的有序分拆之间是一一对应的。

对于正整数n 的首端分部量为1 的任意有序分拆ζ=(1，a2，a3，…，ak)，若ak=1，则删掉首端分部量1，得到分拆θ=(a2，a3，…，ak)，θ 为n-1 的首端分部量大于1 的相应分拆；若ak＞1，则用ak-1 替换ak，得到n-1 的首端分部量为1 的相应分拆。

反之，对于n-1 的分部量1 在首、末两端的任意有序分拆π=(s1，s2，…，sl)，若s1=1，则用sl+1替换sl，得到分拆ρ=(1，s2，s3，…，sl+1)，ρ 为n 的末端分部量大于1 的相应有序分拆；若s1＞1，则sl=1，在分拆π 的首端添加分部量1，得到分拆ν=(1，s1，s2…，sl)，其为n 的末端分部量为1 的相应有序分拆。因此证明了正整数n 的分部量1 在首端的有序分拆与n-1 的分部量1 在首、末两端的有序分拆是一一对应的。

因为

且C1(1)=1，C1(2)=1，所以

证毕！

定理5正整数n 的分部量1 在首、末两端的有序分拆数等于正整数n 的奇有序分拆数。

证明对于正整数n 的首端分部量大于1 的任意奇有序分拆α=(a1，a2，…，ak)，先从右向左考察分拆α。若ak≠1，则将ak分拆为（ak-1，1）；若ak=1，则保留ak。再考察ak-1，若ak-1≠1，则保留ak-1；若ak-1=1，则向左找到不等于1 的分部量as，将as分拆为（as-1，1），记as-1=ds，则ds为偶数。然后将ds的右边所有相邻的分部量1 合并，产生的和作为新的分部量。合并时应注意，若ak=1，则保留ak。重复上述过程，考察α 的所有分部量，从而得到n 的分部量1 只在末端的有序分拆。

例如，由9 的奇分拆（5，1，3）和（3，1，1，1，1，1，1）产生分部量1 只在末端的分拆（4，2，2，1）和（2，6，1）的过程，分别为(5，1，3)→(5，1，2，1)→(4，1，1，2，1)→(4，2，2，1)，(3，1，1，1，1，1，1)→(2，1，1，1，1，1，1，1)→(2，6，1)。

反之，对于n 的分部量1 在末端的任意有序分拆β=(b1，b2，…，bt-1，1)，先从左向右考察分拆β 的分部量，若b1为奇数，则保留b1。若b1为偶数，则再考察b2，若b2=1，则将b1与b2相加，得到一个奇分部量；若b2＞1，则将b2分拆为b2个1，并将b1与其右边相邻的1 合并，得到一个奇分部量。重复上述步骤，考察β 的所有分部量，从而得到n 的首端分部量大于1 的奇有序分拆。

例如，由9 的分部量1 在末端的分拆（3，2，3，1）和（2，2，2，2，1）产生奇分拆（3，3，1，1，1）和（3，1，3，1，1）的过程，分别为(3，2，3，1)→(3，2，1，1，1，1)→(3，3，1，1，1)，(2，2，2，2，1) → (2，1，1，2，2，1)→(3，1，2，2，1)→(3，1，2，1，1，1)→(3，1，3，1，1)。

对于正整数n 的首端分部量为1 的任意奇有序分拆π=(1，c2，c3，…，cs)，从左向右考察分拆π，若c2＞1，则保留c2；若c2=1，则将c2与其右边相邻的分部量合并，得到新的分部量。重复上述过程，考察π 的所有分部量，从而得到n 的分部量1 在首端的有序分拆。

反之，对于n 的分部量1 在首端的任意有序分拆δ=(1，r2，r3，…，rl)，从左向右考察分拆δ 的分部量，若r2为奇数，则保留r2；若r2为偶数，则将r2分拆为（1，r2-1）。重复上述步骤，考察δ 的所有分部量，从而得到n 的首端分部量为1 的奇有序分拆。

证毕！

例2设n=8，则8 的奇有序分拆与8 的分部量1 在首、末两端的有序分拆的对应关系为

定理6正整数n 的分部量1 在首、末两端的有序分拆数等于正整数n+1 的分部量大于1 的有序分拆数。

证明将正整数n 的分部量1 在首、末两端的有序分拆分为2 类：

（i）首端分部量为1 的分拆；

（ii）首端分部量不为1 的分拆。

对于（i）中的任意分拆α=(1，b2，b3…，bk)，首先在α 的末端添加分部量1，并将首端的分部量1 移至末端，得到分拆β=(b2，b3…，bk，1，1)。然后，合并分拆β 的末端所有相邻的分部量1，产生的和作为末端新的分部量，得到分拆γ=(b2，b3…，bs)，其中，末端分部量bs(1 ＜bs≤3)是n+1 的分部量大于1、末端分部量不超过3 的分拆。例如，由7 的分拆（1，2，3，1）产生8 的分拆（2，3，3）的过程为(1，2，3，1)→ (1，2，3，1，1)→(2，3，1，1，1) →(2，3，3)。反之，对于n+1 的分部量大于1、末端分部量不超过3 的任意分拆 π=(c1，c2，…，ct)，其 中，ci＞1，i=1，2，…，t-1，1 ＜ct≤3，首先，用dt=ct-1 替换分部量ct，得到分拆ρ=(c1，c2，…，dt)。然后，对于分拆ρ，将末端分部量dt分拆出一个1 作为首端分部量，dt-1 仍为末端分部量。如果dt=1，则直接将dt移至首端，得到n 的首端分部量为1 的有序分拆。例如，由8 的分拆（2，3，3）产生7 的分拆（1，2，3，1）的过程为(2，3，3)→(2，3，2)→(1，2，3，1) ；而由8 的分拆（4，2，2）产生7 的分拆（1，4，2）的过程为(4，2，2)→(4，2，1)→(1，4，2)。

对于（ii）中的任意分拆ς=(r1，r2，…，rt-1，1)，r1≠1，首先，在ς 的末端添加分部量1，得到分拆η=(r1，r2，…，rt-1，1，1)。然后，在分拆η 中，将末端的3 个分部量rt-1，1，1 相加，将其和作为末端新的分部量，得到分拆θ=(r1，r2，…，rt-1+2)，其为n+1 的分部量大于1 且末端分部量大于3 的分拆。例如，由7 的分拆（2，2，2，1）产生8 的分拆（2，2，4）的过程为(2，2，2，1)→(2，2，2，1，1)→(2，2，4)。反之，对于n+1 的分部量大于1、末端分部量大于3 的任意分拆σ=(c1，c2，…，cs)，ci＞1，i=1，2，…，s-1，cs＞3，首先，用ds=cs-1 替换分部量cs，得到分拆τ=(c1，c2，…，ds)，ds＞2。然后，在分拆τ 中，将末端分部量ds分拆为（ds-1，1），从而得到n 的首端分部量不为1、末端分部量为1 的分拆。例如，由8的分拆（3，5）产生7 的分拆（3，3，1）的过程为(3，5)→(3，4)→(3，3，1)。

证毕！

例3设n=7，则7 的分部量1 在首、末两端的有序分拆与8 的分部量大于1 的有序分拆之间的对应关系为

定理7正整数n 的分部量1 在首、末两端的有序分拆数等于正整数n-1 的1-2 有序分拆数。

证明将正整数n 的分部量1 在首、末两端有序分拆分为2 类：

（i） 首端分部量不为1 的分拆；（ii） 首端分部量为1 的分拆。

对于（i）中的任意分拆α=(r1，r2，…，rk)，rk=1，首先，用r1-1 替换r1，得到分拆β=(r1-1，r2，r3，…，rk)。然后，求分拆β 的共轭分拆为n-1 的末端分部量为2 的1-2 有序分拆。反之，对于n-1 的末端分部量为2 的任意1-2 有序分拆θ=(a1，a2，…，at-1，2)，1 ≤ai≤2，i=1，2，…，t-1，首先，求分拆θ 的共轭分拆为n-1 的末端分部量为1 的分拆。然后，将分拆的首端分部量加1，得到n 的首端分部量不为1 的分拆。

例如，由8 的分拆（3，2，2，1）产生7 的分拆（1，2，2，2） 的过程为 (3，2，2，1)→(2，2，2，1)→ (1，2，2，2)，而由7 的分拆（1，4，2）产生8 的分拆（3，1，1，2，1）的过程为(1，4，2)→(2，1，1，2，1)→ (3，1，1，2，1)。

对于（ii）中的任意分拆ς=(1，c2，c3，…，ck)，首先，若ck≠1，则删掉ς 的首端分部量1，得到分拆η=(c2，c3，…，ck)。然后，求分拆η 的共轭分拆为n-1 的首、末两端分部量均为1 的1-2 有序分拆。若ck=1，则删掉η 的末端分部量ck=1，得到分拆ρ=(1，c2，c3，…，ck-1)。最后，求分拆ρ 的共轭分拆为n-1 的首端分部量为2、末端分部量为1的1-2 有序分拆。反之，对于n-1 的末端分部量为1 的任意1-2 有序分拆σ=(b1，b2，…，bs-1，1)，其中，bi=1，2，i=1，2，…，s-1。 若b1=1，则先求分拆σ 的共轭分拆，则为n-1 的分部量大于1的有序分拆，再在分拆的首端添加分部量1，得到n 的首端分部量1 为的有序分拆；若b1=2，则先求分拆σ 的共轭分拆为n-1 的首端分部量为1、其余分部量大于1 的分拆，再在分拆的末端添加分部量1，得到n 的分部量1 在首、末两端的有序分拆。

证毕！

例4设n=7，则7 的分部量1 在首、末两端的有序分拆与6 的1-2 有序分拆之间的对应关系为

推论1正整数n 的分部量1 在首、末两端的有序分拆数等于正整数n 的分部量2 在首、末两端的1-2 有序分拆数。

证明先求有序分拆的共轭分拆，再利用2 个分拆之间是一一对应的结论来证明，此证略。

例5设n=6，则6 的分部量1 在首、末两端的有序分拆为（1，2，2，1），（1，4，1），（1，2，3），（3，2，1），（5，1），（1，5），（1，3，2），（2，3，1）。6 的首、末两端的分部量为2 的1-2 有序分拆为（2，2，2），（2，1，1，2），（2，2，1，1），（1，1，2，2），（1，1，1，1，2），（2，1，1，1，1），（2，1，2，1），（1，2，1，2）。

推论2正整数n 的首端分部量为1 的1-2 有序分拆数等于正整数n 的分部量1 在首、末两端的有序分拆数。

证明对于n 的分部量1 在首、末两端的任意有序分拆γ=(c1，c2，…，cs)，当cs≠1 时，按照从左向右的顺序，将大于2 的分部量分拆为（1，1，…，1，2）的形式，得到n 的首端分部量为1、末端分部量为2的1-2 有序分拆；当cs=1 时，按照从左向右的顺序分2 种情形：（1）若c1=1，将大于2 的分部量分拆为（2，1，…，1）的形式；（2）若c1≠1，将c1分拆为（1，1，…，1），并将大于 2 的分部量分拆为（2，1，…，1）的形式，从而得到n 的首端分部量为1、末端分部量为1 的1-2 有序分拆。

反之，对于n 的分部量1 在首端的任意1-2 有序分拆δ=(1，a2，a3，…，ak)，当ak=2 时，保留首端分部量1，按照从右向左的顺序，将分部量2，1，…，1 相加，将其和作为新的分部量，得到n 的末端分部量大于1、首端分部量为1 的有序分拆；当ak=1 时，保留ak=1，按照从右向左合并分部量1，1，…，1，2，将其和作为新的分部量，从而得到n 的末端分部量为1 的有序分拆。

证毕！

例6设n=6，则6 的分部量1 在首、末两端的有序分拆为（1，2，2，1），（1，4，1），（1，2，3），（3，2，1），（5，1），（1，5），（1，3，2），（2，3，1）。6 的首端分部量为1 的1-2 有序分拆为（1，2，2，1），（1，2，1，1，1），（1，2，1，2），（1，1，1，2，1），（1，1，1，1，1，1），（1，1，1，1，2），（1，1，2，2），（1，1，2，1，1）。

推论3正整数n 的末端分部量为1 的1-2 有序分拆数等于正整数n 的分部量1 在首、末两端的有序分拆数。

证明取推论2 中1-2 有序分拆的反分拆，即得推论3 的相应分拆，此证略。

例7设n=7，则7 的分部量1 在首、末两端的有序分拆为（6，1），（2，4，1），（4，2，1），（2，2，2，1），（3，3，1），（1，6），（1，3，3），（1，2，4），（1，4，2），（1，2，2，2），（1，5，1），（1，2，3，1），（1，3，2，1）。7 的末端分部量为1 的1-2 有序分拆为（1，1，1，1，1，1，1），（1，1，2，1，1，1），（1，1，1，1，2，1），（1，1，1，2，1，1），（1，1，2，2，1），（1，1，1，1，1，2），（1，1，2，1，2），（1，2，1，1，2），（1，1，1，2，2），（1，2，2，2），（1，2，1，1，1，1），（1，2，2，1，1），（1，2，1，2，1）。