彩珠手串的配色计数
用 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)的二元表达式？ Case S(3,4)， 红绿黄三色四珠的手串。每种颜色的珠子都足够多，用它们穿手串，那么共有 21 种不同色配的手串，全谱图如下。
谱图中任意一条手串，无论怎样旋转、翻面，都不会跟谱图中别的手串完全一样。
任一红绿黄四珠手串，经适当地旋转、翻面，一定会跟谱图中某个手串完全相同。
需要引用一下带有重复元素的圆排列和环排列相关知识。
下面内容引自 常新德 永城职业学院《有重复元素的圆排列和环排列的计数问题》
记 `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 \right)!}{\Pi_{i=1}^k !}` 为对称圆排列数，`` 为高斯函数（表示 `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}`）
不知楼主那个公式是怎么得到的？ 看了下《有重复元素的圆排列和环排列的计数问题》这篇论文。我们的问题跟论文说的问题，还是有差别的。
在本主题中，各色珠子的个数分配不是固定的，而上述论文中，各元素的重数是已知、固定的。
论文中讲了一个红黄各四穿成八珠手串共 8 种的例子，见下图。
这显然只是跟我们所要求的 S(2,8) 的一部分。
关于主帖中那些公式是如何得到的？我是观察列表，发现每一行都呈 n 阶等差数列，猜想就是 n 阶等差数列，用待定系数法就可以得到数列的一个通项公式，也就是主帖中的那些公式。
《有重复元素的圆排列和环排列的计数问题》论文中说的方法，我看不明白。我想，也许可求得 S(m, n) 的二元表达式，或者至少是一个算法能够算出 S(m, n) 的值。 https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem 又推出了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}` 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) 用伯恩赛德引理（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楼所给的经验公式。 对于`n`是一个奇素数` p` 的情况，我暗暗猜测的蒙对了。:)
`\D S(m,p)=\frac{m(m^{\frac{p-1}2}+p-1)(m^{\frac{p-1}2}+1)}{2p}`