從圓排列的相嵌到組合的枚舉

【摘要】國內外的《組合數學》中，有的還沒有討論圓排列問題，更沒有討論圓排列的相對計數法和圓排列相嵌問題.本文引入這兩種新概念，利用新發現的圓排列相嵌與線排列相嵌的關系，才完成命題的證明，解決了兩種元素的圓排列的枚舉問題，這也可以說明圓排列理論基本成熟，同時也為組合枚舉提供了一種具有理論依據的新方法，這里不做實例演示，只給出理論證明和枚舉所需的步驟.

【關鍵詞】圓排列；線排列；相嵌；相對數之和

預備知識

(A)f，g是以n的約數為變量的函數，d是主變量，k是負變量，則有：

①fnd=∑k|ndgndkgnd=∑k|ndu(k)fndk；

②∑d|nd∑k|ndu(k)fndk=∑d|n(d)fnd.

（B）a1元素有n1個，a2元素有n2個，…，ai元素有ni個，n1+n2+…+ni=N，D是n1，n2，…，ni的最大公約數，D≥1，N個元素的圓排列的總數是1N∑d|D(d)Nd!n1d!n2d!…nid!.

定義 不改變圓排列元素的順序，將所有元素平均分成元素相同，排列順序相同的若干組，并且使所分的組數是最多的，每組元素的個數稱為圓排列的周期，組數的倒數稱為圓排列的相對數；不能夠進行分組的圓排列稱為整圓排，能夠進行分組的圓排列稱為分圓排.

整圓排的周期等于元素總數，相對數是一.相對數之和與線排列的關系：多種周期、任意數量的圓排列的相對數之和（每個圓排列的元素總數均為N）乘以N，等于這些圓排列展開所產生的線排列之和，這是因為任意一個圓排列展開所產生的線排列數，等于這個圓排列的周期.

規定 圓排列展開變成線排列，要順時針展開，線排列變成圓排列，元素也要順時針擺放.

圓排列性質 （1）一個周期為k的分圓排，任意取k個連續的元素，不改變原有順序所組成的新圓排列，每次都相同，且是整圓排.（2）任意一個圓排列展開所產生的任意一個線排列，復制k個再組成一個分圓排，每一個線排列所組成的分圓排均相同，且周期與原圓排列相同.

(C)n無序拆分成k個正整數之和，即a1+a2+…+ak=n（a1≥a2≥…≥ak≥1）.n有序拆分成k個正整數之和，即a1+a2+…+ak=n有Ck-1n-1組正整數解.無序拆分與有序拆分的關系：每一個無序拆分都進行線排列，k個數字的線排列之和就是有序拆分數Ck-1n-1.

說明 本文中u（k）表示Mbius函數，(d)表示Euler函數.A（全部），B（部分）出自本人的論文，新恒等式與Mbius反演公式的新理解及其在圓排列計數中的應用［J］.數學學習與研究2009年第四期（下半月刊）.

引 言

從n+m個不同數字中，取m個數字的組合數，與n個黑球、m個紅球的線排列數是相等的，這里通過圓排列使得組合與線排列形成具有規律的對應關系.兩個同心圓，將1，2，3，…，n+m從小到大均勻的放在一個圓周上，將n個黑球m個紅球的任意一個整圓排放在另一個圓周上，整圓排每轉動一個數字的距離，m個紅球所對應的m個數字就是一個組合，轉動一周可以得到m+n個不同的組合；如果是分圓排轉動一周，得到的組合個數與分圓排的周期相等，因此任意一個圓排列轉動一周所得到的組合數，與這個圓排列所產生的線排列數是相等的.絕大多數圓排列正反面是不同的，因此很多圓排列的反面轉動一周，也可得到與周期相等的組合數，因此互為正反面的兩個圓排列，只需保留一個.由以上可知組合的枚舉，關鍵是兩種元素的圓排列的枚舉.

定義 兩個圓排列的元素個數相等，不改變元素的順序，將一個圓排列的元素，放在另一個圓排列的元素之間，且每個位置只能放一個元素，這就稱做兩個圓排列的相嵌.

