数学研发论坛

 找回密码
 欢迎注册
楼主: TSC999

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

[复制链接]
发表于 2016-10-28 19:36:58 | 显示全部楼层
对于其它一些特殊形式的珠数,也能得到显式解。
`\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)=。。。。`

点评

n的因子数目越少,公式越简单  发表于 2016-10-28 20:03
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-10-29 07:06:13 | 显示全部楼层
比如根据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)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-10-29 10:24:31 | 显示全部楼层
哎哟,我原先还以为是个比较简单的问题,没想到踏进了 “波利亚” 的雷区,大大超出了本人的能力。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-10-29 20:41:19 | 显示全部楼层
将二项式定理扩充至多项,引入`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` 的所有约数?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-11-3 20:09:07 | 显示全部楼层
根据 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# 楼的程序给出的结果。
运行结果1.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-11-3 22:00:09 | 显示全部楼层
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)

输出结果

输出结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-11-6 22:11:48 | 显示全部楼层
北大校长丁石孙最先解决这个问题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-11-7 22:46:49 | 显示全部楼层
是傅种孙教授最先解决。
这是一个有趣的难题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-11-9 20:37:20 | 显示全部楼层
本帖最后由 数学青年 于 2016-11-9 20:50 编辑

         傅种孙(1898年2月27日—1962年1月18日),字仲嘉,中国著名数学家、教育家,生于江西省高安,1916年毕业于省立第八中学,后考入北京高等师范学校,1920年留校任教,后担任北京女子师大、北京大学、辅仁大学、西北大学教授;1945年赴英国考察;1947年回国,后担任北平师范学院数学系主任;全国解放以后,任北京师范大学教务长、副校长、《中国数学》总编辑等职务,撰有多部颇具影响的初等数学教材,培养了大批数学教学与研究人才;1957年被错划为右派,1962年在北京病逝。
       抗战时期,傅种孙了解决组合理论中有关无向循环排列的问题:
       设有m种珠子,每种分别有n,n,…,n个,共有n个,若将这些珠子穿成一个圆环,问有多少种穿法?
      
他完全解决了上述问题,写成论文于1942年刊于《 武汉大学理科季刊》上。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-3-29 12:51:40 | 显示全部楼层
本帖最后由 王守恩 于 2021-3-29 18:15 编辑

  \(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})\)


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2022-5-26 20:12 , Processed in 0.091792 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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