(k,q)平坦數(shù)列研究

朱堯興

(南京鐵道職業(yè)技術(shù)學院蘇州校區(qū),江蘇蘇州215137)

從1到n的n個自然數(shù)進行排列,可以有各種各樣的排列。設(shè)S={1,2,3,…,n},將這n個數(shù)排成一環(huán)形數(shù)列:a0,a1,a2,a3,…,an-1,ai∈S,記 Ai=ai+ai+1+…+ai+k-1,其中i+k-1(mod n),0≤i≤n-1,值達到最小值,記作LS(n,k,q),那么稱此排列為(k,q)-平坦數(shù)列。顯然,這樣的排列與n,k和q都有關(guān)系。例如,n=5時,有12種不同的環(huán)形排列,其中LS(5,2,2)=184,LS(5,3,2)=409,LS(5,3,3)=3753,非常巧合的是,達到這些下限值的排列均為:1,5,2,3,4。對于一般的n,k和q,下面筆者給出了一些性質(zhì)。

1 (k,q)-平坦數(shù)列的幾個性質(zhì)

性質(zhì)1(平凡性) 對于任意的排列,有:

由定義可容易得到上述性質(zhì)。

性質(zhì)2(單調(diào)性) 如果排列C使和值S(n,k,q)達到LS(n,k,q),那么該排列必也能達到LS(n,k,q+1),反之亦然,對于q＞1,k＞1,n＞3。

證明 設(shè)排列C:a0,a1,a2,a3,…,an-1是取得LS(n,k,q)的排列,那么對于其他任意的排列C′:a′0,a′1,a′2,a′3,…,a′n-1 都有于 A′i,Ai ≥1,i=0,1,…,n-1,成立。反之亦然。

性質(zhì)3(周期性) 如果排列C使和值S(n,k,q)達到LS(n,k,q),那么必也能達到LS(n,n+k,q),反之亦然。

證明 設(shè)排列C:a0,a1,a2,a3,…,an-1是取得LS(n,k,q)的排列,那么對于其他任意的排列C′:a′0,a′1,a′2,a′3,…,a′n-1都有:

下面計算:

則:

性質(zhì)4(互補性) 當q=2時,如果排列C使和值S(n,k,2)達到LS(n,k,2),那么必也能達到LS(n,n-k,2),反之亦然。

證明 設(shè)排列C:a0,a1,a2,a3,…,an-1是取得LS(n,k,2)的排列,那么對于其他任意的排列C′:a′0,

即該排列也使達到LS(n,n-k,2)值。

2 LS(n,2,2)的值及其對應的排列

當q=2,k=2時:

下面來選取適當?shù)呐帕惺節(jié)M足式(1),從而使值達到LS(n,2,2):

從n開始考慮,則n的左右兩側(cè)分別取1和2,這樣能滿足(1)的條件(而且是唯一的),然后在1的左側(cè)取(n-1),2的右側(cè)取(n-2),同樣滿足條件 (1),如果換成其他的數(shù),則不能滿足條件 (1),所以這是最合適的。依次地以式(1)為條件選取數(shù),直至結(jié)束,由這樣的取法可知是滿足式 (1)的唯一排列 (如圖1)。

圖1 排列圖

容易計算:

其中,當n為奇數(shù)時,ε=1;當n為偶數(shù)時ε=2。

3 k＞2,q=2值的部分結(jié)果

對于k＞2,q=2的一般情形,尚未有結(jié)果,筆者通過計算機計算了部分情形,如表1。

表 1 k＞2,q=2的部分結(jié)果

由表1可知,當n增大時,達到最小值的排列不唯一。顯然,隨著n的增加,計算機搜索的量飛速增長,因此探求一般的排法,很有價值。

[1]曹汝成.組合數(shù)學 [M].廣州:華南理工大學出版社,2002.

[2]Brualdi R A.組合數(shù)學 [M].馮舜璽 等譯.北京:機械工業(yè)出版社,2002.