有黄绿红三种颜色的珠子各 4、4、1个。用它们穿成 9 颗珠子的手串，有多少种组合？

TSC999

下面是常新德公式对于颜色数 m=4，各色珠子数分别是 1、1、1、3 时的计算程序代码：

1. m = 4; n[1] = 1; n[2] = 1; n[3] = 1; n[4] = 3; Subscript[S, n] = \!\(
   
2. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(m\)]\(n[i]\)\);
   
3. Q = (Sum[EulerPhi[d] *(Subscript[S, n]/d)!/\!\(
   
4. \*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(m\)]\(\((
   
5. \*FractionBox[\(n[i]\), \(d\)])\)!\)\), {d,
   
6.      Divisors[GCD[n[1], n[2], n[3], n[4]]]}])/Subscript[S,
   
7.   n]  (*圆排列数*)
   
8. M = (\!\(
   
9. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(m\)]\(\[LeftFloor]
   
10. \*FractionBox[\(n[i]\), \(2\)]\[RightFloor]\)\))!/\!\(
    
11. \*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(m\)]\(\[LeftFloor]
    
12. \*FractionBox[\(n[
    
13.        i]\), \(2\)]\[RightFloor]!\)\)(*圆排列中的对称排列数，\[LeftFloor]n[i]/2\
    
14. \[RightFloor]表示取整 *)
    
15. \[CapitalPhi] = (Q + M)/2(*环排列数*)
    
16. \[CapitalPhi] = \[LeftFloor](Q + M)/2\[RightFloor] (*环排列数取整*)

复制代码

计算结果是  Q=20， M=1，Φ=(Q+M)/2=21/2，取整后等于 10。

补充内容 (2021-7-9 09:30):
程序运行结果等于 10。与公式算的取整后结果相同。

TSC999

下面是用改正错误后的程序进行计算，并与常新德公式计算结果对比。有时二者完全相同，但有时二者不一样，需要判定是哪个有错。例如下面的例子：

下面是四色珠子，黄色 1 颗、蓝色 1 颗、绿色 2 颗、红色 3 颗。手串共由这 7 颗珠子穿成。

按程序计算，共有 30 种花色如下图所示。但是按照常新德的公式计算，却有 31 种花色。问题来了，是公式错了还是程序错了？



上图中有没有花色重复的？ 有没有遗漏的？

下面是程序计算和常新德公式计算，程序代码放在一起了。
有个疑问，公式计算中，算出了有 2 个圆排列是对称的，结果就折算成了 1 个环排列。我咋看不出哪个环排列是对称的？

1. Clear["Global`*"];   
   
2. m = 4; n[1] = 1; n[2] = 1; n[3] = 2; n[4] = 3;
   
3. Subscript[S, n] = \!\(
   
4. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(m\)]\(n[i]\)\);
   
5. ss = {};     (* 所有的方案数列表 *)
   
6. a = Permutations[{"黄", "蓝", "绿", "绿", "红", "红", "红"}, {Subscript[S,
   
7.    n]}]; (* Subscript[S, n] 个有重复元素的全排列 *)
   
8. L = Length[a];       (* 共有多少种线排列？ *)
   
9. k = 0;
   
10. While[L > 0,
    
11.   s = a[[1]];  (* 候选方案*)
    
12.   ss = Append[ss, s];
    
13.   s1 = Reverse[s];  (* 候选方案反排*)
    
14.   Do[If[a[[i]] == s || a[[i]] == s1, a[[i]] = {}], {i, 2, L}]; (*
    
15.   s 左移，s1右移之前，先筛一次 *)
    
16.   Do[s = RotateLeft[s]; s1 = RotateRight[s1]; (* s 左移一位，并存到 s 中;
    
17.    s1右移一位，并存到 s1 中*)
    
18.    Do[If[a[[i]] == s || a[[i]] == s1, a[[i]] = {}], {i, 2, L}];
    
19.    , {i, 1, Subscript[S, n] - 1}];     (*
    
20.   s每左移一位、s1每右移一位，与其余的比较，若有一个是相同的，将那个其余清空。共筛 Subscript[S, n] 次 *)
    
21.   a = DeleteCases[a, {}]; (* 去掉 a 中的所有空集 *)
    
22.   a = Delete[a, 1];    (* 去掉 a 中的候选方案 a[[1]] 后的 a 列表 *)
    
23.   L = Length[a];       (* 筛一轮后的 a 还有多少种线排列？ *)
    
24.   k = k + 1;
    
25.   If[L == 0, Print[ss, " 所有花色方案展示，方案数 = ", k]];
    
26.   ];
    
