幾個關于1-2有序分拆的恒等式及組合證明

郭 育 紅

( 河西學院 數學與統(tǒng)計學院， 甘肅 張掖 734000 )

0 引 言

在整數分拆理論中，MacMahon[1]第一次定義了正整數的有序分拆．即把正整數n表示成一些正整數的有序和，其中每一項叫該分拆的分部量．如果不考慮分部量的順序就是無序分拆．例如，4的有序分拆有4，3+1，1+3，2+2，2+1+1，1+2+1，1+1+2，1+1+1+1或(4)，(3，1)，(1，3)，(2，2)，(2，1，1)，(1，2，1)，(1，1，2)，(1，1，1，1)共8個，而無序分拆有5個：4，3+1，2+2，2+1+1，1+1+1+1．有序分拆的反分拆是把該分拆的分部量的順序倒過來產生的分拆．例如，(1，1，2)的反分拆就是(2，1，1)，它們互為反分拆．分拆α的反分拆用α′表示．

在經典的分拆理論中，分拆恒等式的研究一直是熱點問題之一[1-3]．近年來，許多研究者得到了豐富的研究成果[4-9]．本課題組也得到了一些關于帶約束的有序分拆恒等式[10-16]．

通常把正整數n的分部量是1或者2的有序分拆稱為1-2有序分拆，把正整數n的分部量是奇數的有序分拆稱為奇有序分拆．

借助于正整數的帶約束的有序分拆與特殊數列的關系，能夠產生一些有趣的分拆恒等式．比如，正整數n的1-2有序分拆數等于正整數n+1的奇有序分拆數．尋找分拆恒等式一直是整數分拆理論研究中有趣的內容，但是，獲得分拆恒等式或者給出分拆恒等式的組合證明仍然是比較困難的．

本文考察正整數的首、末兩端分部量是1或者2的1-2有序分拆，給出這些有序分拆數與Fibonacci 數之間的一些關系式，進而，利用熟知的與Fibonacci數相關的有序分拆恒等式得到幾個新的有序分拆恒等式，并給出組合雙射證明．

1 預備知識

在文獻[1]中，MacMahon給出了有序分拆的圖表示，稱為zig-zag圖，類似于無序分拆的Ferres圖，即將有序分拆每個分部量λi依次用含有λi個點的行來表示，但要求下一行的第一個點與上一行的最后一個點對齊．例如14的有序分拆(6，3，1，2，2)的zig-zag圖如圖1所示．

圖1 Zig-zag圖

文獻[6]中給出了關于正整數的分部量帶約束的一些有序分拆數與Fibonacci數之間的關系式．所謂Fibonacci數是指滿足以下條件的數：F1=1，F2=1，Fn=Fn-1+Fn-2，n>2．

下面以定理的形式給出文獻[6]中幾個熟知的關系式．

定理1[6]設正整數n的分部量是1或者2的有序分拆數為C1-2(n)，則

C1-2(n)=Fn+1；n>0

其中Fn+1是第n+1個Fibonacci數．

定理2[6]設正整數n的分部量是奇數的有序分拆數為Codd(n)，則

Codd(n)=Fn；n>0

其中Fn是第n個Fibonacci數．

定理3[6]設正整數n的分部量是大于1的有序分拆數為C>1(n)，則

C>1(n)=Fn-1；n>1

其中Fn-1是第n-1個Fibonacci數．

2 主要結果

首先給出下面與分部量2有關的1-2有序分拆數和Fibonacci數的一個關系式．

其中Fn是第n個Fibonacci數．

下面給出該定理的一個組合證明．

證明把正整數n的首、末兩端的分部量至少有一個是2的1-2有序分拆分為下面兩類：

(A)左端的分部量是2；

(B)左端的分部量是1．

對于(A)類中的任意一個分拆α=(2，a2，a3，…，ak)，若ak=1，則直接刪掉ak=1，就得到了n-1的首、末兩端分部量至少有一個是2，且左端分部量是2的1-2有序分拆；若ak=2，則把左端的分部量2用1替換，就得到了n-1的首、末兩端分部量至少有一個是2，且左端分部量不是2的1-2有序分拆．這樣，就得到了n-1的首、末兩端分部量至少有一個是2的1-2有序分拆．反之，對于n-1的首、末兩端分部量至少有一個是2的任意一個1-2有序分拆β=(b1，b2，…，bs)，其中b1、bs中至少有一個是2，若b1=2，則在β的右端添上分部量1，就得到分拆γ=(b1，b2，…，bs，1)，則γ就是n的右端分部量是1的相應1-2有序分拆．若b1=1，此時bs=2，用b1+1替換b1，得到Δ=(2，b2，…，bs)，則Δ就是n的右端分部量是2的相應1-2有序分拆．這樣就說明了(A)類中的分拆與n-1的首、末兩端分部量至少有一個是2的1-2有序分拆是一一對應的．

即

故結論成立．

□

