数学问题
一般的排也可以,就是分情况考虑,个人觉得考虑不相邻的三份的颜色,再排剩下的比较好,但都比较繁琐
下面采用递推数列来算:
把问题扩展为把:一个圆分成n份,现在有4种颜色,给这个圆涂色,要求相邻不能涂同一颜色,求共有几种涂法。 设涂法数目为A(n)。(怕下标写了很混乱所以这么写)
依次把n份编号为1,2,。。。,n
这么考虑:对每一种涂法,观察第1份和第n-1份的颜色,只有两种情况:不同或者相同。
(1)当不同的时候,我们把第n份拿走,让第1份和第n-1份相邻(随便你怎么想,就当把那两块拉一拉靠在一起好了),由于第1份和第n-1份颜色不同,这实际上就构成了“一个圆分成n-1份,现在有4种颜色...全部
一般的排也可以,就是分情况考虑,个人觉得考虑不相邻的三份的颜色,再排剩下的比较好,但都比较繁琐
下面采用递推数列来算:
把问题扩展为把:一个圆分成n份,现在有4种颜色,给这个圆涂色,要求相邻不能涂同一颜色,求共有几种涂法。
设涂法数目为A(n)。(怕下标写了很混乱所以这么写)
依次把n份编号为1,2,。。。,n
这么考虑:对每一种涂法,观察第1份和第n-1份的颜色,只有两种情况:不同或者相同。
(1)当不同的时候,我们把第n份拿走,让第1份和第n-1份相邻(随便你怎么想,就当把那两块拉一拉靠在一起好了),由于第1份和第n-1份颜色不同,这实际上就构成了“一个圆分成n-1份,现在有4种颜色,给这个圆涂色,相邻不能涂同一颜色”的一种涂法,按照假设共有A(n-1)种。
再把第n份加上去,不能和第1和第n-1份颜色相同,只有两种颜色,所以这种情况下有2A(n-1)种涂法。
(2)当相同的时候,同样拿走第n份和第n-1份,因为n-2份的颜色不和n-1份相同,而n-1的颜色和第1块相同,所以n-2的颜色不和第1块相同,同样让n-2和第1块相邻,就构成了“一个圆分成n-2份,现在有4种颜色,给这个圆涂色,相邻不能涂同一颜色”的一种涂法,按照假设共有A(n-2)种。
再把第n-1份和第n份加上去,由于这时第n-1份和第1份颜色相同,没有选择的余地只有一种涂法,第n份与第1份,第n-1份的颜色都不相同,但1和n-1的颜色相同,所以有3种涂法。这种情况下有3A(n-2)种涂法。
所以A(n)=2A(n-1)+3A(n-2)
解这个差分方程,特征方程为x^2=2x+3,得到x=-1,3
所以设A(n)=B(-1)^n+C3^n
代入A(2)=4*3=12,A(3)=4*3*2,(像A(1)这种边界条件最好不要代入)解得B=3,C=1
所以A(n)=3(-1)^n+3^n
A(6)=3(-1)^6+3^6=732
不好意思,刚才答案写错了
其实直接排也不算太困难:
4*3^3+3*4*3*3*2^2+4*3*2*2^3=732。
收起