關(guān)于正整數(shù)不含分部量2的有序分拆的幾個(gè)組合雙射

郭育紅， 王汝軍

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

關(guān)于正整數(shù)不含分部量2的有序分拆的幾個(gè)組合雙射

郭育紅， 王汝軍

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

利用正整數(shù)有序分拆的共軛分拆, 分別給出了偶數(shù)2k、奇數(shù)2k+1和正整數(shù)n的不含分部量2 的自反的有序分拆數(shù)的遞推關(guān)系式的組合雙射證明. 此外, 還給出了NAGI關(guān)于正整數(shù)n不含分部量 2的有序分拆數(shù)的一個(gè)恒等式的不同組合雙射.

正整數(shù)的有序分拆;共軛分拆;自反的有序分拆;組合雙射;關(guān)系式

Journal of Zhejiang University(Science Edition), 2017,44(3):261-265

0 引 言

1919年，MACMAHON[1]首次定義了正整數(shù)的有序分拆，即把正整數(shù)n表示成一些正整數(shù)的有序和,其中的每一項(xià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的8個(gè)有序分拆是: (4), (3,1), (1,3), (22), (12,2), (1,2,1), (2,12), (14). MACMAHON[1]給出了有序分拆的一些性質(zhì)和表示圖, 稱為Zig-Zag graph, 類似于無序分拆的Ferres graph,即將有序分拆每個(gè)分部量ni依次用一行含有ni個(gè)的點(diǎn)來表示,但要求下一行的第1個(gè)點(diǎn)與上一行的最后一個(gè)點(diǎn)對齊.例如分拆(6,3,1,2,2)的Zig-Zag graph見圖1.

利用有序分拆的Zig-Zag graph給出該分拆的共軛分拆,即將Zig-Zag graph從左向右按列來讀. 則圖 1按列讀產(chǎn)生的有序分拆 (15, 2, 1, 3, 2, 1) 就是分拆 (6, 3, 1, 2, 2) 的共軛分拆, 它們互為共軛.

圖1 Zig-Zag 圖Fig.1 Zig-Zag graph

MUNAGI[2-3]給出了包括Zig-Zag graph在內(nèi)的5種求有序分拆的共軛分拆方法,本文只介紹direc detection of conjugates(簡稱DD)法, 是一種比較寬泛直接的表示法, 即正整數(shù)的任意一個(gè)有序分拆通常有2種形式:

(1)C=(1a1,b1, 1a2,b2, 1a3,b3，…),a1>0,ai≥0,i>1;bi≥2,i≥1;

(2)E=(b1, 1a1,b2, 1a2,b3, 1a3, …),ai≥0,bi≥2.

這里將有序分拆C的共軛分拆記為C′,于是上述2種形式的有序分拆對應(yīng)的共軛分拆分別為：

(3)C′=(a1+1, 1b1-2,a2+2, 1b2-2,a3+2，…);a1>0,ai≥0,i>1;bi≥2,i≥1;

(4)E′=(1b1-1,a1+2, 1b2-2,a2+2, …),ai≥0,bi≥2.

例如，(1,3,4,13,2,12,6)的共軛分拆是

(1+1,13-2,0+2,14-2,3+2,12-2,2+2,16-1)=

(2,1,2,12,5,4,15).

利用有序分拆的共軛可給出一些分拆恒等式的組合雙射證明.

文獻(xiàn)[4]討論了正整數(shù)不含分部量2的有序分拆, 給出了一系列計(jì)數(shù)結(jié)果. 包括正整數(shù)不含分部量2的自反的有序分拆問題. 正整數(shù)自反的有序分拆的定義如下:

定義1[1]如果正整數(shù)n的一個(gè)有序分拆的分部量從左向右讀和從右向左讀相等, 則這個(gè)分拆叫自反的有序分拆.

例如, (1,3,2,5,2,3,1)就是17的一個(gè)自反的有序分拆.

本文將利用正整數(shù)有序分拆的共軛分拆給出文獻(xiàn) [4] 中涉及的關(guān)于正整數(shù)不含分部量2的自反的有序分拆的幾個(gè)組合雙射證明. 文獻(xiàn)[2] 給出了定理1的遞推關(guān)系證法, 下文將給出該定理的組合雙射證明.

定理1[2]正整數(shù)n的分部量2在左端或右端最多出現(xiàn)一次有序分拆數(shù)等于正整數(shù)n+1不含分部量2的有序分拆數(shù).

1 主要結(jié)果及證明

文獻(xiàn)[4]給出了下面關(guān)于自反的有序分拆的結(jié)果.

文獻(xiàn)[4]給出了一種從中間分部量考慮累加的證法，本文則給出更直接的組合雙射證明.

證明 (1) 當(dāng)n=2k時(shí),將n的不含分部量2的自反的有序分拆分成2種類型:

(A)分部量的個(gè)數(shù)為偶數(shù);

(B)分部量的個(gè)數(shù)為奇數(shù).

在(A)類中, 對于任何一個(gè)自反的有序分拆,由于分部量的個(gè)數(shù)是偶數(shù), 于是以中間相同的2個(gè)分部量為準(zhǔn), 保留第1個(gè), 刪掉第2個(gè)及其右邊的所有分部量, 然后在右端添上分部量1, 就得到k+1的右端分部量為1的不含分部量2的有序分拆. 反之亦然.

在(B)類中, 由于分拆的分部量個(gè)數(shù)是奇數(shù), 這時(shí), 顯然中間的分部量為大于2的偶數(shù)2s,s>1. 將中間分部量除以2, 然后刪掉右邊的所有分部量, 得到一個(gè)右端分部量為s的分拆, 再用s+1代替s, 就得到k+1的右端分部量是大于1的不含分部量2的有序分拆. 反之亦然.故

(2)當(dāng)n=2k+1時(shí), 也將n的不含分部量2的自反的有序分拆分成2種類型來考查:

(C)中間分部量是3;

(D)中間分部量不是3.

在(C)類中, 將任何一個(gè)分拆的中間分部量3連同其右邊的分部量都刪掉, 就得到k-1的不含分部量2的有序分拆.

顯然上述是一一對應(yīng)的, 故有

證畢.

由上述證明易得以下推論.

推論1 偶數(shù)2k,k>1的分部量的個(gè)數(shù)是偶數(shù), 且不含分部量2的自反的有序分拆數(shù)等于k的不含分部量2的有序分拆數(shù).

文獻(xiàn) [4]給出了關(guān)于正整數(shù)n的不含分部量2的有序分拆數(shù)的遞推關(guān)系:

于是自然地有以下遞推關(guān)系.

顯然, 偶數(shù)的不含分部量2的自反的有序分拆數(shù)也滿足以下遞推關(guān)系式.

.

證明 將2k,2k-4的不含分部量2的自反的有序分拆分成以下3類:

(A)2k的首末兩端分部量都是1的分拆;

(B)2k的首末兩端分部量都是3的分拆;

(C)2k的首末兩端分部量都是大于3的分拆, 以及2k-4的分拆.

對于(A)類中的任一個(gè)分拆, 刪掉首末兩端的分部量1, 得到2k-2的不含分部量2的自反的有序分拆. 反之亦然.

對于(B)類中的任一個(gè)分拆, 刪掉首末兩端的分部量3, 得到2k-6的不含分部量2的自反的有序分拆. 反之亦然.

對于(C)類中的2k的任一個(gè)分拆, 設(shè)首末兩端的分部量d,d>3, 這時(shí)用d-1代替d, 于是得到2k-2的首末兩端的分部量大于2的分拆, 即得到2k-2的首末兩端的分部量不等于1的不含分部量2的自反的有序分拆; 對于2k-4任意一個(gè)不含分部量2的自反的有序分拆,給該分拆的首末兩端分別添上分部量1, 就得到2k-2的首末兩端的分部量等于1的分拆. 故(C)類中的分拆對應(yīng)2k-2的所有不含分部量2的自反的有序分拆. 反之亦然.

綜上,有

即

證畢.

下面給出該關(guān)系式的組合雙射證明.

證明 由于考查的是奇數(shù)的自反的有序分拆,故分部量的個(gè)數(shù)是奇數(shù), 且中間分部量也是奇數(shù).于是將2k+1的不含分部量2的自反的有序分拆分成2類:

(A)中間分部量不等于3;

(B)中間分部量等于3.

在(A)類中, 對于2k+1的任意一個(gè)自反的有序分拆, 設(shè)中間分部量是d, 于是用d-1代替d, 這時(shí)若d=1, 則得到2k的分部量是偶數(shù)的自反的有序分拆; 若d≠1, 則得到2k的分部量是奇數(shù)的自反的有序分拆. 反之, 對于2k的任何一個(gè)分部量的個(gè)數(shù)是偶數(shù)的自反的不含分部量2的有序分拆,在中間添加分部量+1, 可得2k+1的中間分部量是1的自反的不含分部量2的有序分拆; 對于2k的任何一個(gè)分部量的個(gè)數(shù)是奇數(shù)的自反的不含分部量2的有序分拆,此時(shí)中間分部量是偶數(shù),給中間分部量+1,可得2k+1的中間分部量不等于1的奇數(shù)的自反的不含分部量2的有序分拆. 這樣就得到了2k+1的所有不含分部量2的自反的有序分拆.

在(B)類中, 由于中間分部量是3,于是中間3個(gè)分部量組成分拆(s,3,s),這里s≠2.依據(jù)中間的分拆(s,3,s),將(B)類中的分拆又分為以下2種類型考慮:

(a)中間的分拆(s,3,s)中s>1;

(b)中間的分拆(s,3,s)中s=1.

對于(a)類中的任一個(gè)分拆, 求該分拆的共軛分拆, 仍得到分部量個(gè)數(shù)是奇數(shù)的自反的分拆, 這是因?yàn)槿粼O(shè)正整數(shù)n的有序分拆的分部量個(gè)數(shù)為t, 則其共軛分拆的分部量個(gè)數(shù)為n-t+1. 且此時(shí)得到的共軛分拆的中間3個(gè)分部量組成的分拆必然是(2,1,2),于是刪掉中間的分拆(2,1,2), 可得2k-4的分部量個(gè)數(shù)為偶數(shù)的自反的有序分拆, 然后再求該分拆的共軛, 可得2k-4的分部量個(gè)數(shù)為奇數(shù)的不含分部量2的自反的有序分拆.

