不盡相同元的環排列計數問題

申 紅 蓮

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

1 緒論

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

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

首先給出圓排列和環排列的定義：

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

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

2 不盡相同元的環排列

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

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

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

2) 若……