命題1 d1與d2的最大公約數是r，周期分別是nd1，nd2的兩個圓排列之間不存在相同的元素，相嵌可得到周期是2nr的圓排列nrd1d2個.

理解說明 d1，d2，r是可以等于一的，n是元素個數.

證明 兩個圓排列的元素，從任意一個元素開始都可以分成完全相同的r組，r是d1，d2的最大公約數，因此兩個圓排列的元素，在所分的組數相等，每組元素完全相同的條件下，r組是最多的，所以兩個圓排列相嵌，所得到新圓排列的周期均為2nr.

兩個圓排列相嵌，可轉化成nd1個線排列與nd2個線排列的相嵌，可組成n2d1d2對線排列進行相嵌，每對線排列相嵌可得到兩個新線排列，因此得到新線排列的總數是2n2d1d2個，因而新圓排列的個數是2n2d1d2÷2nr=nrd1d2.

推論1 兩個相等的同心圓，從一點起將一圓周d1等分，另一個圓周d2等分，將一圓任意轉動，若d1與d2的最大公約數是r，則每轉動360rd1d2度就有r個重合點均分兩圓.

證明 略.

提示 d1，d2，r是可以等于一的.起點視為重合點.

將兩個圓排列放在同心圓的位置進行相嵌，在得到nrd1d2個新圓排列的過程中，有一個圓排列轉動了nrd1d2個元素的距離，nrd1d2個元素所對應的圓心角就是360n×nrd1d2=360rd1d2度.

推論2 兩組圓排列之間不存在相同的元素，且每一個圓排列的元素個數均相等，兩組圓排列展開的線排列之和分別是A和B，若一組中的每一個圓排列都與另一組所有的圓排列進行相嵌，則得到新圓排列展開的線排列之和是2AB.

證明 略.

命題2 n個黑球、m個紅球分別分成k組排列在圓周上，每組至少有一個球，并且使相鄰兩組的小球不同色，D是n，m，k的最大公約數，n≥m≥k≥1，D≥1.

（1）符合條件的圓排列展開所產生的線排列數是

n+mkCk-1n-1Ck-1m-1.

（2）符合條件的圓排列數是

1k∑d|D(d)Cnd-1，kd-1Cmd-1，kd-1.

證明 （1）n個黑球分成k組，k組可以理解成k個黑色數字，由有序拆分可知k個黑色數字的線排列之和是Ck-1n-1，m個紅球分成k組，k個紅色數字的線排列之和是Ck-1m-1，紅色數字的圓排列與黑色數字的圓排列相嵌，可轉化成Ck-1n-1Ck-1m-1對線排列相嵌，每對線排列相嵌可得到兩個新線排列，新線排列數是2Ck-1n-1Ck-1m-1，每個新線排列的數字有2k個，因此新圓排列的相對數之和是1kCk-1n-1Ck-1m-1，任意一個新圓排列的數字，用相應的小球取代，這兩個圓排列的相對數是相等的.因此，n個黑球m個紅球的圓排列，相對數之和也是1kCk-1n-1Ck-1m-1，即有符合條件的線排列數是n+mkCk-1n-1Ck-1m-1.

（2）令d是n，m，k的公約數，nd個黑球分成kd組，kd個黑色數字的線排列之和是Cnd-1，kd-1，md個紅球分成kd組，kd個紅色數字的線排列之和是Cmd-1，kd-1，黑色數字的線排列與紅色數字的線排列相嵌，可得到2kd個數字的線排列2Cnd-1，kd-1Cmd-1，kd-1個.

令h是Dd的一個約數，函數MDdh表示2kd個數字，周期是2kdh的圓排列的個數，函數fDd表示2kd個數字的線排列之和，則有：

fDd=∑h|Dd2kdhMDdh

=2Cnd-1，kd-1Cmd-1，kd-1.①

令gDdh=2kdhMDdh，當h=1時，gDd=2kdMDd，由上面的題設可知MDd表示2kd個數字的整圓排的個數，由圓排列的性質可知MDd也可表示2k個數字周期是2kd的圓排列的數量，2k個數字的圓排列總數是∑d|DMDd，由①式可得

fDd=∑h|DdgDdh

gDd=∑h|Ddu(h)fDdh=2kdMDd

MDd=d2k∑h|Ddu(h)fDdh

