Kaplansky計數(shù)命題的拓廣及應(yīng)用

唐善剛

(西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院, 四川 南充 637009)

Kaplansky計數(shù)命題的拓廣及應(yīng)用

唐善剛

(西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院, 四川 南充 637009)

應(yīng)用組合分析技巧,給出基于線排列與環(huán)形排列情形下的經(jīng)典的Kaplansky計數(shù)命題的拓廣情形，得到了兩個推廣后的新的Kaplansky計數(shù)命題.通過推廣Ménage計數(shù)問題以及組合恒等式的證明，所得結(jié)果拓展了已有文獻(xiàn)的研究結(jié)果.

Kaplansky計數(shù)命題； Ménage計數(shù)問題； 線排列； 環(huán)形排列； 組合恒等式； 容斥原理

Kaplansky計數(shù)命題在Ménage計數(shù)問題[1-5]、二重亂序的計數(shù)公式[6]、限位排列[7-13]，以及第一、二類可重環(huán)形排列[7-13]中有著廣泛的應(yīng)用，其基本形式可表述為基于線排列與環(huán)形排列情形下的組合計數(shù)命題.

文獻(xiàn)[6]將定理1，2推廣為定理3，4.

1 Kaplansky計數(shù)命題的再拓廣

進(jìn)一步將定理3,4拓廣為基于如下的線排列與環(huán)形排列情形下的組合計數(shù)命題.

證明 先假定1lt;klt;n,設(shè){ai,1,ai,2,…,ai,yi|1≤i≤s}是從全排列a1a2…an中選出的符合題意的k元組合，設(shè)段ai,1,ai,2,…,ai,yi與段a(i+1),1,a(i+1),2,…,a(i+1),yi+1之間在全排列a1a2…an中間隔的元素個數(shù)為xi+1(1≤i≤s-1)；段a1,1,a1,2,…,a1,y1在全排列a1a2…an之前的元素個數(shù)為x1；段as,1,as,2,…,as,ys在全排列a1a2…an之后的元素個數(shù)為xs+1.據(jù)此，可得如下的不定方程組,即

式(1)中:x1,xs+1≥0；xi≥λ(i=2,3,…,s)；yjgt;0(j=1,2,…,s).

據(jù)此，得到從全排列a1a2…an中選取符合題意的k個元素的組合的個數(shù)為

n.

1) 若k=1，必有s=1.顯然，此時符合題意的k個元素的組合的個數(shù)為n，且

n.

2) 若k=n時，必有s=1.顯然，此時符合題意的k個元素的組合的個數(shù)為1，且

3) 若s=1.顯然，此時符合題意的k個元素的組合的個數(shù)為n-k+1，且

綜上所述，從全排列a1a2…an中選取符合題意的k個元素的組合的個數(shù)為

λ.

證明 先假定1lt;klt;n.設(shè){ai,1,ai,2,…,ai,yi|1≤i≤s}是從⊙a(bǔ)1a2…an中選出的符合題意的k元組合，于是⊙a(bǔ)1a2…an中不屬于{ai,1,ai,2,…,ai,yi|1≤i≤s}的元素可能為aj+1,aj+2,…,aj+λ(1≤j≤n).

⊙a(bǔ)1a2…an中不屬于{ai,1,ai,2,…,ai,yi|1≤i≤s}的元素aj+1,aj+2,…,aj+λ(1≤j≤n)，其下標(biāo)j+1,j+2,…,j+λ約定為j+1,j+2,…,j+λ分別除以n所得到的最小正剩余數(shù)，例如，當(dāng)j=n-1時，元素an,an+1,an+2,…,an+λ-1即為an,a1,a2,…,aλ-1.

據(jù)此，按照如下4個步驟求解.

步驟1設(shè)從環(huán)形排列⊙a(bǔ)1a2…an中選取符合題意的k元組合為{ai,1,ai,2,…,ai,yi|1≤i≤s}，且使得aj+1,aj+2,…,aj+λ不屬于{ai,1,ai,2,…,ai,yi|1≤i≤s}的組合的個數(shù)為dj,1≤j≤n.

根據(jù)定理5，求dj等價于求如下不定方程組的整數(shù)解(x1,y1,x2,y2,…,xs,ys,xs+1)的個數(shù)，即

式(2)中：x1,xs+1≥0；xi≥λ(i=2,3,…,s)；yjgt;0(j=1,2,…,s).