27. (*以下是按常新德公式计算*)
    
28. Q = Sum[EulerPhi[d] *(Subscript[S, n]/d)!/\!\(
    
29. \*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(m\)]\(\((
    
30. \*FractionBox[\(n[i]\), \(d\)])\)!\)\), {d,
    
31.    Divisors[GCD[n[1], n[2], n[3], n[4]]]}]/Subscript[S, n](*圆排列数*)
    
32. M = (\!\(
    
33. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(m\)]\(\[LeftFloor]
    
34. \*FractionBox[\(n[i]\), \(2\)]\[RightFloor]\)\))!/\!\(
    
35. \*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(m\)]\(\[LeftFloor]
    
36. \*FractionBox[\(n[i]\), \(2\)]\[RightFloor]!\)\)(*圆排列中的对称排列数*)
    
37. \[CapitalPhi] = (Q + M)/2(*环排列数*)
    
38. 
    

复制代码

上面程序运行结果是： 程序算出环排列数为 30，它们的具体排列方案见上图。常新德公式计算圆排列数为 Q = 60 种，其中对称排列的为  M = 2 种，所以环排列数  Φ =(Q+M)/2 = 31 种，比程序算的多了一种。

我看不出来存在 2 种对称的圆排列，如果有，它是什么模样的？ 黄珠 1 颗、蓝珠 1 颗、绿珠 2 颗、红珠 3 颗。它们的圆排列咋能有对称的呢？ 哪位网友发现有对称的，请告知一下。

补充内容 (2021-7-15 08:57):
最终发现程序没错，常新德公式也没错，错在我马虎了，没有认真看常新德老师的论文。各色珠子个数有奇有偶，若奇数个数大于 2 则 M=0，不存在对称圆排列，不用按公式计算了。当奇数个数是0、1、2 时才按公式计算。

TSC999

把一些计算结果汇总，放在一张表格中看，结论就一目了然了。

从下表可知，无论穿成手串的珠子颜色有几种，每一种颜色的珠子数目要么是奇数，要么是偶数，但是如果奇数多于 2 个，常新德公式计算结果就会出错。这一点，常老师在其论文中已有过说明。



结论就是：

    ① 本帖中的程序计算结果是可以信赖的。这个程序对于珠子数目中有多少个奇数没有限制。

    ② 常新德的公式尚存在一定缺陷，有继续进一步研究并对其进行修正的必要。这一项工作，有待大侠们去努力。

TSC999

据网友 “数学青年” 提供的信息， 民国时期我国著名的数学家和教育家傅种孙曾于 1942 年完全解决了这一问题， 即：

设有 \(m\) 种颜色的珠子，每种颜色分别有 \(n_1，n_2，…，n_m\) 颗，总共有 \(n = n_1+n_2+…+n_m \) 颗。若用这些珠子穿成一个圆环，问有多少种穿法?

从网上查到，现在武汉大学图书馆馆藏文献目录中仍有傅种孙教授的这篇论文，题目是  A Problem on Non-sensed Cirular Permulations /武汉大学理科季刊 8 卷 1 期（1942 年）。  英文标题的意思是一个关于无向循环排列的问题。

66 年后的 2008 年，国内常新德老师也发表了《有重复元素的圆排列和环排列的计数问题》，可惜他的公式解决问题不彻底，留了一个大尾巴待解决。

