数学研发论坛

 找回密码
 欢迎注册
查看: 4929|回复: 40

[讨论] 彩珠手串的配色计数

[复制链接]
发表于 2016-10-26 19:47:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

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

x
用 m 种颜色的珠子穿手串,每串有 n 颗珠子,每种颜色的珠子都足够多。有多少种配色不同的手串?
我用编程的方法,得到了如下数据:
m种颜色
1 2 3 4 5 6 7 8 9 10 11 12

n


2 1 3 6 10 15 21 28 3645 55 66 78
31 410 2035 5684 120 165220 286 364
41 6 21 55120 231 406 666 1035 15402211 3081
51 8 39 136 377888 1855 35366273 10504 16775 25752
6 113 92 430 15054291 10528 23052 4618586185 151756 254618
71 18 198 1300 589520646 60028 151848344925 719290 13992662569788
81 30498 4435 25395107331 365260 1058058 2707245 6278140 13442286 26942565
9 1 46 121915084 110085563786 22503117472984 2155296955605670 131077771 286779076
101 78 321053764 493131 303731414158228 53762472 174489813 500280022 12973624623096689388
111 126 8418 1927002227275 16514106
12 1 224 22913 70437010196680 90782986

根据上表数据,外推出 n 小于等于 6 时通项公式:
`\D S(m,2)=\frac{m(m+1)}2`
`\D S(m,3)=\frac{m(m^2+3m+2)}6=\frac{m(m+1)(m+2)}6`
`\D S(m,4)=\frac{m(m^3+2m^2+3m+2)}8=\frac{m(m+1)(m^2+m+2)}8`
`\D S(m,5)=\frac{m(m^4+5m^2+4)}{10}=\frac{m(m^2+1)(m^2+4)}{10}`
`\D S(m,6)=\frac{m(m^5+3m^3+4m^2+2m+2)}{12}=\frac{m(m+1)(m^4-m^3+4m^2+2)}{12}`

可否得到 S (m, n)的二元表达式?

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +12 收起 理由
wayne + 3 + 3 + 3 + 3 + 12 蛮有意思的题目

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-10-26 19:54:32 | 显示全部楼层
Case S(3,4), 红绿黄三色四珠的手串。每种颜色的珠子都足够多,用它们穿手串,那么共有 21 种不同色配的手串,全谱图如下。
      谱图中任意一条手串,无论怎样旋转、翻面,都不会跟谱图中别的手串完全一样。
      任一红绿黄四珠手串,经适当地旋转、翻面,一定会跟谱图中某个手串完全相同。


3 色 4 珠的所有手串.png

点评

第四行第3个的红珠应该是黄色珠。总数还是对的。  发表于 2016-10-28 11:17
第三行第一个与第四行第三个是一样的(旋转或者上下翻转)。  发表于 2016-10-26 22:19
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-10-26 22:16:08 | 显示全部楼层
需要引用一下带有重复元素的圆排列和环排列相关知识。

下面内容引自 常新德 永城职业学院《有重复元素的圆排列和环排列的计数问题》

记 `k\,(k\geqslant 1)` 重集 `S=\{n_1\*e_1,n_2\*e_2,\cdots,n_k\*e_k\}`,其中 `e_i,\,n_i\;(i=1,2,\dots,k)`分别为元素以及相应的重复数,且集合的势 `|S|=n_1+n_2+\cdots+n_k=n`. 那么该集合所有元素的
1)圆排列数为$$ Q(S)=\frac{1}{n}\sum_{d|(n_1,\cdots,n_k)}\varphi(d)\frac{(\frac{n}{d})!}{\Pi_{i=1}^k(\frac{n_i}{d})!}$$其中 `\varphi(x)` 为数论中的欧拉函数,`(n_1,\cdots,n_k)` 表示 `n_1,n_2,\cdots,n_k` 的最大公约数。
2)环排列数为$$R(S)=\frac{Q(S)+M(S)}{2}$$其中,`\D M(S)=\frac{\left(\sum_{i=1}^k [n_i/2]\right)!}{\Pi_{i=1}^k [n_i/2]!}` 为对称圆排列数,`[x]` 为高斯函数(表示 `x` 的整数部分)。
注意:环排列圆排列,概念有细微区别。环排列考虑旋转不变且翻转不变,而圆排列考虑的是旋转不变。