反之, 對于2k-4的分部量個(gè)數(shù)為奇數(shù)的任一個(gè)不含分部量2的自反的有序分拆, 先求其共軛, 得到分部量是偶數(shù)的分拆, 再在中間添上分拆(2,1,2), 然后求所得到的2k+1的分拆的共軛分拆, 可得2k+1的中間分部量為3的自反的分拆.

于是, (a)類分拆對應(yīng)2k-4的分部量個(gè)數(shù)為奇數(shù)且不含分部量2的自反的有序分拆.

在(b)類中, 直接刪掉中間分拆(1,3,1), 則得到2k-4的分部量個(gè)數(shù)為偶數(shù)的不含分部量2的自反的有序分拆. 反之, 對于2k-4的分部量個(gè)數(shù)為偶數(shù)的不含分部量2的自反的有序分拆, 中間添上分拆(1,3,1)，可得2k+1的中間分拆是(1,3,1)的相應(yīng)有序分拆.

綜上, (B)類中的分拆對應(yīng)2k-4的所有不含分部量2的自反的有序分拆.故有

證畢.

下面用例子說明上述組合雙射.

例1 17的分拆(4,3,3,3,4),(1,1,4,1,3,1,4,1,1)與12的分拆(4,4,4), (1,1,4,4,1,1)之間的對應(yīng)關(guān)系如下:

