一环均分为 6 段，可涂黑白灰，但至多只用 2 色，有几种涂色法？（旋转翻转只算一种）

Bathan_Tam

不太肯定,请教方法

luyuanhong

Nicolas2050

:lol老陆同志用枚举法，没有解决一般性的问题方法。采用图论染色方法才是通用方法。

天山草

这个问题叫做有重复元素的环排列问题。中外历史上应该有多人研究过。国内近期已知的研究者是常新德，他是一位中专学校的老师。

对于本问题，用常新德老师给出的公式计算如下：

1. Clear["Global`*"]; (*常新德公式*)
   
2. s = 0;
   
3. m = 3; n[3] = 0;
   
4. Do[
   
5.   n[1] = k; n[2] = 6 - k;  (* m 种颜色，n[i]是各色珠子个数 *)
   
6.   q = 0; Do[If[OddQ[n[i]], q = q + 1], {i, 1, m}]; (* n[i] 中的奇数个数 *)
   
7.   Subscript[S, n] = \!\(
   
8. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(m\)]\(n[i]\)\);   (*
   
9.   共有 Subscript[S, n] 颗珠子 *)
   
10.    If[q < 3, M = (\!\(
    
11. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(m\)]\(\[LeftFloor]
    
12. \*FractionBox[\(n[i]\), \(2\)]\[RightFloor]\)\))!/\!\(
    
13. \*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(m\)]\(\[LeftFloor]
    
14. \*FractionBox[\(n[i]\), \(2\)]\[RightFloor]!\)\), M = 0];(*圆排列中的对称排列数*)
    
15.   Q = (Sum[EulerPhi[d] *(Subscript[S, n]/d)!/\!\(
    
16. \*UnderoverscriptBox[\(\[Product]\), \(i = 1\), \(m\)]\(\((
    
17. \*FractionBox[\(n[i]\), \(d\)])\)!\)\), {d,
    
18.        Divisors[GCD[n[1], n[2], n[3]]]}])/Subscript[S, n];
    
19.   \[CapitalPhi] = (Q + M)/2; s = s + \[CapitalPhi];
    
20.   , {k, 1, 5}];
    
21. s
    

复制代码

程序运行结果为 s=11。这即是前面陆教授得出的只用两种颜色的组合数。只用一种颜色时显然是 3 种。因此总组合数是 3+11×3=36 种。

天山草

此问题有两种基本提法：

（一）见下图 (这个图中的公式不是常新德给出的)：



（二）有一堆大小相同的珠子，共有 m 种颜色。每一种颜色的珠子分别为 n(1)、n(2)、........、n(m) 颗。

共有珠子 n = n(1)+n(2)+......+n(m) 颗，用这 n 颗珠子穿成手串，能穿成多少种花色的手串？ (下图中的公式是常新德做出的)：



上面公式中是以 m =3 为例。 q  是  n(1)、n(2)、 n(3) 中有几个奇数。如果 q 大于等于 3，则 M=0，就是圆排列中的对称排列数 M=0，

如果 q 小于等于 2，则 M 按图中公式计算。公式中的最后一行即是所求的环排列数。

天山草

主帖中的问题等价于：

一条手串由  6 颗珠子穿成，珠子颜色有三种为黑、白、灰。如果手串只允许一种颜色或二种颜色的珠子穿成，共有多少种不同花色的手串？