账号 自动登录 找回密码 密码 欢迎注册
 搜索

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

 本帖最后由 王守恩 于 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 软件的程序代码。

 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

楼主| 发表于 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 程序代码为： Q = 1/n \!$$\*UnderoverscriptBox[\(\[Sum]$$, $$i = 1$$, $$n$$]$$m^GCD[n, i]$$\); \[CapitalPhi] = Q/2 + 1/4 (m^\[LeftFloor](n + 1)/2\[RightFloor] +      m^\[LeftFloor](n + 2)/2\[RightFloor])复制代码

 1楼的通项公式。   m 种颜色 n 颗珠。 {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, 30, 31, 32, 33}, {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, 406, 435, 465, 496, 528, 561}, {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, 4060, 4495, 4960, 5456, 5984, 6545}, {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, 82621, 94830, 108345, 123256, 139656, 157641}, {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, 1732024, 2063321, 2443512, 2877823, {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, 25863201, 32424588, 40318642, {1, 18, 198, 1300, 5895, 20646, 60028, 151848, 344925, 719290, 1399266, 2569788, 4496323, 7548750, 12229560, 19206736, 29351673, 43782498, 63913150, 91508580, 128746431, 178285558, 243341748, 327771000, 436160725, {1, 30, 498, 4435, 25395, 107331, 365260, 1058058, 2707245, 6278140, 13442286, 26942565, 51084943, 92383305, 160386360, 268718116, 436365945, 689252778, 1062132490, 1600850055, 2365010571, 3431103775, 4896133188, {1, 46, 1219, 15084, 110085, 563786, 2250311, 7472984, 21552969, 55605670, 131077771, 286779076, 589324749, 1148105154, 2136122255, 3818273456, 6588925841, 11020906014, 17928333139, 28446045340, 44128712341,   Table[Total[EulerPhi[n/#]m^#&/@Divisors[n]/(2n)]+(m^Ceiling[n/2]+m^Ceiling[(n+1)/2])/4,{n,9},{m,33}]复制代码

 杨辉三角啊

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖并转播 回帖后跳转到最后一页

GMT+8, 2024-8-12 08:12 , Processed in 0.027073 second(s), 16 queries .