Question

排列组合。环行染色问题。要详细的解释。谢谢！

Answer 1

递推法
设n个点有f(n)种，
考虑下面染色方法，
按次序，第一个点有3种，第二个，第三个，……，第n个都有2种
所以共有
3×2^(n-1)种
但会出现第n个点和第一个点染色相同的情况，这种情况实际等效于染n-1个点的方法数，即f(n-1)
所以，
f(n)=3×2^(n-1)-f(n-1)
f(2)=6
f(3)=12-f(2)=6
f(4)=24-f(3)=18
f(5)=48-f(4)=30

追答

本题颜色较少，所以分类计数绝对不难，但我上面的方法更加好，更加适合做一些难题
分类的算法
(1) ACD颜色都不相同
3×2×1×1×1
(2) AC颜色都相同
3×1×2×2×1
(3) AD颜色都相同
3×1×2×2×1

追问

谢谢！