一類(lèi)不含分部量2的有序分拆

郭 育 紅

(河西學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 張掖 734000)

0 引 言

圖1 分拆(6,3,1,2,2)的zig-zag圖Fig.1 Zig-zag graph of composition (6,3,1,2,2)

整數(shù)分拆理論是組合數(shù)學(xué)研究領(lǐng)域中的一個(gè)重要課題, 目前已有很多研究結(jié)果[1-2]. 近年來(lái), 關(guān)于分部量帶約束條件的有序分拆的研究也取得了許多成果[3-7]. 在經(jīng)典分拆理論中, MacMahon[1]定義了正整數(shù)的有序分拆, 即把正整數(shù)n表示成一些正整數(shù)的有序和, 其中每項(xiàng)稱(chēng)為該分拆的分部量. 例如: 4的有序分拆有4,3+1,1+3,2+2,2+1+1,1+2+1,1+1+2,1+1+1+1, 共8個(gè), 也可記為(4),(3,1),(1,3),(22),(12,2),(1,2,1),(2,12),(14). 文獻(xiàn)[1]給出了有序分拆的一些分析性質(zhì)及圖表示, 稱(chēng)為zig-zag圖, 類(lèi)似于無(wú)序分拆的Ferres圖, 即將有序分拆每個(gè)分部量ni依次用一行含有ni個(gè)點(diǎn)表示, 但要求下一行的第一個(gè)點(diǎn)與上一行的最后一個(gè)點(diǎn)對(duì)齊. 例如: 分拆(6,3,1,2,2)的zig-zag圖如圖1所示.

定理1[10]設(shè)C≠2(m)表示正整數(shù)m的不含分部量2的有序分拆數(shù), 則

C≠2(n)=2C≠2(n-1)-C≠2(n-2)+C≠2(n-3),n>2,

(1)

本文進(jìn)一步研究正整數(shù)互為共軛的分拆均不含分部量2的有序分拆, 給出該類(lèi)有序分拆數(shù)與Fibonacci數(shù)之間的一個(gè)關(guān)系式, 并結(jié)合正整數(shù)的分部量是1,2, 分部量是奇數(shù), 分部量大于1的有序分拆與Fibonacci數(shù)之間的關(guān)系式, 得到這幾類(lèi)有序分拆數(shù)之間的幾個(gè)分拆恒等式, 并給出其組合證明. 本文用CC≠2(n)表示正整數(shù)n的互為共軛分拆均不含分部量2的有序分拆數(shù).

1 主要結(jié)果

由于正整數(shù)7的有序分拆(5,1,1)的共軛分拆是(1,1,1,1,3), 所以(5,1,1) 即為本文所研究的有序分拆, 而分拆(3,4)的共軛分拆是(1,1,2,1,1,1), 含有分部量2, 所以(3,4)不是本文所討論的有序分拆. 首先給出這種有序分拆數(shù)的遞推關(guān)系式.

定理2設(shè)CC≠2(n)表示正整數(shù)n互為共軛的分拆均不含分部量2的有序分拆數(shù), 則

CC≠2(1)=1,CC≠2(2)=0,CC≠2(3)=2,CC≠2(4)=2,

(2)

CC≠2(n)=CC≠2(n-1)+CC≠2(n-2),n>4.

(3)

證明: 因?yàn)橛行蚍植鸺捌涔曹椃植鹂偝蓪?duì)出現(xiàn), 故本文僅考慮左端分部量是1的有序分拆. 互為共軛的分拆均不含分部量2的有序分拆, 若左端的分部量是1, 則最少含有兩個(gè)1. 下面分兩種情形討論：

1) 左端分部量是“1,1”;

在情形1)中, 對(duì)于n的任何一個(gè)適當(dāng)?shù)挠行蚍植? 先刪掉左端兩個(gè)分部量“1,1”, 得到分拆α, 然后求α的共軛分拆α′, 則α′即為n-2的左端分部量是1的相應(yīng)有序分拆. 反之, 對(duì)于n-2的左端分部量是1的適當(dāng)有序分拆β, 先求其共軛分拆β′, 再在β′的左端添上兩個(gè)分部量“1,1”, 于是即得到n的左端分部量是“1,1”的相應(yīng)有序分拆.

在情形2)中, 對(duì)于n的任何一個(gè)適當(dāng)?shù)挠行蚍植? 刪掉左端的一個(gè)分部量1即得到n-1的左端分部量是1的相應(yīng)有序分拆. 反之亦然.

由于1符合條件的有序分拆是(1), 2符合條件的有序分拆沒(méi)有, 3符合條件的有序分拆是(1,1,1),(3), 4符合條件的有序分拆是(1,1,1,1),(4), 故結(jié)論成立. 證畢.

表1列出了部分正整數(shù)互為共軛的分拆均不含分部量2的有序分拆數(shù).

