不盡相同元的環(huán)排列計(jì)數(shù)問題

申 紅 蓮

(衡水學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，河北 衡水 053000)

1 緒論

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

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

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

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

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

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

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

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

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

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

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

情況一：排列×O ××× ×OO×O 和 O ×OO× ×××O×其實(shí)是一個(gè)正反面的關(guān)系，因此應(yīng)認(rèn)定為是同一個(gè)環(huán)排列，但在圓排列的計(jì)數(shù)中，計(jì)算2次.

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

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

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

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

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

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

情況一：排列×O × × OO×O 和 O× O O ××O×其實(shí)是一個(gè)正反面的關(guān)系，因此應(yīng)認(rèn)定為同一個(gè)環(huán)排列，但在圓排列的計(jì)數(shù)中，計(jì)算2次.

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

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

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

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

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

其中圓排列公式和對稱圓排列公式可參考文獻(xiàn)[4].

3 總結(jié)

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

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

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

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

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