四元同名元素不相鄰可重復排列數的算法

史千里

(長江大學文理學院，湖北 荊州 434020)

四元同名元素不相鄰可重復排列數的算法

史千里

(長江大學文理學院，湖北 荊州 434020)

研究四元同名元素不相鄰可重復排列數F(a,b,c,d)的一般性質，獲得了排列數F(a,a,a,a)和F(a,a,c,d)的遞推公式以及F( 1,1,c,d)的計算公式。

可重復排列；同名元素不相鄰；序串

定義1設a+b+c+d=n，a,b,c,d∈Z+,a≤b≤c≤d，φ是有序串，令:

S ={φ∣φ=x1x2，…xn,φ含a個A, b個B, c個C, d個D,不含片斷AA、BB、CC、DD}

其中，φ是四元同名元素不相鄰可重復排列，令F(a,b,c,d) =∣S∣，即為排列數。

如1個主持人、1位嘉賓、3名老師和3名學生坐成一橫排，同身份的人不相鄰，求不同的排法數。

對于三元同名元素不相鄰可重復排列數F(a,b,c)(1≤a≤b≤c )，文獻[1]給出了的遞推公式。 四元同名元素不相鄰可重復排列數F(a,b,c,d)還沒有一般的算法,已有研究僅限于極特殊的個例情形[2],而這類計算又有著很重要的應用[3]。為此，筆者在獲得F(a,b,c,d)的部分一般性質基礎上，求得多種情形的遞推公式或計算公式。

令：

SA={ψ│ψ∈S,ψ左端x1≠A}

記：

|SA|=A(a,b,c,d)

可以類似地定義|SB|=B(a,b,c,d)，|SC|=C(a,b,c,d)，|SD|=D(a,b,c,d)。

定理1設1≤ a ≤ b ≤ c≤ d。則F(a,b,c,d)≥1的充分必要條件是:

d-1≤a+b+c

(1)

證明 (必要性)設F(a,b,c,d)≥1，即S≠φ, 設φ∈S，φ含d個D, 至少需要d-1個A、B、C才能使φ中沒有DD片斷，所以d-1≤a+b+c。

(充分性)設式(1)成立。只需構造一個φ∈S，則可得F(a,b,c,d)≥1。

先排a個A, b個B, c個C：

還剩余d-[c-(b-a)]=d+b-(a+c)個D。

第1段和第2段共有[a+(b-a)]×2-1=2b-1個“縫”可以插入D, 第1段開頭左側、第2段尾部右側可以各排1個D。于是，共有(2b-1)+2=2b+1個空位可以排D。由式(1)知：

(2b+1)-[ d+b-(a+c)]=(a+b+c)-(d-1) ≥0

所以，在第1,2,3段上可以把剩余的D排盡,即?φ∈S。

推論1設1≤a≤b≤c≤d,恰在a+b+2種情形下F(a,b,c,d)≥1，即:

F(a,b,c,c+j)≥1 j∈{0,1,2, …，a+b,a+b+1}

易證得以下6個引理。

引理1F(0,b,c,d)= F(b,c,d)。

F(b,c,d)的定義和算法見文獻[1]。

引理2A(0,b,c,d)=F(b,c,d)

引理3A (a,b,c,d) =A(a,c,b,d)=…

=B(b,a,c,d)=B(c,a,b,d)= …

=C(c,b,a,d)=C(b,c,a,d)=…

=D(b,c,d,a)=D(c,b,d,a)=…

引理4A(a,0,c,d)=A(a,c,0,d)=A(a,c,d,0)=A(a,c,d)

A(a,c,d)的定義和算法見文獻[1]。

引理5A(a,b,c,d)= B(a,b-1,c,d)+C(a,b,c-1,d)

+D(a,b,c,d-1) (1≤a,b,c)

引理6F(a,b,c,d)= A(a-1,b,c,d)+B(a,b-1,c,d)

+C(a,b,c-1,d)+D(a,b,c,d-1) (a,b,c≥1)

由引理5和引理6即得定理2。

定理2設a≥1，則:

A(a,b,c,d) = F(a,b,c,d)-A(a-1,b,c,d)

推論2A(1,b,c,d)=F(1,b,c,d)- F(b,c,d)

定理3若d=a+b+c+1,則：

(2)

定理4設a≥1, 則:

F(a,a,a,a)=12A(a-1,a-1,a,a)

(3)

設a≥2, 則:

F(a,a,a,a) =12[A(a-2,a-1,a,a)+4A(a-2,a-1,a-1,a)+6A(a-2,a-1,a-1,a-1)]

(4)

證明由引理1～引理6得:

F(a,a,a,a) =A(a-1,a,a,a) +B(a,a-1,a,a) +C(a,a,a-1,a) +D(a,a,a,a-1)

