與有序分拆的分部量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）。