步驟4根據(jù)步驟3的結(jié)果，從環(huán)形排列⊙a(bǔ)1a2…an中選取k個元素，并使得這k個元素被環(huán)形排列⊙a(bǔ)1a2…an中其余元素分隔成s段，且任何兩段之間在環(huán)形排列⊙a(bǔ)1a2…an中至少還間隔有λ個元素的組合的個數(shù)為

n.

1) 若k=1時，必有s=1.顯然，此時符合題意的k個元素的組合的個數(shù)為n，且

n.

2) 若s=1時，顯然，符合題意的k個元素的組合的個數(shù)為n，且

n.

綜上所述，從環(huán)形排列⊙a(bǔ)1a2…an中選取符合題意的k個元素的組合的個數(shù)為

k.

2 Kaplansky計數(shù)命題的應(yīng)用

Ménage計數(shù)問題是一個著名的組合學(xué)問題，由法國數(shù)學(xué)家Lucus提出，即求n對夫妻圍圓桌而坐，且男女相間夫妻不相鄰的坐法數(shù).1986年，Bogart等[1]又提出了所謂的不要求男女相間的“放松的夫妻對圍坐計數(shù)問題”.文獻(xiàn)[2-3]利用容斥原理將Ménage計數(shù)問題推廣為多維情形下的計數(shù)問題加以研究.文中將經(jīng)典的Ménage計數(shù)問題推廣為如下情形.

Ménage計數(shù)問題的拓廣如下：有n組學(xué)生，且每組學(xué)生中男、女生人數(shù)均為λ人,n組學(xué)生圍圓桌而坐.設(shè)α與β是n組學(xué)生圍圓桌而坐的兩種坐法方式,α=β當(dāng)且僅當(dāng)每個學(xué)生在α及β中與之相鄰的人組成的集合是相等的.

1) 求滿足上述約定下的n組學(xué)生男女相間圍圓桌而坐，且恰好有r組學(xué)生中的每組學(xué)生是坐在一起的坐法方式數(shù)f1(n,λ).

2) 求滿足上述約定下的n組學(xué)生男女相間圍圓桌而坐，且恰好使得其中指定的r組學(xué)生中的每組學(xué)生是坐在一起的坐法方式數(shù)f2(n,λ).

3) 求滿足上述約定下的n組學(xué)生男女相間圍圓桌而坐，且至多有r組學(xué)生中的每組學(xué)生是坐在一起的坐法方式數(shù)f3(n,λ).

4) 求滿足上述約定下的n組學(xué)生男女相間圍圓桌而坐，且至少有r組學(xué)生中的每組學(xué)生是坐在一起的坐法方式數(shù)f4(n,λ).

為行文方便起見，對圍圓桌的2λn個座位按照逆時針方向以自然順序編號，其座位號分別標(biāo)記為1,2,3,…,2λn.

2) 不妨設(shè)滿足情形1)下的k個座位的組合為{i1,i2,…,ik}，且組合{i1,i2,…,ik}必然與含有2λk個座位的組合{is,is+1,is+2,…,is+2λ-1|1≤s≤k}之間存在一一對應(yīng)的關(guān)系.將指定的某組學(xué)生男女相間安排在座位i1,i1+1,i1+2,…,i1+2λ-1上入坐的坐法方式數(shù)為2(λ!)2；而將指定的另外某組學(xué)生男女相間安排在座位is,is+1,is+2,…,is+2λ-1上入坐的坐法方式數(shù)為(λ!)2，2≤s≤k；最后，剩余的n-k組學(xué)生男女相間入坐在剩余的2λn-2λk個座位上的坐法方式數(shù)為((λn-λk)!)2.

由于圍圓桌而放置的座位是帶有標(biāo)號的，故組合{is,is+1,is+2,…,is+2λ-1|1≤s≤k}中代表座位編號的具體數(shù)字都約定為它們除以2λn后所得的最小正剩余數(shù).

顯然n組學(xué)生男女相間圍著帶有標(biāo)號的2λn個座位的圓桌而坐的坐法方式數(shù)為2((λn)!)2，即

當(dāng)k=0時,上式仍然成立.

4)fi(n,λ)即為二面體群D2λn作用于由2λn個學(xué)生男女相間圍著帶有標(biāo)號的2λn個座位的圓桌而坐的所有坐法方式構(gòu)成的集合的軌道數(shù)(1≤i≤4).運(yùn)用Burnside引理[8-13]及容斥原理[2-3,14-16]，即得定理7.

定理7推廣的Ménage計數(shù)問題的結(jié)果為

定理8證明下列組合恒等式