表1 互為共軛的分拆均不含分部量2的有序分拆數(shù)

數(shù)列CC≠2(n)與數(shù)列A006355相同[11], 而序列A006355也表示n-pan圖的匹配數(shù). 由上述遞推關(guān)系易得如下推論.

推論2若CC≠2(n)表示正整數(shù)n的互為共軛的分拆均不含分部量2的有序分拆數(shù), 則

CC≠2(n+2)=2Fn,n>0.

(4)

由于正整數(shù)n的分部量是奇數(shù)的有序分拆數(shù)等于Fn, 正整數(shù)n的分部量是1,2的有序分拆數(shù)等于Fn+1, 正整數(shù)n的分部量大于1的有序分拆數(shù)等于Fn-1, 因此易得正整數(shù)n的互為共軛的分拆均不含分部量2的有序分拆數(shù)與上述幾類(lèi)有序分拆數(shù)之間的分拆恒等式. 因?yàn)橛行蚍植鸺捌涔曹椨行蚍植鹂偸浅蓪?duì)出現(xiàn), 故本文僅給出左端分部量是1的組合證明, 左端分部量大于1的證明類(lèi)似.

定理3設(shè)C>1(n)表示正整數(shù)n的分部量大于1的有序分拆數(shù), 則

CC≠2(n+1)=2C>1(n),n>1.

(5)

證明: 對(duì)于正整數(shù)n+1的互為共軛的分拆均不含分部量2, 且左端分部量是1的任意一個(gè)有序分拆α, 首先求α的共軛分拆α′, 此時(shí)α′左端的第一個(gè)分部量h>2, 且兩個(gè)大于2的分部量之間至少有一個(gè)分部量1; 其次, 在α′中按照從左向右的順序?qū)⒎植苛?右邊大于2的分部量d分拆成“1,d-1”, 然后仍按照從左向右的順序?qū)⑾噜彽姆植苛俊?,1,…,1”相加產(chǎn)生新的分部量, 即得到分拆β； 最后, 將分拆β左端的第一個(gè)分部量h用h-1代替, 得到有序分拆γ, 則γ即為n的分部量大于1的有序分拆.

反之, 對(duì)于n的任意一個(gè)分部量大于1的有序分拆γ=(λ1,λ2,…,λt), 首先把第一個(gè)分部量λ1用λ1+1替換, 按照從左向右的順序, 依次將λ2分拆成“1,1,…,1”,λ3不變,λ4分拆成“1,1,…,1”,λ5不變, 以此類(lèi)推直到λt, 即得到分拆δ; 其次, 對(duì)于δ按照從右向左的順序, 將大于1的分部量h與其左邊的一個(gè)1相加作為新的分部量得到有序分拆β, 此時(shí),β是任意兩個(gè)大于1的分部量之間至少有一個(gè)分部量1; 最后求β的共軛分拆β′, 則β′即為n+1的左端第一個(gè)分部量是1, 且分拆及其共軛分拆均不含分部量2的有序分拆.

例如, 14的有序分拆(1,1,3,1,1,1,3,1,1,1)產(chǎn)生13的分拆(2,2,4,2,3)過(guò)程如下：

反之,

故結(jié)論成立. 證畢.

下面舉例說(shuō)明定理3中的分拆恒等式.

例1當(dāng)n=7時(shí), 8的互為共軛的分拆均不含分部量2的有序分拆與7的分部量大于1的有序分拆之間的對(duì)應(yīng)關(guān)系為:

(1,1,1,1,1,1,1,1)?(7)?(8), (1,1,6)?(2,5)?(3,1,1,1,1,1),

(1,1,1,1,1,3)?(5,2)?(6,1,1), (1,1,1,1,4)?(4,3)?(5,1,1,1),

(1,1,1,5)?(3,4)?(4,1,1,1,1), (1,1,1,3,1,1)?(3,2,2)?(4,1,3),

(1,1,4,1,1)?(2,3,2)?(3,1,1,3), (1,1,3,1,1,1)?(2,2,3)?(3,1,4).

定理4設(shè)C1-2(n)表示正整數(shù)n的分部量是1,2的有序分拆數(shù), 則

CC≠2(n+3)=2C1-2(n),n>0.

(6)

證明: 對(duì)于正整數(shù)n+3的互為共軛的分拆均不含分部量2, 且左端分部量是1的任意一個(gè)有序分拆α, 由定理3的證明可得n+2 的分部量大于1的有序分拆β. 下面求β的共軛分拆β′. 因?yàn)棣率欠植苛看笥?的有序分拆, 所以其共軛分拆β′即為分部量是1,2, 且左右兩端的分部量都是1的有序分拆. 將β′的左右兩端各刪掉一個(gè)分部量1, 即得到n的分部量均為1,2的有序分拆. 由定理3的證明以及上述對(duì)應(yīng)法則可知, 該對(duì)應(yīng)關(guān)系是可逆的. 證畢.

