有重复元素的圆排列和环排列的计数问题常新德 永城职业学院 476600[内容提要]本文通过排列的周期概念的引入，利用数论中茂陛乌斯函数和欧拉函数，导出了n个不尽相异元素的圆排列数公式: 、对称圆排列数公式和计算环排列数的公式关键词：重集，周期，圆排列，对称圆排列，环排列，茂陛乌斯函数，欧拉函数对于n个完全相异元素的排列（包括圆排列、环排列）在一些书上都有介绍，但对于n个不尽相异元素的排列，特别是圆排列与环排列则介绍甚少下面我们就来讨论这个问题一．线排列为了与后面所说圆排列、环排列等的区别，我们把通常所说的排列称为线排列，不过这里考虑的是全排列[定义1] 把一些元素按一定的顺序排成一列，就叫做由这些元素排成的一个线排列，由这些元素排成的所有不同的线排列的个数称为这些元素的线排列数例1．由 1、1、1、2、2 可以排成多少个不同的五位数总数为 ）[定理1] 设S={e1·n1，e2·n2，…，ek·nk}为一个有重复元素的集合（简称重集），其中ei·ni中的ei为元素，ni为元素ei的重复数(i=1,2,3,…,k)，且n1+n2+…+ nk=n则由S的全部元素所作的线排列的总数为：证明：略。
为了下面讨论圆排列的需要，我们先来研究由S的全体元素作成的 个线排列的一些性质[定义2] 若线排列x1x2… xn可以分成完全相同的d段，则每一段称为线排列x1x2… xn的一个循环节，循环节的长度即一个循环节中元素的个数t称为线排列x1x2… xn的周期，最小的周期t称为线排列x1x2… xn的最小周期显然，每一个线排列x1x2… xn都有周期，例如取d =1,这时t= n ( d t=n )，即周期为n.用Ad代表周期为的由S的元素排成的线排列集合，（d | ni ，i=1,2,…,k），|Ad| 代表Ad中线排列的个数容易证明：[引理1] 若 d1 | d2 ，则Ad2Ad1[引理2] Ad2∩Ad1= A[d1，d2] ，其中[d1，d2]表示d1、d2的最小公倍数[引理3] (其中 d | ni , i =1,2,3,…,k. ).[定理2] 设重集 S={e1·n1，e2·n2，…，ek·nk}，且，n1,n2,n3,…,nk的最大公约数 (n1,n2,n3,…,nk) = p，若d | p，则在由S的所有元素组成的线排列的集合A1中，有： 个线排列以为最小周期其中： 为茂陛乌斯函数(见初等数论P177)，表示展布在正整数p的一切正因数上的和式。
证明：在周期为的线排列的集合Ad中，任一元素的最小周期都可以写成的形式，其中，在q=1时所对应的元素即为最小周期为的线排列，因此最小周期为的线排列的集合为（其中表示Aqd在Ad中的补集）因为： (其中r为的质因数).再由斥容原理(其中设有s个不同的质因数 r1,r2,…,rs)定理得证二．圆排列[定义3] 把一些元素按一定顺序而不论具体位置排成一圈，就叫做由这些元素排成的一个圆排列，由这些元素排成的所有圆排列的个数称为这些元素的圆排列数例2．四名穿红色衣服的小孩和四名穿黄色衣服的小孩围坐在一个旋转木马上，问可以组成多少种不同的花色？这是一个求圆排列数的问题，解答在后面给出X1X2X3XiXn※[定义4] 若圆排列可以分成完全相同的d段，则每一段称为圆排列(※)的一个循环节，循环节的长度t 称为圆排列(※)的周期，最小的周期 t称为圆排列(※)的最小周期容易证明：[引理4] 每一个最小周期为t的线排列，对应一个最小周期为t的圆排列；而每一个最小周期为t的圆排列，对应着 t个互不相同的最小周期为t的线排列[定理3] 设重集 S={e1·n1，e2·n2，…，ek·nk}，且，(n1,n2,n3,…,nk)=p，则由S的元素组成的圆排列数为：其中为欧拉函数（参见初等数论P46）。
证明：由引理4和定理2得：（其中 (见初等数论P182)例2的解：三．环排列例3．由4棵红色珠子和4棵黄色珠子可以串成多少种不同花色的珠环？这个问题与上面的例2在本质上是不同的，因为不仅旋转而且翻转也不会将一个珠环改变花色所以我们把这一问题称为环排列问题解答在后面给出）[定义5] 把一些元素按一定顺序串成一个环，就叫做由这些元素组成的一个环排列，由这些元素组成的所有环排列的个数称为这些元素的环排列数容易证明：[引理5] 一个圆排列对应一个环排列，而一个环排列对应一个翻转不变的圆排列或两个翻转改变的圆排列翻转不变的圆排列简称为对称圆排列由引理5容易证明：[定理4] 若重集S的所有元素的圆排列数为Q，其中对称圆排列数为M，则S的所有元素的环排列数为 [定理5] 在重集 S={e1·n1，e2·n2，…，ek·nk} 的所有元素组成的圆排列中，有对称圆排列当且仅当在 n1,n2,n3,…,nk 中的奇数个数不超过两个证明：设S的一个圆排列X1X2X3XiXn※的每一个元素都是在圆的n等分点上，若(※)是对称圆排列，则至少有一个对称轴，且对称轴是圆的直径在一条轴上至多有两个元素，轴两边的元素完全相同，因此除一条轴上的元素外，其余每一种元素的重数都是偶数。
Ⅰ、若这条轴上没有元素，则n1,n2,n3,…,nk全为偶数；Ⅱ、若这条轴上只有一个元素，则n1,n2,n3,…,nk中只有一个是奇数；Ⅲ、若这条轴上有两个不同的元素，则n1,n2,n3,…,nk中只有两个是奇数；Ⅳ、若这条轴上有两个相同的元素，则n1,n2,n3,…,nk全为偶数总结以上四条可知，定理5正确[定理6] 若n1,n2,n3,…,nk中至多只有两个奇数，则在重集S={e1·n1，e2·n2，…，ek·nk}的所有元素作成的圆排列中共有对称圆排列 （个）其中[x]表示x的整数部分证明：要分几种情况证明（略）例3的解：即可做成8种不同花色的珠环参考文献：闵嗣鹤，严士健《初等数论》人民教育出版社1982年9月第二版。