.

證明 將n的不含分部量2的自反的有序分拆分成2類:

(A)首末兩端的分部量等于1;

(B)首末兩端的分部量大于1, 包括只含一個(gè)分部量的情形.

對于(A)類中的任何一個(gè)n的不含分部量2的自反的有序分拆, 刪掉首末兩端的分部量1, 就得到n-2的不含分部量2的自反的有序分拆. 反之, 對于n-2的任何一個(gè)不含分部量2的自反的有序分拆, 在首末兩端添上分部量1,則得到n的首末兩端分部量是1的自反的不含分部量2的有序分拆.

對(B)類分拆, 又可分為2種類型考慮:

(a)n為偶數(shù);

(b)n為奇數(shù).

在(a)類中考慮以下2種情形:

情形1： 分部量的個(gè)數(shù)是奇數(shù), 這時(shí)中間分部量是偶數(shù), 由于不含分部量2, 故中間分部量為大于2的偶數(shù), 于是將中間分部量-3, 得到n-3的首末兩端分部量均大于1的相應(yīng)分拆. 反之亦然.

情形2： 分部量的個(gè)數(shù)是偶數(shù), 此時(shí)先求該分拆的共軛,再將得到的共軛分拆的中間3個(gè)分部量分別-1,可得n-3的首末兩端分部量都為1的相應(yīng)分拆. 反之亦然.

