一个涂色问题：用三种颜色给由n个区域组成的直线型结构涂色,其中有一种颜色不能相邻!问有多少涂色的方法

Question

一个涂色问题：用三种颜色给由n个区域组成的直线型结构涂色,其中有一种颜色不能相邻!问有多少涂色的方法

Answer 1

题目中：其中（至少）有（且仅有）,没表达清楚.
总涂色方法3^n
至少有：
先求都不相邻：3×2^(n-1),第一个可以随便选,其他n-1个里每个只能选2种,因为要和前一个不同
所以答案是3^n-3×2^(n-1)；
有且仅有：
选一种颜色：3
第一格：随便涂是3
第二格：（第一格P1的概率是该色,×2,2/3的概率是它色×3）
第三个：（第二格有（1/3）^2+2/3×（1/3）的概率是该色,×2,1-P2的概率×3）
类推并作乘积
其中PN=（1/3）^(n-1)+(1/3)*(2/3)^(n-1)
得到的乘积再乘3就是结果