∑d|DMDd=∑d|Dd2k∑h|Ddu(h)fDdh

=12k∑d|Dd∑h|Ddu(h)fDdh=12k∑d|D(d)fDd

=1k∑d|D(d)Cnd-1，kd-1#8226;Cmd-1，kd-1.

因2k個數字的圓排列，與n個黑球m個紅球的圓排列是一一對應的關系，因此上式也可以表示兩種小球的圓排列數.

理解說明 命題2要求n≥m≥k≥1，k的所有可取的值是：1，2，…，m，因此∑mk=1n+mkCk-1n-1Ck-1m-1是n+m個小球的線全排列，∑mk=11k∑d|D(d)Cnd-1，kd-1Cmd-1，kd-1是n+m個小球的圓全排列，因而有下面兩個等式.

圓全排列展開的線排列之和等于線全排列，是圓排列的理論基礎，在本文所提到的論文中，也有一點論述；命題二的證明還是在這個基礎上所進行的，每個無序折分都有一組圓全排列和一組線全排列，所有無序折分的圓全排列之和與線全排列之和，也符合理論基礎的要求，推論中第二個等式的成立，驗證了這個理論基礎的正確性，同時也說明了對圓排列一些基本特性的認識，絕大多數是正確的，因此這個等式的出現是圓排列理論成熟的標志.

推論 （1）Cmn+m=(n+m)∑mk=11kCk-1n-1Ck-1m-1(n≥m).

（2）1n+m∑d|(n，m)(d)Cn+md，md=

∑mk=11k∑d|(n，m，k)(d)Cnd-1，kd-1#8226;Cmd-1，kd-1(n≥m).

枚舉步驟

（1）用黑色筆寫出x1+x2+…+xk=n的無序拆分，每一個無序拆分就是k個黑色數字，并標出每個無序拆分的線排列數，只有當所有的線排列之和等于Ck-1n-1時，才說明無序拆分沒有多寫也沒有少寫.

（2）將線排列數相等的無序拆分歸為一類，只要寫出一個無序拆分的所有圓排列，這一類無序拆分的圓排列，都可以參照很容易寫出，兩個互為正反面的圓排列只需保留一個.

（3）同理，用紅色筆寫出y1+y2+…+yk=m的無序拆分，并寫出每一個無序拆分的圓排列，兩個互為正反面的圓排列只需保留一個.

（4）每個黑色數字的圓排列，與所有紅色數字的圓排列相嵌，每對圓排列相嵌所產生新圓排列的個數由命題1確定.

①兩個正反面不同的圓排列相嵌，正面與正面相嵌完成以后，再進行一輪正反面相嵌，所得到的每一個新圓排列都表示兩個圓排列.②一個正反面不同的圓排列，與一個正反面相同的圓排列相嵌，只需正面與正面相嵌，所得到的每一個新圓排列都表示兩個圓排列.③兩個正反面相同的圓排列相嵌，只需正面與正面相嵌，所得到的每一個新圓排列，只表示一個圓排列，存在互為正反面的圓排列，有的也存在正反面相同的圓排列.

（5）黑色數字、紅色數字的每一個圓排列，黑色數字是幾就用幾個黑球取代，紅色數字是幾就用幾個紅球取代，再利用引言中的方法操作，就可以得到相對應的組合.

注意事項 任意一個正反面不同的圓排列，一定存在一個圓排列是它的反面，這兩個圓排列反面與反面合在一起，可以做到所有相同的元素所處的位置也相同.

若一個整圓排正反面是相同的，圓周上的元素以一條直徑相對稱，且對稱位置的元素是相同的.如果把這個整圓排展開，任意取一個線排列復制k個，再組成一個分圓排，這個分圓排正反面也是相同的.在圓全排列中存在正反面相同的圓排列，最多只能有兩種元素的個數是單數.

【參考文獻】

［1］馬光思.組合數學［M］.西安電子科技大學出版社，2002.

［2］盧開澄，盧華明.組合數學［M］.北京：清華大學出版社，2006.

［3］［美］格里馬迪（Grimaldi，R）.林永鋼譯.離散數學與組合數學［M］.北京：清華大學出版社，2007.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文