输入n，k，求着色方案的数量
by 377isrubbish @ 2017-03-25 14:21:09
#你那个3-3环中列出的1和4不是本质相同的环吗？
by GoAway @ 2017-03-25 15:53:56
组合数学啊
Ci,j表示j个选i个的方案数
n=3,k=3就是 C1,3\*C1,2\*C1,1
所以你只要考虑对于每一个点染色，合法情况有几种可以选就可以了，因为是环，多以比较简单//这种方法应该是没有bug
by 张仪 @ 2017-03-25 16:02:02
@[GoAway](/space/show?uid=39497) VO，某韬大叔叔？hhh
by 张仪 @ 2017-03-25 16:03:12
@[GoAway](/space/show?uid=39497) 交换任意两节点的颜色，算另外一种着色方案
by 377isrubbish @ 2017-03-25 17:33:50
没有这么简单。
课上讲了一大堆还是没有推出来.
by 377isrubbish @ 2017-03-25 17:34:43
或许可以换种表示方式：
一条线段上有n个点，对它们进行k染色，要求任意相邻二点不同色，第一个点和最后一个点不同色。
by 377isrubbish @ 2017-03-25 18:58:41
@[GoAway](/space/show?uid=39497) @[张仪](/space/show?uid=18085)
如果没有第二个要求限制，那么f(n,k)=k\*(k-1)^(n-1)。加上第二个要求限制即减去f(n-1,k)的情况。
k\*(k-1)^(n-1)-k\*(k-1)^(n-2)= ### k\*(k-1)^(n-2)\*(k-2)。
如果有错误请指出，私信我，谢谢！
by 377isrubbish @ 2017-03-25 19:02:33
哎呀，Markdown玩多了 【滑稽】
by 377isrubbish @ 2017-03-25 19:04:31
@[377isrubbish](/space/show?uid=37526) 我懂你的意思了，可以线性递推求解，高级点的可以矩阵、推通项。
递推式 
通项 
by GoAway @ 2017-03-25 19:17:14