由于正整數n的1-2有序分拆數等于Fn+1，利用Fibonacci數的性質，得到關于分部量1的1-2有序分拆的一個關系式．

其中Fn-1是第n-1個Fibonacci數．

下面給出該關系式的一個組合證明．

證明把正整數n首、末兩端分部量都是1的1-2有序分拆分為下面兩類：

(A)第二個分部量是2，即α=(1，2，a3，…，ak，1)；

(B)第二個分部量是1，即β=(1，1，c3，…，ct，1)．

對于(A)類中的任意一個分拆α=(1，2，a3，…，ak，1)，直接刪掉第二個分部量2就得到了n-2的首、末兩端分部量都是1的1-2有序分拆．反之，對于n-2的首、末兩端分部量都是1的任意一個1-2有序分拆γ=(1，b2，…，bs-1，1)，在前兩個分部量1與b2之間添上分部量2，得到的分拆δ=(1，2，b2，…，bs-1，1)，就是n的首、末兩端分部量都是1的相應分拆．這樣就說明了(A)類中的分拆與n-2的首、末兩端分部量都是1的1-2 有序分拆是一一對應的．

對于(B)類中的任意一個分拆β=(1，1，c3，…，ct，1)，刪掉β的第一個分部量1，就得到了n-1的首、末兩端分部量都是1的1-2有序分拆．反之，對于n-1的首、末兩端分部量都是1的任意一個1-2有序分拆ζ=(1，c1，c2，…，cs-1，1)，在ζ的左端添上分部量1，就得到了n的首、末兩端分部量都是1，且左邊至少有2個分部量1的1-2有序分拆．這樣就說明了(B)類中的分拆與n-1的首、末兩端分部量都是1的1-2有序分拆是一一對應的．

即

故結論成立．

□

進一步考察，得到下面與Fibonacci數相關的結果．

其中Fn是第n個Fibonacci數．

其中Fn是第n個Fibonacci數．

定理6與定理7的組合證明類似于定理5，故證明略．

下面給出定理6的一個例子．

例1設n=6，則6的首端分部量是1的1-2 有序分拆有下面8個：

(1，2，2，1)，(1，2，1，1，1)，(1，1，2，1，1)，(1，1，1，2，1)，(1，1，1，1，2)，(1，1，1，1，1，1)，(1，1，2，2)，(1，2，1，2)

由定理6及定理1～3可得到下面的有序分拆恒等式．

推論1正整數n的首端分部量是1的1-2有序分拆數等于n的奇有序分拆數．

推論2正整數n的首端分部量是1的1-2有序分拆數等于n+1的分部量大于1的有序分拆數．

推論3正整數n的首端分部量是1的1-2有序分拆數等于n-1的1-2有序分拆數．

類似地，給出下面的恒等式．

推論4正整數n的末端分部量是1的1-2有序分拆數等于n的奇有序分拆數．

推論5正整數n的末端分部量是1的1-2有序分拆數等于n+1的分部量大于1的有序分拆數．

推論6正整數n的末端分部量是1的1-2有序分拆數等于n-1的1-2有序分拆數．

下面僅給出推論6的一個例子．

例2設n=6，則6的末端分部量是1的1-2有序分拆有下面8個：

(1，2，2，1)，(1，2，1，1，1)，(2，2，1，1)，(1，1，2，1，1)，(1，1，1，1，1，1)，(2，1，1，1，1)，(2，1，2，1)，(1，1，1，2，1)

與5的以下8個1-2有序分拆一一對應：

(1，2，2)，(1，2，1，1)，(2，2，1)，(1，1，2，1)，(1，1，1，1，1)，(2，1，1，1)，(2，1，2)，(1，1，1，2)

結合定理3和定理5，易得下面的有序分拆恒等式．

定理8正整數n的首、末兩端的分部量都是1的1-2有序分拆數等于n的分部量大于1的有序分拆數．

利用有序分拆的共軛易知兩類分拆之間存在一一對應關系，證明略．

由定理4和定理2可得到下面的恒等式．

定理9正整數n的首、末兩端分部量至少有一個是2的1-2有序分拆數等于n的奇有序分拆數．

下面給出該定理的一個組合證明．

證明對于正整數n的首、末兩端分部量至少有一個是2的任意一個1-2有序分拆α=(a1，a2，…，ak)，若a1=1，此時ak=2，在α中，按照從左向右的順序，將分部量1和其右邊相鄰的所有分部量2相加，產生的和作為新的分部量，這樣得到的分拆就是n的左端分部量是1，右端分部量大于1的奇有序分拆．反之，對于n的右端分部量大于1的任意一個奇有序分拆，將大于1的奇分部量分拆成“1，2，2，…，2”的形式，就得到n的左端分部量是1，右端分部量是2的1-2有序分拆．

在α中，當a1=2時，分兩種情形來討論：

(a)右端的分部量ak=1；

(b)右端的分部量ak=2．

