首页 > 代码库 > 一个环上的染色问题

一个环上的染色问题

学高中数学组合计数的时候经常在那本实验班里碰到这个问题:给一个n元环用k种颜色染色,相邻位置不同色,求方案数。高中遇到这个问题的时候nk都是很小的,因为一般都是讨论讨论瞎计数做掉。当时某吴姓同学经常说有个公式……但是那个时候我并不知道怎么推出来。今天中午吃饭的时候又看到一个讲这个问题的帖子,所以自己整理了一下发现做法还是挺多的。这个也算是经典问题了吧?

技术分享

 

(n=4,k=2的情况,有2种方案)

首先我们可以直接写出一个dp:不妨设1号点染的色是1号颜色(最终答案乘个k)设f[i,j]表示对前i个点染色,其中最后一个点染的颜色编号为j的方案数。则f[1,1]=1,f[1,j]=0(j>1).转移方程是技术分享,答案是技术分享

观察这个方程可以发现,由于对称性,f[i,2]=f[i,3]=...=f[i,k],于是可以设g[i]=f[i,1],h[i]=f[i,j](j>1),然后有f[i]=(k-1)g[i-1],g[i]=(k-2)g[i-1]+f[i-1],答案为k(k-1)g[n].写出转移矩阵技术分享

解出转移矩阵的两组特征根和特征向量

技术分享

分解初始条件的向量

技术分享

于是

技术分享

技术分享

//群里还看到NBC说了一个做法:如果不考虑1号点与n号点不同色这一限制的话(也就是把环断成链),答案是k(k-1)^n-1,然后要减去1号点与n号点不同色的方案数,发现这就是一个(n-1)元环的k染色,迭代一下之后用等比数列求和也可以做出来。但是因为输公式实在太精神污染了这个很好算,就不写了。注意有个坑:迭代应该在n=2,答案为k(k-1)的时候结束,因为n=2n=1的转化是不成立的

啊啊啊公式怎么这么难输啊我要学markdown

 

一个环上的染色问题