Kaplansky計數命題的拓廣及應用

唐善剛

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

Kaplansky計數命題的拓廣及應用

唐善剛

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

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

Kaplansky計數命題； Ménage計數問題； 線排列； 環形排列； 組合恒等式； 容斥原理

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

文獻[6]將定理1，2推廣為定理3，4.

1 Kaplansky計數命題的再拓廣

進一步將定理3,4拓廣為基于如下的線排列與環形排列情形下的組合計數命題.

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

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

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

n.

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

n.

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

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

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

λ.

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

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

據此，按照如下4個步驟求解.

步驟1設從環形排列⊙a1a2…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}的組合的個數為dj,1≤j≤n.

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

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

步驟4根據步驟3的結果，從環形排列⊙a1a2…an中選取k個元素，并使得這k個元素被環形排列⊙a1a2…an中其余元素分隔成s段，且任何兩段之間在環形排列⊙a1a2…an中至少還間隔有λ個元素的組合的個數為

n.

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

n.

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

n.

綜上所述，從環形排列⊙a1a2…an中選取符合題意的k個元素的組合的個數為

k.

2 Kaplansky計數命題的應用

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

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

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

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

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

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

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

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

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

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

當k=0時,上式仍然成立.

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

定理7推廣的Ménage計數問題的結果為

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

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

據此有

從而有

3 結束語

將文獻[6]的Kaplansky計數命題推廣至更具一般化情形下的基于線排列與環形排列下的新的組合計數命題，從理論上拓寬了經典的Kaplansky計數命題的適用范圍；給出了從理論上推廣后的新的Kaplansky計數命題在具體組合問題中的應用，拓展了相關文獻的結果.

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

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

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

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

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

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

[7] 李喬.組合數學基礎[M].北京:高等教育出版社,1993.

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

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

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

[11] 屠規彰.組合計數方法及其應用[M].北京:科學出版社,1981.

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

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

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

[15] 唐善剛.容斥原理的拓展及其應用(Ⅱ)[J].山東大學學報(理學版),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.

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

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-)，男，副教授，主要從事組合計數方法理論及應用的研究.E-mail:tangshangang2001@163.com.

國家自然科學基金資助項目(11401480)； 四川省教育廳自然科學基金重點項目(16ZA0173, 17ZA0383)