定理5設(shè)Codd(n)表示正整數(shù)n的分部量是奇數(shù)的有序分拆數(shù), 則

CC≠2(n+2)=2Codd(n),n>0.

(7)

證明: 對(duì)于正整數(shù)n+2的互為共軛的分拆均不含分部量2, 且左端分部量是1的任意一個(gè)有序分拆α, 由定理3的證明可得n+1的分部量大于1的有序分拆β. 下面求β的共軛分拆β′. 因?yàn)棣率欠植苛看笥?的有序分拆, 所以其共軛分拆β′即為分部量是1,2, 且左右兩端的分部量都是1的有序分拆. 將β′的左端刪掉一個(gè)分部量1, 再按照從右向左的順序?qū)?及其左邊相鄰的所有2相加產(chǎn)生新的分部量, 于是得到n的分部量均為奇數(shù)的有序分拆. 由定理3的證明以及上述對(duì)應(yīng)法則可知, 該對(duì)應(yīng)關(guān)系是可逆的. 證畢.

下面舉例說(shuō)明定理5中的分拆恒等式.

例2當(dāng)n=6時(shí), 8的互為共軛的分拆均不含分部量2的有序分拆與6的分部量是奇數(shù)的有序分拆之間的對(duì)應(yīng)關(guān)系為:

(1,1,1,1,1,1,1,1)?(1,1,1,1,1,1)?(8), (1,1,6)?(3,1,1,1)?(3,1,1,1,1,1),

(1,1,1,1,1,3)?(1,1,1,3)?(6,1,1), (1,1,1,1,4)?(1,1,3,1)?(5,1,1,1),

(1,1,1,5)?(1,3,1,1)?(4,1,1,1,1), (1,1,1,3,1,1)?(1,5)?(4,1,3),

(1,1,4,1,1)?(3,3)?(3,1,1,3), (1,1,3,1,1,1)?(5,1)?(3,1,4).

在整數(shù)分拆理論中, 分部量帶約束條件的分拆一直是該領(lǐng)域的研究熱點(diǎn), 尤其是尋找各類(lèi)有序分拆數(shù)之間的分拆恒等式, 建立不同類(lèi)型分拆之間的組合雙射具有重要的理論意義. 本文借助一些特殊的有序分拆數(shù)與Fibonacci數(shù)之間的關(guān)系式, 給出了正整數(shù)的互為共軛的分拆均不含分部量2的有序分拆數(shù)與分部量大于1的有序分拆數(shù), 分部量是1,2的有序分拆數(shù), 分部量是奇數(shù)的有序分拆數(shù)之間的分拆恒等式以及組合證明, 進(jìn)一步豐富了整數(shù)分拆理論.

衷心感謝審稿專(zhuān)家提出的寶貴意見(jiàn).

[1] MacMahon P A. Combinatory Analysis: Volumes 1 [M]. Mineola, NY: Dover Publications, Inc, 1915.

[2] Andrews G E. The Theory of Partitions [M]. Cambridge: Cambridge University Press, 1998.

[3] 郭育紅, 王汝軍. 與自反的n-Color有序分拆相關(guān)的一些恒等式 [J]. 數(shù)學(xué)學(xué)報(bào)(中文版), 2016, 59(4): 535-544. (GUO Yuhong, WANG Rujun. Some Identities Related to the Self-inversen-Color Compositions [J]. Acta Mathematica Sinica (Chinese Series), 2016, 59(4): 535-544.)

[4] Shapcott C. New Bijections fromn-Color Compositions [J]. J Comb, 2013, 4(3): 373-385.

[5] Shapcott C. C-Color Compositions and Palindromes [J]. Fibonacci Quart, 2012, 50(4): 297-303.

[6] GUO Yuhong. Inverse-Conjugate Compositions with Odd Parts [J]. Ars Comb, 2017, 135: 93-102.

[7] GUO Yuhong.n-Color Odd Self-inverse Compositions [J/OL]. J Integer Seq, 2014-11-04. https://cs.uwaterloo.ca/journals/JIS/VOL17/Guo/guo9.pdf.

[8] Munagi A O. Primary Classes of Compositions of Numbers [J]. Ann Math Inform, 2013, 41： 193-204.

[9] Munagi A O. Zig-Zag Graphs and Partition Identities of A.K.Agarwal [J]. Ann Comb, 2015, 19(3): 557-566.

[10] Chinn P, Heubach S. Integer Sequence Related to Compositions without 2’s [J/OL]. J Integer Seq, 2003-07-08. https://cs.uwaterloo.ca/journals/JIS/VOL6/Heubach/heubach5.pdf.

[11] Sloane N J A. The On-line Encyclopedia of Integer Sequences [J]. Notices Amer Math Soc, 2003, 50(8): 912-915.