数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 5329|回复: 7

一环均分为 6 段,可涂黑白灰,但至多只用 2 色,有几种涂色法?(旋转翻转只算一种)

[复制链接]
发表于 2021-8-8 15:16 | 显示全部楼层 |阅读模式
不太肯定,请教方法

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2021-8-9 13:09 | 显示全部楼层


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x

点评

谢谢陸老师  发表于 2021-8-9 16:40
回复 支持 1 反对 0

使用道具 举报

发表于 2021-8-9 22:23 | 显示全部楼层
:lol老陆同志用枚举法,没有解决一般性的问题方法。采用图论染色方法才是通用方法。
回复 支持 反对

使用道具 举报

发表于 2021-8-10 11:59 | 显示全部楼层
这个问题叫做有重复元素的环排列问题。中外历史上应该有多人研究过。国内近期已知的研究者是常新德,他是一位中专学校的老师。

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

  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 种。

点评

理论基础是波利亚计数理论。  发表于 2021-8-10 14:45
回复 支持 反对

使用道具 举报

发表于 2021-8-10 19:19 | 显示全部楼层
此问题有两种基本提法:

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



(二)有一堆大小相同的珠子,共有 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 按图中公式计算。公式中的最后一行即是所求的环排列数。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

发表于 2021-8-10 19:41 | 显示全部楼层
主帖中的问题等价于:

一条手串由  6 颗珠子穿成,珠子颜色有三种为黑、白、灰。如果手串只允许一种颜色或二种颜色的珠子穿成,共有多少种不同花色的手串?
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-11 06:55 , Processed in 0.085261 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表