申 紅 蓮

(衡水學院 數學與計算機科學學院，河北 衡水 053000)

1 緒論

對于n個不同元素的圓排列問題，參考線排列即可得出相應的結果，比較容易實現.文獻[1-3]指出對于不盡相同元的圓排列問題，情況比較復雜，沒有固定的公式可循，一般需要具體問題具體分析，但是文獻[4]利用數論中的歐拉函數，給出了n個不盡相同元(有重復元素)的圓排列的計數公式.

本文主要通過舉例，分析了圓排列中環(huán)排列的各種情況，利用環(huán)排列和圓排列的關系，給出了環(huán)排列的公式及其證明過程，供使用者參考.

首先給出圓排列和環(huán)排列的定義：

定義1 把n個元素按一定順序排成一圈，就叫做這n個元素的一個圓排列，由這些元素組成的所有圓排列的個數稱為這些元素的圓排列數.若這些元素不盡相同時，就叫做這n個元素的不盡相同元的圓排列.

定義2 把n個元素按一定順序串成一個環(huán)，就叫做這些元素組成的一個環(huán)排列，由這些元素組成的環(huán)排列的個數稱為這些元素的環(huán)排列數.當這n個元素互異時，又稱項鏈問題或穿珠問題.

2 不盡相同元的環(huán)排列

環(huán)排列和圓排列之間存在著一定的聯(lián)系，可參考下述例題分析.

例1 將4粒相同的白色珠子，6粒相同的紅色珠子及一粒黑色珠子放在桌上，擺成一圈有幾種擺法？若用線穿成珠圈又有幾種不同的穿法？

解 1) 記 S = { 4.白 珠,6 .紅 珠, 1 .黑 珠} ，則11重集S做成線排列，有11!/4!6!= 2 310種擺法，由于每11個線排列對應著同一個圓排列，因此所求圓排列數有2310/11 = 2 10種.

2) 若穿成珠圈，即要求做環(huán)排列.本題中共有奇數粒珠子，其中黑珠是1粒.不妨把黑珠固定，其余10粒珠子做成的圓排列數為10 ! /4!6!= 210種.

在所有的圓排列(不妨以線排列表示)中，包含這樣兩種情況，為區(qū)別，以×表示白珠， O 表示紅珠：

情況一：排列×O ××× ×OO×O 和 O ×OO× ×××O×其實是一個正反面的關系，因此應認定為是同一個環(huán)排列，但在圓排列的計數中，計算2次.

情況二：排列O× O ×× ××O×O兩邊的元素和排列位置完全相同，這樣的排列可定義為對稱圓排列，在圓排列的計數中計算一次，并且此類圓排列的個數為5!/2!3!= 1 0個.

綜合上述2種情況，先在所有圓排列的個數中去掉對稱圓排列的個數，即為情況一所示的所有圓排列的個數，除以2即為情況一中所對應的環(huán)排列的個數，情況二也是環(huán)排列的情況，需要再加上，即可得所有環(huán)排列的個數，記環(huán)排列個數為N，

例2 將4粒相同的白色珠子和4顆相同的紅色珠子可以串成多少種不同花色的珠環(huán)？

解 1) 記 S = { 4.白 珠 ,4 .黃 珠}，則此8重集S所做的圓排列數可參考文獻[3]例2有10種.

2) 若穿成珠環(huán)，即要求做環(huán)排列.本題中共有偶數粒珠子.

在所有的圓排列(不妨以線排列表示)中，包含這樣2種情況，為區(qū)別，以×表示白珠，O表示紅珠：

情況一：排列×O × × OO×O 和 O× O O ××O×其實是一個正反面的關系，因此應認定為同一個環(huán)排列，但在圓排列的計數中，計算2次.

情況二：排列O× O × ×O×O兩邊的元素和排列位置完全相同，這樣的排列可定義為對稱圓排列，在圓排列的計數中計算一次，并且此類圓排列的個數為4!/2!2!= 6 個.

綜合上述2種情況，先在所有圓排列的個數中去掉對稱圓排列的個數，即為情況一所示的所有圓排列的個數，除以2即為情況一中所對應的環(huán)排列的個數，再加上情況二所對應的環(huán)排列的個數(即對稱圓排列的個數)，即為所有環(huán)排列的個數，記環(huán)排列個4數為N，

由上述2個例題可以看出，不管多重集是奇數集還是偶數集，只要分別知道圓排列和對稱圓排列的個數，按照兩種情況分析，則可得出環(huán)排列的計數公式.

定理1 若重集S的所有元素的圓排列個數為Q，其中對稱圓排列的個數為M，則S的所有元素的環(huán)排列個數為

證明 在重集S的所有元素的圓排列中，包含2種情況：第一種為非對稱圓排列的前提下圓排列1翻轉即為圓排列2的情況，第二種為對稱圓排列的情況.去掉情況二的個數，即為情況一所示的所有圓排列的個數，除以2即為情況一中所對應的環(huán)排列的個數，再加上情況二所對應的環(huán)排列的個數(即對稱圓排列的個數)，即為所有環(huán)排列的個數，記環(huán)排列個數為N，

其中圓排列公式和對稱圓排列公式可參考文獻[4].

3 總結

通過上述例題和定理，本文清楚地利用環(huán)排列和圓排列的關系，由圓排列公式和對稱圓排列公式，得到了環(huán)排列公式，并且給出了證明.在以后的計算中，可借鑒和參考使用本文的結論，直接快速有效地得到結果.

[1] 曹汝成.組合數學[M].廣州:華南理工大學出版社,2006:58-59.

[2] 鄧秀芬.組合數學中的圓排列[J].數學教學,2009(11):114,138.

[3] 羅肇華.圓排列[J/OL].[2012-07-10].http://wenku.baidu.com/view/10b202d133d4b14e8524683b.html.

[4] 陳瓊,常新德.有重復元素的圓排列和環(huán)排列的計數問題[J].商丘職業(yè)技術學院學報,2008,7(2):10-13.