两个计算原理中的染色问题将一个五棱锥的每个顶点染上一种颜色,使同一条棱的两端点异色,如果只有4种颜色可供使用,那么不同的

两个计算原理中的染色问题
将一个五棱锥的每个顶点染上一种颜色,使同一条棱的两端点异色,如果只有4种颜色可供使用,那么不同的染色方法总数是多少?
我想的是先确定顶点的颜色,有4种选择,然后确定底面的一个端点颜色,有3种选择,再分对角是否同色,但老是算到96种方法,答案是120种,应该还漏了一点.
跪求赐教!
三寸旧城 2024-04-28 悬赏6金币 已收到1个回答
赞

zyleg6125

共回答了53个问题采纳率：90.5%

"我想的是先确定顶点的颜色,有4种选择," 下面继续：
先确定顶点的颜色,有4种选择. 然后问题转化成三种色用在下面的五个点上.
设 f(n) 是三种色用在圆环上的n个点 使得相邻异色的个数.
f(3) = 6, f(4) = 18. 然后一般有
f(n+2) = f(n+1) + 2f(n), n>= 3
证明： 对n+2个点的, 指定一个点 a2, 两旁分别称 a1, a3. 去掉a2, 成n+1个点,如果 a1, a3 异色, 成为 f(n+1) 之一. 如果 a1,a3同色, 合并a1,a3, 成为 n个点, 但这时, 因为 a1,a3同色, 所以 有两个选择染色方法, 别的都相同,只有 a2 不同. 去掉a2 合并a1,a3, 后成为 相同的n个点染色方法. 所以总数是 2f(n).
于是 f(5)= 18+2*6=30
总数为 4×30 = 120
15
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2018 - 2024 XGT8.CN - 西瓜解题吧
西瓜单词 | 建筑试题 | 会计师试题
闽ICP备14005894号-7