在(b)類中亦考慮2種情形:

情形1： 中間分部量為大于1的奇數(shù), 這時(shí)將中間分部量-3, 得到n-3的首末兩端分部量都大于1的相應(yīng)分拆. 反之, 對于n-3的首末兩端分部量都大于1的分拆, 當(dāng)分部量的個(gè)數(shù)為偶數(shù)時(shí), 中間添分部量3; 當(dāng)分部量的個(gè)數(shù)為奇數(shù)時(shí), 中間分部量+3, 可得n的中間分部量、首末兩端分部量均大于1的相應(yīng)分拆.

情形2： 中間分部量是1, 這時(shí)先求該分拆的共軛, 再將得到的共軛分拆的中間3個(gè)分部量分別-1, 就得到n-3的首末兩端分部量都為1的相應(yīng)分拆. 反之亦然. 特別地, 對于分拆(k,1,k), 對其共軛分拆(1k-1,3,1k-1)的中間3個(gè)分部量分別-1, 得到分拆(1k-2,3,1k-2),然后將中間的分部量2再分拆成1+1, 得到n-3的只含有分部量1的分拆.

反之,n-3只有分部量1的分拆對應(yīng)n的分拆(k,1,k).

證畢.

下面用例子來說明上述證明中(B)類的對應(yīng)關(guān)系.

定理1的組合證法 將正整數(shù)n+1的不含分部量2的分拆分為以下4類:

(A)最右端的分部量等于1;

(B)最右端的分部量等于3;

(C)最右端的分部量等于5;

(D)最右端的分部量大于3,但不等于5.

對于(A)類中的分拆,將右端的分部量1刪掉,就得到了n的不含分部量2的分拆. 反之亦然.

對于(B)類中的分拆, 將右端的分部量3減去1, 就得到n的最右端分部量是2的分拆.反之, 對于n的右端分部量是2的分拆, 給右端分部量+1就得到n+1的只出現(xiàn)1個(gè)分部量2在右端的分拆.

對于(C)類中的分拆,將右端的分部量5分拆成2+1+2, 然后刪掉分部量1, 并將2個(gè)2分別放在去掉分部量5的分拆的首末兩端, 得到n的首末兩端分部量都為2的分拆. 反之亦然.

對于(D)類中的分拆, 將右端的分部量d分拆成2+t, 并分別將2和t-1放在去掉分部量d的分拆的左右兩端, 得到n的僅左端是分部量2的分拆. 因?yàn)閐>3,d≠5,故t-1≠2. 反之，n僅左端是分部量2的分拆, 將其左端的分部量與右端的分部量相加再+1后放在右端, 則得到n+1的右端分部量為大于3且不等于5的分拆.證畢.

[1]MACMAHONPA. Combinatory Analysis：Vol 1 [M]. Cambridge: Cambridge University Press,1915.

[2] MUNAGI A O. Primary classes of compositions of numbers [J]. Annales Mathematicae et Informaticae,2013,41:193-204.

[3] MUNAGI A O. Zig-Zag graphs and partitions identities of A.K. Agarwal [J]. Annals of Combinatorics,2015,19(3):557-566.

[4] CHINN P, HEUBACH S. Integer sequence related to compositions without 2’s [J]. Journal of Integer Sequences,2003(6): Article 03.2.3.

Several combinatorial bijections about compositions without 2’s of positive integers.

GUO Yuhong, WANG Rujun

(SchoolofMathematicsandStatistics,HexiUniversity,Zhangye734000,GansuProvince,China)

Using the conjugate of compositions, we present combinatorial bijective proofs of the recurrence relation of the self-inverse compositions without 2’s of even 2k, 2’s of odd 2k+1, and without 2’s of positive integern, respectively. In addition, we also obtain the combinatorial bijection of an identity which was obtained by MUNAGI relating to the number of the compositions without 2’s of positive integern. The methods used in this paper are different from the proofs of MUNAGI.

compositions of positive integer; the conjugate of compositions; the self-inverse compositions; combinatorial bijection; relation

2015-11-02.

國家自然科學(xué)基金資助項(xiàng)目(11461020).

郭育紅(1970-)，ORCID：http://orcid.org/0000-0002-1403-2033，女，碩士，教授，主要從事組合數(shù)學(xué)研究，E-mail：gyh7001@163.com.

10.3785/j.issn.1008-9497.2017.03.002

O 157

A

1008-9497(2017)03-261-05