染色问题

kastin

用m种不同颜色给n+1边形的顶点染色，要求相邻点不能同色，问染色方式有多少种？

wayne

旋转对称算一种还是多种

kastin

wayne 发表于 2013-12-7 13:17
旋转对称算一种还是多种

这里的多边形是一般的多边形，因此不考虑正多边形情况。

Lwins_G

可以用简单的递推解决这个问题。为叙述方便，我们假设多边形是$n$边形而用$m$种颜色染色。
把多边形先展开为折线段（随意选取一条边，去掉这条边），把顶点标号为$1$至$n$。
定义$f_{i,j}$表示给一个有$i$个顶点的折线段的顶点各自染上$m$种颜色中的一种，第$i$个顶点恰染第$j$种颜色的所有合法的方案数目。特别地，第一个顶点只能染第一种颜色。
那么有
$f_{1,1}=1,\ f_{1,2}=f_{1,3}=\cdots=0$
$f_{i+1,j}=\sum_{k=1}^{m}f_{i,k} - f_{i,j}$
而稍加分析（请自行思考正确性）可得出原题答案应为$m \cdot (f_{n,2}+f_{n,3}+\cdots+f_{n,m})$。
而如何化简上面的递推，然后推出答案也交给大家思考。（答案并不复杂）

mathe

m色n边数目如果是a(n,m),对于n边，第一个点有m种染色方案，然后后面每个同前一个不同，有m-1种方案，唯一问题是最后一点可能和第一点同色，这些方案可将这两点合并对应n-1点方案得出a(n,m)+a(n-1,m)=m(m-1)^(n-1)