彩珠手串的配色计数

王守恩

                  答 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}

TSC999

根据 王守恩 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]

TSC999

根据 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])

复制代码