2016年10月TSC999提问:
用 m 种颜色的珠子穿手串,每串有 n 颗珠子,每种颜色的珠子都足够多。有多少种配色不同的手串?
2019年10月markfang2050提问:
某珠宝商准备将蓝、绿、紫三种不同颜色的珠子串成由七颗珠子组成的手链进行出售。请问有多少种不同排列顺序的手链产生?
注意:1,没说一定要用全三色;2,手串是环形,对称性要排除。
markfang2050给他的问题配上几个例图:
mathe手工分析markfang2050的问题:
同色3种, 如果左右对称,对称轴过一棵珠子,34−3=78种(需要去除同色的三种), 任意摆放的去掉同色和对称的有1437−3−78×7=117,
得出总数为3+78+117=198.
northwolves很快回复markfang2050,对于他的问题,n颗珠子对应的答案为:
1 3
2 6
3 10
4 21
5 39
6 92
7 198
8 498
9 1219
并且后来右给出对应的python代码并且计算到n=30:
import numpy as np
def count(n):
m=0
for i in range(n):
m+=3.0**np.gcd(n,i+1)
m+=(2+n%2)*n*3**(n//2)
return int(m//(2*n))
for n in range(1,31):
print (n,count(n))
并且指出结果和A027671匹配。
markfang2050也同样给出了Python代码, 并且指出这个问题可以用burnside引理或Polya定理高效解决。
chyanog使用Mathematica代码计算和做出所有对应的手链:
dlpg070改进chyanog的代码将数据结果和图片放在一起:
hujunhua指出7色手链问题是我们已经讨论过的彩珠手串的配色计数的特例。
其中,TSC999首先自己给出了一个计算结果的表格:
| m种颜色 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
n
颗
珠
子 | 2 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 | 66 | 78 |
3 | 1 | 4 | 10 | 20 | 35 | 56 | 84 | 120 | 165 | 220 | 286 | 364 |
4 | 1 | 6 | 21 | 55 | 120 | 231 | 406 | 666 | 1035 | 1540 | 2211 | 3081 |
5 | 1 | 8 | 39 | 136 | 377 | 888 | 1855 | 3536 | 6273 | 10504 | 16775 | 25752 |
6 | 1 | 13 | 92 | 430 | 1505 | 4291 | 10528 | 23052 | 46185 | 86185 | 151756 | 254618 |
7 | 1 | 18 | 198 | 1300 | 5895 | 20646 | 60028 | 151848 | 344925 | 719290 | 1399266 | 2569788 |
8 | 1 | 30 | 498 | 4435 | 25395 | 107331 | 365260 | 1058058 | 2707245 | 6278140 | 13442286 | 26942565 |
9 | 1 | 46 | 1219 | 15084 | 110085 | 563786 | 2250311 | 7472984 | 21552969 | 55605670 | 131077771 | 286779076 |
10 | 1 | 78 | 3210 | 53764 | 493131 | 3037314 | 14158228 | 53762472 | 174489813 | 500280022 | 1297362462 | 3096689388 |
11 | 1 | 126 | 8418 | 192700 | 2227275 | 16514106 | | | | | | |
12 | 1 | 224 | 22913 | 704370 | 10196680 | 90782986 | | | | | | |
并且根据上面表格外推出n小于等于6时通项公式:
S(m,2)=2m(m+1)
S(m,3)=6m(m2+3m+2)=6m(m+1)(m+2)
S(m,4)=8m(m3+2m2+3m+2)=8m(m+1)(m2+m+2)
S(m,5)=10m(m4+5m2+4)=10m(m2+1)(m2+4)
S(m,6)=12m(m5+3m3+4m2+2m+2)=12m(m+1)(m4−m3+4m2+2)
后来又给出了S(m,7), S(m,8)的公式:
S(m,7)=14m(m6+7m3+6)
S(m,8)=16m(m7+4m4+5m3+2m+4)
并且给出了S(3,4)对应的所有情况的图片:
kastin给出分析:
下面内容引自 常新德 永城职业学院《有重复元素的圆排列和环排列的计数问题》:
记 k(k⩾1) 重集 S={n1×e1,n2×e2,⋯,nk×ek},其中 ei,ni(i=1,2,…,k)分别为元素以及相应的重复数,且集合的势 ∣S∣=n1+n2+⋯+nk=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})!}$$其中 φ(x) 为数论中的欧拉函数,(n1,⋯,nk) 表示 n1,n2,⋯,nk 的最大公约数。
2)环排列数为R(S)=2Q(S)+M(S)其中,M(S)=Πi=1k[2ni]!(∑i=1k[2ni])! 为对称圆排列数,[x] 为高斯函数(表示 x 的整数部分)。
注意:环排列和圆排列,概念有细微区别。环排列考虑旋转不变且翻转不变,而圆排列考虑的是旋转不变。
现在,假定有c种k重集,那么楼主的手串总数就是S(m,n)=∑k=1m∑i=1cCmkR(Si)问题分三步进行:
- 求线性不定方程 x1+x2+⋯+xm=n 的非负整数解(共 Cn+m−1m−1 组解)。
- 对任一组解(n1,n2,⋯,nm), 计算相应的重集 Si={n1×e1,n2×e2,⋯,nm×em}的环排列数R(Si)。
- 将这些环排列数相加,S(m,n)=∑i=1cR(Si)。(这与上面的汇总公式不同,是因为这里第1步中允许xi取0,c=Cn+m−1m−1)
TSC999又根据论文内容给出对应的红黄各四穿成八珠手串的漂亮图片:
hujunhua指出:
可以在OEIS中找到
S(2,n)=A000029
S(3,n)=A027671
S(4,n)=A032275
S(5,n)=A032276
S(6,n)=A056341
S(7,n)=A032276
以及
S(m,9)=A060561
S(m,10)=A060562
kastin接着用伯恩赛德引理(Burnside's lemma,波利亚计数定理就是用它推导得来的)就能得到如下结论:
对于 m 个颜色可重复地选取 n 个排成一圈,圆排列数为N(m,n)=n1∑i=1nm(n,i)环排列数为
M(m,n)=2N(m,n)+{2mk+1,4(m+1)mk,n=2k+1n=2k
hujunhua 猜测对于n是一个奇素数p的情况,有S(m,p)=2pm(m2p−1+p−1)(m2p−1+1) .
并且得出S(m,2p)=4pm(m2p−1+p⋅mp+(p+1)mp−1+(p−1)(m+1)).