彩珠手串的配色计数

hujunhua

对于其它一些特殊形式的珠数，也能得到显式解。
`\D S(m,2p)=\frac{m\left(m^{2p-1}+p\cdot m^p+(p+1)m^{p-1}+(p-1)(m+1)\right)}{4p}`
`\D S(m,2^t)=。。。。`

mathe

比如根据9#公式
$N(m,8)=1/8(m^8+m^4+2m^2+4m)$
$S(m,8)=1/16m(m+1)(m^6-m^5+m^4+3m^3+2m^2-2m+4)$

TSC999

哎哟，我原先还以为是个比较简单的问题，没想到踏进了 “波利亚” 的雷区，大大超出了本人的能力。

kastin

将二项式定理扩充至多项，引入`r`-重组合数 `\mathrm C_n^{n_1,n_2,\cdots,n_r}`，定义如下$$(x_1+x_2+\cdots+x_r)^n=\sum_{n_1+n_2+\cdots+n_r=n\\n_i\in \NN,\;i=1,2,\cdots,r}\mathrm C_n^{n_1,n_2,\cdots,n_r}x_1^{n_1}x_2^{n_2}\cdots x_r^{n_r}\tag{a}$$其中求和符号下面表示的是遍历所有可能满足条件的取值，`\NN` 为非负整数集。
利用二项式展开，有$$\mathrm C_n^{n_1,n_2,\cdots,n_r}=\mathrm C_n^{n_1}\mathrm C_{n-n_1}^{n_2}\mathrm C_{n-n_1-n_2}^{n_3}\cdots \mathrm C_{n_r}^{n_r}=\frac{n!}{n_1!n_2!\cdots n_r!}\tag{b}$$式 `(a)` 本身就是`r`-重集 `S(r)=\{n_1\*e_1,n_2\*e_2,\dots,n_r\*e_r\},\;(n_1+\cdots+n_r=n)` 的线排列的母函数，因此式 `(b)` 即为 `S(r)` 的线排列数 。
另外，令 `x_1=x_2=\cdots=x_r=1` 可得 $$r^n=\sum_{n_1+n_2+\cdots+n_r=n\\n_i\in \NN,\;i=1,2,\cdots,r}\mathrm C_n^{n_1,n_2,\cdots,n_r}=\sum_{n_1+n_2+\cdots+n_r=n\\n_i\in \NN,\;i=1,2,\cdots,r}\frac{n!}{n_1!n_2!\cdots n_r!}\tag{c1}$$这个结果很容易理解，左边表示 `n` 位数的每一位可以有 `r` 种选择，共 `r^n` 种选择，右端表示遍历所有可能重复的选择并求和。

通过3楼和9楼mathe的提醒，我们可以得到一个组合恒等式$$\sum_{d|n}\varphi(d)m^{\frac{n}{d}}=\sum_{n_1+n_2+\cdots+n_m=n\\n_i\in \NN,\;i=1,2,\cdots,m}\;\sum_{q|(n_1,n_2,\cdots,n_m)}\varphi(q)\frac{\frac{n}{q}!}{\frac{n_1}{q}!\frac{n_2}{q}!\cdots \frac{n_m}{q}!}\tag{c2}$$注意，上式右端中分子分母中的分式没有用圆括号括起来是因为避免与数论中的雅可比符号产生混淆（同样，3楼中对应位置本来也应该不加括号的）；还有右端之所以用 `q` 而不是用 `d` 表示约数，是为了避免相同符号在等式两边却有不同意义。

我感兴趣的是 `(\mathrm c1)` 和 `(\mathrm c2)` 之间的内在联系。易知，如果 `q` 遍历的值域就是 `n` 的所有因子（即和 `d` 的值域是一样的），那么这二式是等价的（注意到，二重求和符号可交换）。即问不定方程 `n_1+n_2+\cdots+n_m=n\;n_i\in \NN,\;(i=1,2,\cdots,m)` 的每组解的公约数构成的并集是否就是 `n` 的所有约数？

TSC999

根据 kastin 老师的公式，我用 mathematica 写了一段小程序，是当手串珠子数目 n 固定之后，配色方案数目 S(m, n) 的计算公式。
程序计算结果正确，但是不知为什么有警告提示。不知程序哪里不太好而导致，如何才能消除这个警告？
程序如下：

