找回密码
 欢迎注册
楼主: 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)

输出结果

输出结果

点评

谢谢 kastin 老师!您的程序比我的高明多了。经运行完全正确,需要好好学习一下。  发表于 2016-11-4 09:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-11-6 22:11:48 | 显示全部楼层
北大校长丁石孙最先解决这个问题。

点评

这只是组合里面一道习题级别题目,不存在谁先解决的问题  发表于 2016-11-7 20:31
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-11-7 22:46:49 | 显示全部楼层
是傅种孙教授最先解决。
这是一个有趣的难题。

点评

这叫“重新发明轮子”,已经被解决的问题被再次解决,还自称首先解决,难道不可笑?这里是讨论学术问题的地方,不是炫耀争发现权的地方。如果你真的有心,那就把他的论文发上来让大家学习一下,自夸自卖毫无意义。  发表于 2016-11-11 20:15
kastin老师言之有理。但是傅种孙教授也是有实力的。他独立得到这个有趣问题的组合公式也是不容易的,况且老外的你也没有看到。  发表于 2016-11-10 22:05
所以他解决这个问题,如果他是不知道上述原理,肯定是用而不知(相当于自己推导了一遍),不存在不用就能解决的情况。另外,国外人的论文你参考没,也行国外人早就有人考虑这个问题了(因为中国清末才引进西方科学)  发表于 2016-11-10 11:17
首先,任何解决这个问题只有两个途径,一个是容斥原理,另一个就是伯氏定理。定理内容本身不是什么创新的东西,只是把方法进行抽象总结而已,所以适用性更广。任何组合学方法最终都归为加法原理和乘法原理  发表于 2016-11-10 11:13
傅教授并不是按伯氏理论做的。他详细、彻底解决了这个具体问题。难能可贵!  发表于 2016-11-9 20:46
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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年刊于《 武汉大学理科季刊》上。

点评

查网: 抗战时期,傅种孙完成了两篇论文,一是组合理论中有关无向循环排列的问题: 设有m种珠子,每种分别有n1,n2,…,nm个,总共有n个。若用这些珠子穿成一个圆环,问有多少种穿法? 他完全解决了这个问题。  发表于 2021-7-11 20:02
去武汉大学图书馆应该能查到: 傅种孙 A Problem on Non-sensed Cirular Permulations /武汉大学理科季刊8卷1期(1942年)  发表于 2021-7-11 19:52
2008年河南永城职业学院常新德老师发表的论文也是这个题目,但是他没有彻底解决问题,留了一个大尾巴。不知道 66 年前傅种孙教授是否完全解决了?现在要寻找1942年《武汉大学理科季刊》,大概非常困难。  发表于 2021-7-11 19:40
向老一辈数学家致敬!  发表于 2018-9-30 08:27
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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})\)


点评

上面这个公式思路对,但是结果不对。  发表于 2021-6-30 22:41
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 03:08 , Processed in 0.049816 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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