對于情形(a)中的任意一個分拆β=(2，a2，…，ak-1，1)，首先將左端的分部量2分拆成“1，1”，得到分拆γ=(1，1，a2，…，ak-1，1)，然后在分拆γ中按照從左向右的順序，將分部量1和其右邊相鄰的所有分部量2相加，產生的和作為新的分部量，這樣就得到n的左、右兩端分部量都是1的奇有序分拆．反之，對于n的左、右兩端分部量都是1的任意一個奇有序分拆，將大于1的奇分部量分拆成“1，2，2，…，2”的形式，然后將左端的兩個相鄰的分部量“1，1”相加，得到的2作為新的分部量，就得到情形(a)中的分拆．

兩類分拆之間是一一對應的．

□

下面給出一個例子來說明定理9中的對應關系．

例3設n=6，則6的首、末兩端分部量至少有一個是2的1-2有序分拆有下面8個：

(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)

與6的以下8個奇有序分拆一一對應：

(5，1)，(3，1，1，1)，(1，3，1，1)，(1，5)，(1，1，1，3)，(1，1，1，1，1，1)，(1，1，3，1)，(3，3)

類似地，由定理4、定理1和定理3得到下面的恒等式．

定理10正整數n的首、末兩端分部量至少有一個是2的1-2有序分拆數等于n-1的1-2有序分拆數．

證明對于正整數n的首、末兩端分部量至少有一個是2的任意一個1-2有序分拆δ=(r1，r2，…，rt)，若rt=2，則用rt-1=1替換rt，就得到n-1的右端分部量是1的相應分拆．若rt=1，則r1=2，求δ的反分拆δ′=(rt，…，r2，r1)，然后刪掉δ′左端的分部量rt，就得到n-1的右端分部量是2的相應分拆．

反之，對于n-1的任意一個1-2有序分拆σ=(c1，c2，…，ck)，若ck=1，則用ck+1=2替換ck，就得到n的右端分部量是2的1-2有序分拆；若ck=2，先在σ的左端添上分部量1，得到分拆τ=(1，c1，c2，…，ck)，再求τ的反分拆τ′，則τ′就是n的右端分部量是1，左端分部量是2的1-2有序分拆．

故兩類分拆之間一一對應．

□

定理11正整數n的首、末兩端分部量至少有一個是2的1-2有序分拆數等于n+1的分部量大于1的有序分拆數．

故兩類分拆之間一一對應．

□

由定理4和定理6可得到下面的恒等式．

推論7正整數n的首、末兩端分部量至少有一個是2的1-2有序分拆數等于正整數n的首端分部量是1的1-2有序分拆數．

證明對于正整數n的首、末兩端分部量至少有一個是2的任意一個1-2有序分拆α=(a1，a2，…，ak)，其中a1、ak至少有一個是2，若ak=1，此時a1=2，則求α的反分拆，就得到n的左端分部量是1，右端分部量是2的1-2有序分拆．若ak=2，分兩種情況：當a1=2，將a1=2分拆成“1，1”，并把這兩個1分別放在左、右兩端；當a1=1，此時ak=2，將ak=2分拆成“1，1”．于是得到n的左、右兩端分部量是1的1-2有序分拆．反之，對于n的任意一個首端分部量是1的1-2有序分拆β=(b1，b2，…，bt-1，bt)，其中b1=1，若bt=2，求β的反分拆，就得到n的左端分部量是2，右端分部量是1的1-2有序分拆；若bt=1，分兩種情況：當bt-1=1，把bt與bt-1合并得到的2作為右端新的分部量；當bt-1=2，把bt與左端的分部量b1合并得到的2作為左端新的分部量．于是得到n的右端分部量是2的1-2有序分拆．

□

由定理4和定理7可得到下面的恒等式．

推論8正整數n的首、末兩端分部量至少有一個是2的1-2有序分拆數等于正整數n的末端分部量是1的1-2有序分拆數．

該推論的證明與推論7相同，故證明略．

下面給出推論8的一個例子．

例4設n=6，則6的首、末兩端分部量至少有一個是2的1-2有序分拆有下面8個：

(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)

與6的以下8個末端分部量是1的1-2有序分拆一一對應：

(1，2，2，1)，(1，2，1，1，1)，(2，2，1，1)，(1，1，2，1，1)，(1，1，1，1，1，1)，(2，1，1，1，1)，(2，1，2，1)，(1，1，1，2，1)

3 結 語

在整數分拆理論中，分拆恒等式的研究一直是研究熱點，而關于分部量帶約束條件正整數有序分拆恒等式的研究還不是非常深入．本文主要考察了正整數的分部量是1或者2的有序分拆，尤其是正整數的首、末兩端分部量是1或者2的1-2有序分拆，得到了這些有序分拆數與Fibonacci 數之間的一些關系式．進而，利用熟知的與Fibonacci數相關的有序分拆恒等式，得到了幾個關于正整數的1-2有序分拆的新的有序分拆恒等式，并給出了組合雙射證明．這些結果在理論上進一步豐富了整數分拆恒等式，同時也為尋找整數分拆恒等式的組合雙射證明提供了一些方法．