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

2023-06-07 11:16郭育红
浙江大学学报(理学版) 2023年3期
关键词:左向右首端恒等式

郭育红

(河西学院 数学与统计学院,甘肃 张掖 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)。

猜你喜欢
左向右首端恒等式
自适应工况的大型水轮发电机定子接地故障定位方法
活跃在高考中的一个恒等式
理想当燃
重载铁路牵引网雷击仿真模型比较研究
首升降舵布局方式对潜艇垂直面操纵性能仿真分析
一类新的m重Rogers-Ramanujan恒等式及应用
向左向右扭一扭
日常问候用语?《尼山萨满传》节选
Weideman公式的证明
变压器Y,d接线组别联接技巧