1. Clear[s]; Array[s, {30, 30}]; (*定义二维数组 s(16,16) *)
   
2. For[q = 1, q <= 30, q++,     (* 计算二维数组 s 的值 *)
   
3. For[p = 1, p <= 30, p++,
   
4.   If[EvenQ[q], s[p, q] = 1/(2 q) \!\(
   
5. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(q\)]
   
6. \*SuperscriptBox[\(p\), \(GCD[q, i]\)]\) + ((p + 1) p^(q/2))/4,
   
7.     s[p, q] = 1/(2 q) \!\(
   
8. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(q\)]
   
9. \*SuperscriptBox[\(p\), \(GCD[q, i]\)]\) + p^((q + 1)/2)/2];]]
   
10. n =.; j = 30;
    
11. Array[x, 30];             (* 解方程：用数组 x[i] 作为未知数 *)
    
12.   For[n = 1, n <= j, n++,(* 算 1 至 30 珠 *)
    
13. Clear[x]; a = Table[x[k], {k, 1, j}] /.
    
14.    Solve[Table[\!\(
    
15. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(n\)]\(x[i]
    
16. \*SuperscriptBox[\(k\), \(i\)]\)\) == s[k, n], {k, 1, j}],
    
17.     Table[x[k], {k, 1, j}]];
    
18. b = a[[1]];
    
19. m =.; ss = \!\(
    
20. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(n\)]\(b[\([\)\(i\)\(]\)]*
    
21. \*SuperscriptBox[\(m\), \(n + 1 - i\)]\)\);
    
22. Print["s(", n, ")=", Factor[Simplify[ss]]]]

复制代码

运行结果如下：

补充内容 (2021-7-11 18:30):
15# 这个程序的计算结果也有误。正确的结果见下面 16# 楼的程序给出的结果。

kastin

TSC999 发表于 2016-11-3 20:09
根据 kastin 老师的公式，我用 mathematica 写了一段小程序，是当手串珠子数目 n 固定之后，配色方案数目 S ...

Mathematica是函数式程序语言，学会函数式的编程风格，问题将会简单很多。

1. S[m_, n_?OddQ] :=
   
2.   1/2 Sum[EulerPhi[n/d] m^d, {d, Divisors[n]}]/n + m^((n + 1)/2)/2;
   
3. S[m_, n_?EvenQ] :=
   
4.   1/2 Sum[EulerPhi[n/d] m^d, {d, Divisors[n]}]/n + (m + 1) m^(n/2)/4;
   
5. Table[Defer[S][m, n] == S[m, n] // Factor, {n, 1, 6}] // TableForm

复制代码

以下是输出结果（必须在“编辑”>“偏好设置">”计算“>"新输出单元格式"，选择TranditionalForm)

输出结果

数学青年

北大校长丁石孙最先解决这个问题。

数学青年

是傅种孙教授最先解决。
这是一个有趣的难题。

数学青年

         傅种孙（1898年2月27日—1962年1月18日），字仲嘉，中国著名数学家、教育家，生于江西省高安，1916年毕业于省立第八中学，后考入北京高等师范学校，1920年留校任教，后担任北京女子师大、北京大学、辅仁大学、西北大学教授；1945年赴英国考察；1947年回国，后担任北平师范学院数学系主任；全国解放以后，任北京师范大学教务长、副校长、《中国数学》总编辑等职务，撰有多部颇具影响的初等数学教材，培养了大批数学教学与研究人才；1957年被错划为右派，1962年在北京病逝。
       抗战时期，傅种孙了解决组合理论中有关无向循环排列的问题：
       设有ｍ种珠子，每种分别有ｎ_１，ｎ_２，…，ｎ_ｍ个，共有ｎ个，若将这些珠子穿成一个圆环，问有多少种穿法？
      他完全解决了上述问题，写成论文于１９４２年刊于《 武汉大学理科季刊》上。

王守恩

  \(m \) 种颜色 \(  n\)(不分奇数,偶数)颗珠穿成的环，有几种穿法 \(S(m,n)\)？

\(\D S(m,n)=\frac{1}{2 m}\DivisorSum(m,\EulerPhi(\#)n^{\frac{m}{\#}}\&)+\frac{1}{4}(n^{\lceil\frac{m}{2}\rceil}+n^{\lceil\frac{m+1}{2}\rceil})\)