5种颜色5颗珠穿成的环，有几种穿法？

天山草

如果要补齐 n=9 那行的数据，此行必须至少要有 9 个数据才行，即填到 m =9 为止。
如果要补齐 n=10 那行的数据，此行必须至少要有 10 个数据才行，即填到 m =10 为止。

天山草

现在希望找到从上到下的计算公式。

天山草

下面这个图片是数学研发网站上 kastin 先生的回复，这个回复一时半会儿是看不明白的，还是看看原著吧（见附件：有重复元素的圆排列和环排列的计数问题）。

天山草

看了下《有重复元素的圆排列和环排列的计数问题》这篇论文。我们的问题跟论文说的问题，还是有差别的。论文中的公式不能直接解决我们的问题。
在我们的问题中，元素的个数事先不知道有多少。而那篇论文中，元素个数是已知的。
论文中讲了一个四红珠四黄珠共八颗珠子，穿成八颗珠子的手串，穿法共有 8 种，见下图。这跟我们所说的 2 种颜色（红与黄）的珠子，都有很多颗，穿成八颗珠子的手串，共有多少种穿法？ 显然是不一样的问题！

天山草

该问题发到了数学研发网站，kastin 先生给出了 S(m, n）的公式解答：

S(1,1)=1

S(2,1)=2

S(3,1)=3

S(4,1)=4

S(5,1)=5

S(6,1)=6

S(7,1)=7

S(8,1)=8

S(9,1)=9

S(10,1)=10

S(11,1)=11

S(12,1)=12

S(13,1)=13

S(14,1)=14

S(15,1)=15

S(16,1)=16

--------------------------------

S(1,2)=1

S(2,2)=3

S(3,2)=6

S(4,2)=10

S(5,2)=15

S(6,2)=21

S(7,2)=28

S(8,2)=36

S(9,2)=45

S(10,2)=55

S(11,2)=66

S(12,2)=78

S(13,2)=91

S(14,2)=105

S(15,2)=120

S(16,2)=136

--------------------------------

S(1,3)=1

S(2,3)=4

S(3,3)=10

S(4,3)=20

S(5,3)=35

S(6,3)=56

S(7,3)=84

S(8,3)=120

S(9,3)=165

S(10,3)=220

S(11,3)=286

S(12,3)=364

S(13,3)=455

S(14,3)=560

S(15,3)=680

S(16,3)=816

--------------------------------

S(1,4)=1

S(2,4)=6

S(3,4)=21

S(4,4)=55

S(5,4)=120

S(6,4)=231

S(7,4)=406

S(8,4)=666

S(9,4)=1035

S(10,4)=1540

S(11,4)=2211

S(12,4)=3081

S(13,4)=4186

S(14,4)=5565

S(15,4)=7260

S(16,4)=9316

--------------------------------

S(1,5)=1

S(2,5)=8

S(3,5)=39

S(4,5)=136

S(5,5)=377

S(6,5)=888

S(7,5)=1855

S(8,5)=3536

S(9,5)=6273

S(10,5)=10504

S(11,5)=16775

S(12,5)=25752

S(13,5)=38233

S(14,5)=55160

S(15,5)=77631

S(16,5)=106912

--------------------------------

S(1,6)=1

S(2,6)=13

S(3,6)=92

S(4,6)=430

S(5,6)=1505

S(6,6)=4291

S(7,6)=10528

S(8,6)=23052

S(9,6)=46185

S(10,6)=86185

S(11,6)=151756

S(12,6)=254618

S(13,6)=410137

S(14,6)=638015

S(15,6)=963040

S(16,6)=1415896

--------------------------------

S(1,7)=1

S(2,7)=18

S(3,7)=198

S(4,7)=1300

S(5,7)=5895

S(6,7)=20646

S(7,7)=60028

S(8,7)=151848

S(9,7)=344925

S(10,7)=719290

S(11,7)=1399266

S(12,7)=2569788

S(13,7)=4496323

S(14,7)=7548750

S(15,7)=12229560

S(16,7)=19206736

--------------------------------

S(1,8)=1

S(2,8)=30

S(3,8)=498

S(4,8)=4435

S(5,8)=25395

S(6,8)=107331

S(7,8)=365260

S(8,8)=1058058

S(9,8)=2707245

S(10,8)=6278140

S(11,8)=13442286

S(12,8)=26942565

S(13,8)=51084943

S(14,8)=92383305

S(15,8)=160386360

S(16,8)=268718116

--------------------------------

S(1,9)=1

S(2,9)=46

S(3,9)=1219

S(4,9)=15084

S(5,9)=110085

S(6,9)=563786

S(7,9)=2250311

S(8,9)=7472984

S(9,9)=21552969

S(10,9)=55605670

S(11,9)=131077771

S(12,9)=286779076

S(13,9)=589324749

S(14,9)=1148105154

S(15,9)=2136122255

S(16,9)=3818273456

--------------------------------

S(1,10)=1

S(2,10)=78

S(3,10)=3210

S(4,10)=53764

S(5,10)=493131

S(6,10)=3037314

S(7,10)=14158228

S(8,10)=53762472

S(9,10)=174489813

S(10,10)=500280022

S(11,10)=1297362462

S(12,10)=3096689388

S(13,10)=6894242719

S(14,10)=14464776522

S(15,10)=28835595048

S(16,10)=54980090320

--------------------------------

S(1,11)=1

S(2,11)=126

S(3,11)=8418

S(4,11)=192700

S(5,11)=2227275

S(6,11)=16514106

S(7,11)=89937316

S(8,11)=390582648

S(9,11)=1426677525

S(10,11)=4545954550

S(11,11)=12969598086

S(12,11)=33774600756

S(13,11)=81464249503

S(14,11)=184074908850

S(15,11)=393176416200

S(16,11)=799653208816

--------------------------------

S(1,12)=1

S(2,12)=224

S(3,12)=22913

S(4,12)=704370

S(5,12)=10196680

S(6,12)=90782986

S(7,12)=576960734

S(8,12)=2863912668

S(9,12)=11769248715

S(10,12)=41669459260

S(11,12)=130773238871

S(12,12)=371514016094

S(13,12)=970770644298

S(14,12)=2362274901910

S(15,12)=5406143453740

S(16,12)=11728196037656

--------------------------------

S(1,13)=1

S(2,13)=380

S(3,13)=62415

S(4,13)=2589304

S(5,13)=46989185

S(6,13)=502474356

S(7,13)=3726912175

S(8,13)=21145502960

S(9,13)=97766461809

S(10,13)=384620384620

S(11,13)=1327806364511

S(12,13)=4115141199720

S(13,13)=11649073935505

S(14,13)=30527543985764

S(15,13)=74853741905055

S(16,13)=173215504501216

--------------------------------

S(1,14)=1

S(2,14)=687

S(3,14)=173088

S(4,14)=9608050

S(5,14)=218102685

S(6,14)=2799220041

S(7,14)=24223929112

S(8,14)=157077883188

S(9,14)=817040430225

S(10,14)=3571456428595

S(11,14)=13562553214056

S(12,14)=45854348609862

S(13,14)=140620807064413

S(14,14)=396857785692525

S(15,14)=1042605190446480

S(16,14)=2573486651792296

--------------------------------

S(1,15)=1

S(2,15)=1224

S(3,15)=481598

S(4,15)=35824240

S(5,15)=1017448143

S(6,15)=15673673176

S(7,15)=158254933900

S(8,15)=1172820793824

S(9,15)=6863059263885

S(10,15)=33333383340136

S(11,15)=139241712837546

S(12,15)=513567600827216

S(13,15)=1706196841693435

S(14,15)=5185603923191160

S(15,15)=14596464294191704

S(16,15)=38430718967782336

--------------------------------

S(1,16)=1

S(2,16)=2250

S(3,16)=1351983

S(4,16)=134301715

S(5,16)=4768969770

S(6,16)=88162676511

S(7,16)=1038540790210

S(8,16)=8796131295498

S(9,16)=57906989864055

S(10,16)=312500278125640

S(11,16)=1435929708012921

S(12,16)=5777634501348645

S(13,16)=20794271917525288

S(14,16)=68061047386872645

S(15,16)=205262771447683860

S(16,16)=576460770691256356

------------------------------------------------
下面的公式中，S(m, n) 表示环排列数目，GCD[n, k] 表示 n 与 k 的最大公约数。
注： 公式中的第一项的 2 倍等于圆排列数目。

天山草

        这个问题需要涉及 “带有重复元素的圆排列和环排列“ 的知识。历史上解决该问题的人是数学家波利亚。
        波利亚(George Polya，1887-1985)，美籍匈牙利数学家。生于布达佩斯，卒于美国。青年时期曾在布达佩斯、维也纳、巴黎等地攻读数学、物理和哲学，获博士学位。1914年在瑞士苏黎世工业大学任教，1938年任数理学院院长。1940年移居美国，历任布朗大学、斯坦福大学教授。1963年获美国数学会功勋奖。他是法国科学院、美国全国科学园和匈牙利科学院的院士。 曾著有《怎样解题》、《数学的发现》、《数学与猜想》等，它们被译成多种文字，广为流传。
       1935年，波利亚对化学中同分异构体进行了研究，表现了他对对称性的极大兴趣.自从19世纪初发现了同分异构体后，关于同分异构体的计数问题长期得不到解决. 直到1874年，同时出现了三篇有关的论文，其一是德国籍化学家W. 孔那(Korner)的，讨论苯的取代物的同分异构体;其二是荷兰化学家J. H. H. 范霍夫(Van'thoff)的，讨论有机化合物的同分异构体;其三是英国数学家A. 凯莱(Cayley)的，运用树图并引入母函数来研究同分异构体的计数问题.到了20世纪30年代，美国化学家又在这方面做了更多的计算. 但是这些方法都是针对个别情况而缺乏普遍性. 在前人研究同分异构体计数问题的基础上，波利亚在1937年以「关于群、图与化学化合物的组合计算方法」(KombinatorischeAnzahlbestimmungen fr Gruppen，Graphen und ChemischeVerbindungen)为题，发表了长达110页、在组合数学中具有深远意义的著名论文.在这篇论文中推广了伯恩赛德(Burnside)引理，给出了普遍适用的一般计数方法.实际上，第一个提出这一理论的是美国一位工程师J. H.雷德菲尔德(Redfield)，他在1927年发表的论文「群化分布的理论」(The theory of groupredu-ced distribution)中解决了某种矩阵的计数问题.由于雷德菲尔德所使用的数学名词不普遍，因而这篇论文几乎没有引起人们的注意.波利亚的工作更全面、更丰富，其主要定理现已称为「波利亚计数定理」(Polya's enumeration theorem)写入组合数学的教材中，它提供了强有力的和巧妙的(对于那些仅有初等数学知识的人来说又是易于理解的)方法，对图及化合物进行计数.

王守恩

天山草 发表于 2016-10-29 15:47
这个问题需要涉及 “带有重复元素的圆排列和环排列“ 的知识。历史上解决该问题的人是数学家波利亚 ...

第一页是汇总表，后面7页（2颗珠、3颗珠、4颗珠、5颗珠、6颗珠、7颗珠、8颗珠）的规律都汇总在第一页上，请大家找一找第一页汇总表的规律。

王守恩

天山草 发表于 2016-10-29 15:33
该问题发到了数学研发网站，kastin 先生给出了 S(m, n）的公式解答：

S(1,1)=1

谢谢天山草！漂亮的公式！谢谢漂亮的公式！谢谢天山草先生！

  \(m \ 种颜色\  n(不分奇数,偶数)颗珠穿成的环，有几种穿法？\)

\(\displaystyle S(m,n)=\frac{1}{2 n}\DivisorSum(n,\EulerPhi(\#)m^{\frac{n}{\#}}\&)+\frac{1}{4}(m^{\lceil\frac{n}{2}\rceil}+m^{\lceil\frac{n+1}{2}\rceil})\)

王守恩

天山草 发表于 2016-10-29 15:33
该问题发到了数学研发网站，kastin 先生给出了 S(m, n）的公式解答：

S(1,1)=1

                  答 27 楼：杨辉三角！！！

谢谢天山草！漂亮的公式！谢谢漂亮的公式！谢谢天山草先生！

   m 种颜色 1 颗珠 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 种颜色 2 颗珠 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 种颜色 3 颗珠 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 种颜色 4 颗珠 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 种颜色 5 颗珠 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 种颜色 6 颗珠 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 种颜色 7 颗珠 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 种颜色 8 颗珠 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}

王守恩

谢谢天山草！漂亮的公式！谢谢漂亮的公式！谢谢天山草先生！

m种颜色(不分奇数偶数), n颗珠穿成的环, 有S(m,n)种穿法。具体得数见30楼。

\(\displaystyle S(m,n)=\sum_{k = 1}^{n}\frac{m^{GCD(n, k)}}{2  n}+\frac{m^{\lceil n/2\rceil} + m^{\lceil(n + 1)/2\rceil}}{4}\)

1. Table[Sum[m^GCD[n, k], {k, n}]/(2 n)
   
2. + (m^Ceiling[n/2] + m^Ceiling[(n + 1)/2])/4, {n, 1, 12}, {m, 1, 12}]

复制代码