数学研发论坛

 找回密码
 欢迎注册
123
返回列表 发新帖
楼主: TSC999

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

[复制链接]
发表于 2021-3-30 09:02:16 | 显示全部楼层
本帖最后由 王守恩 于 2021-3-30 13:06 编辑

                  答 1 楼:杨辉三角!!!

   m 种颜色 2 颗珠 LinearRecurrence[{2, -1}, {0, 1}, 30]
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29}

   m 种颜色 3 颗珠 LinearRecurrence[{3, -3, 1}, {1, 0, 0}, 30]
{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378}

   m 种颜色 4 颗珠 LinearRecurrence[{4, -6, 4, -1}, {0, 0, 0, 1}, 30]
{1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540, 1771, 2024, 2300, 2600, 2925, 3276, 3654}

   m 种颜色 5 颗珠 LinearRecurrence[{5, -10, 10, -5, 1}, {1, 0, 0, 1, 6}, 30]
{1, 6, 21, 55, 120, 231, 406, 666, 1035, 1540, 2211, 3081, 4186, 5565, 7260, 9316, 11781, 14706, 18145, 22155, 26796, 32131, 38226, 45150, 52975, 61776, 71631}

   m 种颜色 6 颗珠 LinearRecurrence[{6, -15, 20, -15, 6, -1}, {-8, -1, 0, 1, 8, 39}, 30]
{1, 8, 39, 136, 377, 888, 1855, 3536, 6273, 10504, 16775, 25752, 38233, 55160, 77631, 106912, 144449, 191880, 251047, 324008, 413049, 520696, 649727, 803184, 984385, 1196936, 1444743}

   m 种颜色 7 颗珠 LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {73, 7, 0, 0, 1, 13, 92}, 30]
{1, 13, 92, 430, 1505, 4291, 10528, 23052, 46185, 86185, 151756, 254618, 410137, 638015, 963040, 1415896, 2034033, 2862597, 3955420, 5376070, 7198961, 9510523, 12410432, 16012900, 20448025}

   m 种颜色 8 颗珠 LinearRecurrence[{8, -28, 56, -70, 56, -28, 8, -1}, {-1044, -117, -2, 0, 0, 1, 18, 198}, 30]
{1, 18, 198, 1300, 5895, 20646, 60028, 151848, 344925, 719290, 1399266, 2569788, 4496323, 7548750, 12229560, 19206736, 29351673, 43782498, 63913150, 91508580, 128746431, 178285558, 243341748}

   m 种颜色 9 颗珠 LinearRecurrence[{9, -36, 84, -126, 126, -84, 36, -9, 1}, {3921, 375, 13, 0, 0, 1, 30, 498, 4435}, 30]
{1, 30, 498, 4435, 25395, 107331, 365260, 1058058, 2707245, 6278140, 13442286, 26942565, 51084943, 92383305, 160386360, 268718116, 436365945, 689252778, 1062132490, 1600850055, 2365010571}

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-6-30 22:47:19 | 显示全部楼层
根据 王守恩 20# 楼的思路,可将 n 是奇数和 n 是偶数的两种情况合并在一个公式里计算:

S(m,n)  =Sum[EulerPhi[n/k] m^k,{k,Divisors[n]}]/(2n)+1/4 (m^Floor[(n+1)/2]+m^Floor[(n+2)/2])

上面公式中 Floor 表示取整。

20# 楼中的公式有误。上面这个公式是 mathematica 软件的程序代码。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-7-1 09:06:46 | 显示全部楼层
TSC999 发表于 2021-6-30 22:47
根据 王守恩 20# 楼的思路,可将 n 是奇数和 n 是偶数的两种情况合并在一个公式里计算:

S(m,n)  =Sum[E ...

20# 楼中的公式有误。22# 楼中的公式是对的。

S(m,n)  =Sum[EulerPhi[n/k] m^k,{k,Divisors[n]}]/(2n)+1/4 (m^Floor[(n+1)/2]+m^Floor[(n+2)/2])

其中:m^Floor[(n+1)/2]+m^Floor[(n+2)/2]=m^Ceiling[n/2]+m^Ceiling[(n+1)/2]

点评

22# 楼的公式还是好用一些。  发表于 2021-7-1 21:00
对对对,Floor[x] 表示小于等于 x 的最大整数,Ceiling[x] 表示大于等于 x 的最小整数。二者等价。  发表于 2021-7-1 09:31
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-7-11 17:42:08 | 显示全部楼层
本帖最后由 TSC999 于 2021-7-11 18:34 编辑

根据 9# 楼的公式,22# 楼的公式(即主帖所求的有重复元素时的环排列计数公式)也可以写成不引用欧拉函数的形式:

\[Q=\displaystyle \frac{1}{n}\sum_{i=1}^nm^{GCD[n,i]}\]

\[Φ=\frac{Q}{2}+\frac{1}{4}(m^{\lfloor(n+1)/2\rfloor}+m^{\lfloor(n+2)/2\rfloor})\]


式中 \(GCD[n,i]\) 表示 \(n\) 与 \(i\) 的最大公约数。\(\lfloor(n+1)/2\rfloor\) 和 \(\lfloor(n+2)/2\rfloor\) 表示取整。

写成 MMA 程序代码为:

  1. Q = 1/n \!\(
  2. \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(n\)]\(m^GCD[n, i]\)\);
  3. \[CapitalPhi] =
  4. Q/2 + 1/4 (m^\[LeftFloor](n + 1)/2\[RightFloor] +
  5.      m^\[LeftFloor](n + 2)/2\[RightFloor])
复制代码


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

本版积分规则

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

GMT+8, 2022-5-26 18:19 , Processed in 0.070922 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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