彩珠手串的配色计数

TSC999

用 m 种颜色的珠子穿手串，每串有 n 颗珠子，每种颜色的珠子都足够多。有多少种配色不同的手串？
我用编程的方法，得到了如下数据：

		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 时通项公式：
`\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)的二元表达式？

TSC999

Case S(3,4)， 红绿黄三色四珠的手串。每种颜色的珠子都足够多，用它们穿手串，那么共有 21 种不同色配的手串，全谱图如下。
      谱图中任意一条手串，无论怎样旋转、翻面，都不会跟谱图中别的手串完全一样。
      任一红绿黄四珠手串，经适当地旋转、翻面，一定会跟谱图中某个手串完全相同。

kastin

需要引用一下带有重复元素的圆排列和环排列相关知识。

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

记 `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}`）

不知楼主那个公式是怎么得到的？

TSC999

看了下《有重复元素的圆排列和环排列的计数问题》这篇论文。我们的问题跟论文说的问题，还是有差别的。
在本主题中，各色珠子的个数分配不是固定的，而上述论文中，各元素的重数是已知、固定的。
论文中讲了一个红黄各四穿成八珠手串共 8 种的例子，见下图。
这显然只是跟我们所要求的 S(2,8) 的一部分。

TSC999

关于主帖中那些公式是如何得到的？我是观察列表，发现每一行都呈 n 阶等差数列，猜想就是 n 阶等差数列，用待定系数法就可以得到数列的一个通项公式，也就是主帖中的那些公式。
《有重复元素的圆排列和环排列的计数问题》论文中说的方法，我看不明白。我想，也许可求得 S(m, n) 的二元表达式，或者至少是一个算法能够算出 S(m, n) 的值。

mathe

https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem

TSC999

又推出了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}`

hujunhua

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)

kastin

用伯恩赛德引理（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楼所给的经验公式。

hujunhua

对于`n`是一个奇素数` p` 的情况，我暗暗猜测的蒙对了。

`\D S(m,p)=\frac{m(m^{\frac{p-1}2}+p-1)(m^{\frac{p-1}2}+1)}{2p}`