离散数学题，k种颜色，涂n边形的顶点，相邻顶点涂色不能相同，记涂色方法为Cn,求递归公式
1个回答
展开全部
先涂第一个点，有k种涂发，再顺时针一个一个涂，各有k-1种涂发。
关键是最后一个点该怎么涂，分两个情况：
（1）第一点和倒数第二点颜色相同：可将倒数一二两点删去，直接将第一点与倒数第三点相连，相连后形成的n-2边形有C(n-2)中涂发。而倒数第一点此时有k-1种涂法。
（2）....................................不同，此时倒数第一点有k-2种涂法。
求和得C(n)=(k-1)*C(n-2) + k**(k-2)*(k-1)^(k-2)
关键是最后一个点该怎么涂，分两个情况：
（1）第一点和倒数第二点颜色相同：可将倒数一二两点删去，直接将第一点与倒数第三点相连，相连后形成的n-2边形有C(n-2)中涂发。而倒数第一点此时有k-1种涂法。
（2）....................................不同，此时倒数第一点有k-2种涂法。
求和得C(n)=(k-1)*C(n-2) + k**(k-2)*(k-1)^(k-2)
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