2) 求由數(shù)字1,2,…,n組成的不含數(shù)對(i,i+1)(i=1,2,…,n-1)的全排列的個數(shù).令A(yù)表示由數(shù)字1,2,…,n組成的所有全排列的集合，對于π∈A，數(shù)對(i,i+1)界定命題Pi(π)為Pi∶π中含有數(shù)對(i,i+1)，其中，i=1,2,…,n-1.

據(jù)此有

從而有

3 結(jié)束語

將文獻(xiàn)[6]的Kaplansky計數(shù)命題推廣至更具一般化情形下的基于線排列與環(huán)形排列下的新的組合計數(shù)命題，從理論上拓寬了經(jīng)典的Kaplansky計數(shù)命題的適用范圍；給出了從理論上推廣后的新的Kaplansky計數(shù)命題在具體組合問題中的應(yīng)用，拓展了相關(guān)文獻(xiàn)的結(jié)果.

[1] 林翠琴.組合學(xué)與圖論[M].北京:清華大學(xué)出版社,2009.

[2] 唐善剛.關(guān)于“容斥原理的拓廣及其應(yīng)用”的注記[J].山東大學(xué)學(xué)報(理學(xué)版),2012,47(10):64-69. DOI:10.6040 /j.issn． 1671-9352.2012.10.014.

[3] 唐善剛.賦權(quán)有限集上的容斥原理及應(yīng)用[J].浙江大學(xué)學(xué)報(理學(xué)版),2014,41(2):123-126.DOI:10.3785/j.issn.1008-9497.2014.02.001.

[4] 曹汝成.廣義容斥原理及其應(yīng)用[J].數(shù)學(xué)研究與評論,1988,8(4):526-530.

[5] 魏萬迪.廣容斥原理及其應(yīng)用[J].科學(xué)通報,1980,25(7):296-299.

[6] 李磊.關(guān)于幾個組合計數(shù)公式的推廣[J].工程數(shù)學(xué)學(xué)報,1996,13(4):95-98.

[7] 李喬.組合數(shù)學(xué)基礎(chǔ)[M].北京:高等教育出版社,1993.

[8] 盧開澄,盧華明.組合數(shù)學(xué)[M].4版.北京:清華大學(xué)出版社,2006.

[9] 許胤龍,孫淑玲.組合數(shù)學(xué)引論[M].2版.合肥:中國科學(xué)技術(shù)大學(xué)出版社,2010.

[10] 柯召,魏萬迪.組合論[M].北京:科學(xué)出版社,1981.

[11] 屠規(guī)彰.組合計數(shù)方法及其應(yīng)用[M].北京:科學(xué)出版社,1981.

[12] 姜建國,岳建國.組合數(shù)學(xué)[M].西安:西安電子科技大學(xué)出版社,2003.

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

[14] 唐善剛.容斥原理的拓展及其應(yīng)用[J].山東大學(xué)學(xué)報(理學(xué)版),2010,45(12):12-15.

[15] 唐善剛.容斥原理的拓展及其應(yīng)用(Ⅱ)[J].山東大學(xué)學(xué)報(理學(xué)版),2011,46(12):70-75.

[16] BENDER E A,GOLDMAN J R.Mobius inversion in combinatorial analysis[J].Amer Math Monthly,1975(82):789-802.DOI:10.3785/j.issn.1008-9497.2014.02.001.

(責(zé)任編輯： 陳志賢英文審校： 黃心中)

GeneralizationsofKaplanskyEnumeratingTheoremsandItsApplications

TANG Shangang

(College of Mathematics and Information, China West Normal University, Nanchong 637009, China)

By using combinatorial analysis we extend Kaplansky enumerating theorems are to the general conditions under a linear permutation and a circular permutation. Two generalized theorems for the Kaplansky enumerating theorems are obtained. One class of Ménage enumerating problem is extended and some combinatorial identities are proved with the generalized Kaplansky enumerating theorems. Our results generalize those of the previous studies.

Kaplansky enumerating theorem; Ménage enumeratiing problem; linear permutation; circular permutation; combinatorial identity; principle of inclusion-exclusion

10.11830/ISSN.1000-5013.201607009

O 157.1

A

1000-5013(2017)06-0892-06

2016-07-05

唐善剛(1978-)，男，副教授，主要從事組合計數(shù)方法理論及應(yīng)用的研究.E-mail:tangshangang2001@163.com.

國家自然科學(xué)基金資助項(xiàng)目(11401480)； 四川省教育廳自然科學(xué)基金重點(diǎn)項(xiàng)目(16ZA0173, 17ZA0383)