相信傅种孙是完全解决了的。如果有哪位网友方便去武汉大学，可到图书馆查阅一下这篇文献，发到这个论坛上来。
  

TSC999

今天这个帖子的问题可以彻底结束了。经编程试验知：

m = 4; n[1] = 1; n[2] = 1; n[3] = 1;  n[4] = 3  时，环排列数为 10 种,  公式算为 10.5 种。公式算的对称圆排列为 1个，实际应当是 0 个。
m = 4; n[1] = 1; n[2] = 1; n[3] = 2;  n[4] = 3  时，环排列数为 30 种， 公式算为 31 种。公式算的对称圆排列为 2个， 实际应当是 0 个。
m = 4; n[1] = 1; n[2] = 1; n[3] = 1;  n[4] = 2  时，环排列数为  6 种,  公式算为 6.5 种。公式算的对称圆排列为 1个， 实际应当是 0 个。
m = 4; n[1] = 1; n[2] = 3; n[3] = 3;  n[4] = 3  时，环排列数为 840 种, 公式算为 843 种。公式算的对称圆排列为 6个，实际应当是 0 个。
m = 3; n[1] = 1; n[2] = 1; n[3] = 3  时，环排列数为 2 种, 公式算为 2.5 种。公式算的对称圆排列为 1个，实际应当是 0 个。
m = 3; n[1] = 3; n[2] = 3; n[3] = 5  时，环排列数为 420 种, 公式算为 426 种。公式算的对称圆排列为 12个，实际应当是 0 个。
m = 3; n[1] = 1; n[2] = 1; n[3] = 1  时，环排列数为 1 种, 公式算为 1.5 种。公式算的对称圆排列为 1个，实际应当是 0 个。
m = 3; n[1] = 3; n[2] = 3; n[3] = 3  时，环排列数为 94 种, 公式算为 97 种。公式算的对称圆排列为 6个，实际应当是 0 个。
m = 5; n[1] = 1; n[2] = 1; n[3] = 1; n[4] = 2; n[5] = 2 时环排列数为 90 种, 公式算为 91 种。公式算的对称圆排列为 2个，实际应当是 0 个。
m = 5; n[1] = 1; n[2] = 1; n[3] = 1; n[4] = 2; n[5] = 3 时环排列数为 210 种, 公式算为 211 种。公式算的对称圆排列为 2个，实际应当是 0 个。
m = 5; n[1] = 1; n[2] = 1; n[3] = 2; n[4] = 2; n[5] = 3  时环排列数为 840 种, 公式算为 843 种。公式算的对称圆排列为 6个，实际应当是 0 个。
m = 5; n[1] = 1; n[2] = 1; n[3] = 1; n[4] = 2; n[5] = 2  时环排列数为 90 种, 公式算为 91 种。公式算的对称圆排列为 2个，实际应当是 0 个。

这就说明，当各种颜色的珠子个数有奇有偶，而奇数个数多于两个时，对称圆排列是没有的，即此时 M=0，此时环排列的数目等于圆排列数目的一半。

而当奇数个数为 0、1、2 时，M 不等于 0，其值需要按公式计算，此时环排列的数目等于圆排列数目的一半再加上 M 的一半。

再回头看看常新德老师的论文，才发现人家已经把这个问题说明白了，而且论证了为什么奇数个数多于两个时，对称圆排列是不存的。见下图：



这就对了，主帖提出的疑问是不存在的，常新德的公式是完全正确的。

为什么奇数个数多于两个时，对称圆排列不存在，见原著中的证明：



折腾了好几天，最终证明是程序没有错，常新德公式也没有错。错在本人马虎了，没有认真阅读常新德老师的那篇论文。只是跑马观花地瞄了一眼。论文本身也有一点点小瑕疵，
如果多说一句话就好了——当奇数个数大于等于 3 时 M=0，此时按公式算出的 M 值不能用。小于等于 2 时才能按公式算 M。