现在,假定有`c`种`k`重集,那么楼主的手串总数就是\[\D S(m,n)=\sum^m_{k=1}\sum^c_{i=1}C^k_mR(S_i)\]问题分三步进行:
1. 求线性不定方程 `x_1+x_2+\cdots+x_m=n` 的非负整数解(共 `C_{n+m-1}^{m-1}` 组解)。
2. 对任一组解`(n_1,n_2,\cdots,n_m)`, 计算相应的重集 `S_i=\{n_1\*e_1,n_2\*e_2,\cdots,n_m\*e_m\}`的环排列数`R(S_i)`。
3. 将这些环排列数相加,`\D S(m,n)=\sum^c_{i=1}R(S_i)`。(这与上面的汇总公式不同,是因为这里第1步中允许`x_i`取0,`c=C_{n+m-1}^{m-1}`)

不知楼主那个公式是怎么得到的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-10-27 13:57:10 | 显示全部楼层
看了下《有重复元素的圆排列和环排列的计数问题》这篇论文。我们的问题跟论文说的问题,还是有差别的。
在本主题中,各色珠子的个数分配不是固定的,而上述论文中,各元素的重数是已知、固定的。
论文中讲了一个红黄各四穿成八珠手串共 8 种的例子,见下图。
这显然只是跟我们所要求的 S(2,8) 的一部分。
四红四黄穿八珠的方案.png

点评

@kastin并没说两个问题完全一样,只是说要引用论文的公式解决你的问题,并且已经阐明了应用办法。  发表于 2016-10-29 00:06
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-10-27 20:44:56 | 显示全部楼层
关于主帖中那些公式是如何得到的?我是观察列表,发现每一行都呈 n 阶等差数列,猜想就是 n 阶等差数列,用待定系数法就可以得到数列的一个通项公式,也就是主帖中的那些公式。
《有重复元素的圆排列和环排列的计数问题》论文中说的方法,我看不明白。我想,也许可求得 S(m, n) 的二元表达式,或者至少是一个算法能够算出 S(m, n) 的值。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-10-27 21:45:21 | 显示全部楼层

点评

@TSC999,看来你只有高中水平,只能理解具体问题。波利亚计数定理不仅对圆排列(循环群)适用,对于其他更一般的群同样适用(比如计算同分异构体个数,染色种数问题等)。  发表于 2016-10-28 15:06
这个老外的文章,说的好像是另外一码事。  发表于 2016-10-28 11:09
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-10-28 11:10:56 | 显示全部楼层
又推出了S(m,7), S(m,8)的公式。
`\D S(m,7)=\frac{m(m^6+7m^3+6)}{14}`
`\D S(m,8)=\frac{m(m^7+4m^4+5m^3+2m+4)}{16}`
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-10-28 16:34:58 | 显示全部楼层
S(2,n)=A000029(n)
S(3,n)=A027671(n)
S(4,n)=A032275(n)
S(5,n)=A032276(n)
S(6,n)=A056341(n)
S(7,n)=A032276(n)

8色及以上的手链或手串数OEIS尚未收录,楼主若搞出结果来,可以申报上去。

S(m,9)=A060561(n)
S(m,10)=A060562(n)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-10-28 16:48:04 | 显示全部楼层
用伯恩赛德引理(Burnside's lemma,波利亚计数定理就是用它推导得来的)就能得到如下结论:
对于 `m` 个颜色可重复地选取 `n` 个排成一圈,圆排列数为$$N(m,n)=\frac{1}{n}\sum_{i=1}^n m^{(n,i)}$$环排列数为
$$M(m,n)=N(m,n)/2+\begin{cases}\D\frac{m^{k+1}}{2},&n=2k+1\\
\D\frac{(m+1)m^k}{4},&n=2k
\end{cases}$$
经验证,符合1楼所给的经验公式。

点评

@mathe 没错,并且有 `\D\frac{1}{n}\sum_{d|n}\phi(d)m^{\frac{n}{d}}=\frac{1}{n}\sum_{d|n}\phi(\frac{n}{d})m^{d}`  发表于 2016-10-29 11:55
N(m,n)的公式应该可以简化为$1/n \sum_{d|n} phi(n/d) m^d$?  发表于 2016-10-28 19:59
其中 `(a,b)` 表示 `a` 和 `b` 的最大公约数。  发表于 2016-10-28 16:49

评分

参与人数 1威望 +3 金币 +8 贡献 +6 经验 +6 鲜花 +12 收起 理由
hujunhua + 3 + 8 + 6 + 6 + 12 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-10-28 18:52:17 | 显示全部楼层
对于`n`是一个奇素数` p` 的情况,我暗暗猜测的蒙对了。

`\D S(m,p)=\frac{m(m^{\frac{p-1}2}+p-1)(m^{\frac{p-1}2}+1)}{2p}`
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-1-20 15:39 , Processed in 0.084599 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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