=4A(a-1,a,a,a)

=12A(a-1,a-1,a,a)

=12[A(a-2,a-1,a,a)+2A(a-1,a-1,a-1,a)]

其中:

A(a-1,a-1,a-1,a)=2A(a-2,a-1,a-1,a)+A(a-1,a-1,a-1,a-1)

A(a-1,a-1,a-1,a-1)=3A(a-2,a-1,a-1,a-1)

代入即得式(4)。

定理5設1≤a=b≤c≤ d，d-1≤ a+b+c，則:

F( a,a,c,d) = 2A(a-1,a, d-c) +F(a,a,d-c)-2A(a-1,a,c,d)

+A(a-1,a,c-k,d-k+1)+A(a-1,a,c-k+1,d-k)]

(5)

證明由引理1～引理6得:

F(a,a,c,d) =A(a-1,a,c,d) +B(a,a-1,c,d) +C(a,a,c-1,d) +D(a,a,c,d-1)

=2A(a-1,a,c,d) +C(a,a,c-1,d) +D(a,a,c,d-1)

=2A(a-1,a,c,d)+[A(a-1,a,c-1,d)+B(a,a-1,c-1,d)+D(a,a,c-1,d-1)]

+[A(a-1,a,c,d-1)+B(a,a-1,c,d-1)+C(a,a,c-1,d-1)]

=2A(a-1,a,c,d) +2A(a-1,a,c-1,d) +2A(a-1,a,c,d-1)

+4A(a-1,a,c-1,d-1)+2A(a-1,a,c-2,d-1)+2A(a-1,a,c-1,d-2)

+4A(a-1,a,c-2,d-2)+2A(a-1,a,c-3,d-2)+2A(a-1,a,c-2,d-3)

+C(a,a,c-3,d-3) +D(a,a,c-3,d-3)

= ……

其中：

C(a,a,c-c,d-c)=C(a,a,0,d-c)=F(a,a,d-c)

D(a,a,c-c,d-c) =D(a,a,0,d-c)=A(a-1,a,0,d-c)+ B(a,a-1,0,d-c)

=A(a-1,a,d-c)+ B(a,a-1,d-c)

=2A(a-1,a,d-c)。

代入即得式(5)。

由推論1知，F(1,1,c,d)共有4種情形：d=c,c+1,c+2,c+3。定理6和定理7分別給出了算法。

定理6設c≥1 , 則:

F( 1,1,c,c)=20c2+4

(6)

證明由定理5得:

F(1,1,c,c) =2A(0,1, 0)+F(1,1,0)-2A(0,1,c,c)

=2×1+2!-2F(1,c,c)

由文獻[1]定理5得:

F(1,c,c)=6c

F(1,j,j)=6j

F(1,j-1,j)=4(j-1)+2=2(2j-1)

所以:

定理7設c≥1, 則:

F(1,1,c,c+1)= 15c2+15c+6

(7)

F(1,1,c,c+2)=6(c+1)2

(8)

(9)

證明設d-c=t≥0，由定理1知，當且僅當t=0,1,2,3時，F(1,1,c,d)≥1。由定理5得:

F(1,1,c,d) =2A(0,1, t)+F(1,1,t)-2A(0,1,c,c+t)

=2F(1, t)+F(1,1,t)-2F(1,c,c+t)

t=1時:

F(1,1,c,c+1)=2F(1, 1)+F(1,1,1)-2F(1,c,c+1)

由文獻[1]定理5得:

F(1,c-k+1,c-k+1)=6(c-k+1)

F(1,c,c+1)=4c+2

F(1,c-k+1,c-k+2)=4(c-k+1)+2

由文獻[1]定理2得:

F(1,c-k,c-k+2)=c-k+1

所以:

= 15c2+15c+6

t=2和t=3時,可以類似地證明式(8)和式(9)。

[1]史千里.一個特殊可重復排列數的算法[J].數學的實踐與認識，2009, 39(5):207～211.

[2] 仇索.抽空法：“不相鄰”排列問題的專項工具[J].數學通訊,2014(Z3):69～71.

[3] 鐘集.若干相同元不相鄰的重復n排列的計算及應用[J].華東理工大學學報(社會科學版),1997(3):1～5.

[4] 孫淑玲，許胤龍. 組合數學引論[M]. 合肥: 中國科學技術大學出版社, 1999.

[編輯] 張濤

2016-07-28

湖北省教育廳科研技術項目(B2014281)。

史千里(1963-)，男，副教授，現主要從事數論和高等數學方面的教學與研究工作；E-mail:bamsky@126.com。

O157

A

1673-1409(2016)31-0005-04

[引著格式]史千里.四元同名元素不相鄰可重復排列數的算法[J].長江大學學報(自科版)，2016,13(31)：5～8.