排列组合高手进

Question

将一个圆分成n个不相等的扇形，并且用红、黄、蓝三种颜色给扇形染色，不许相邻的扇形有相同的颜色，问共有多少种染色方法？
答案是一个递推数列，请高手给出想法和过程

Answer 1

解答：
设n个扇形时，共有an种染色方法
则 a1=A(3,1)=3,a2=A(3,2)=6，a3=A(3,3)=6,a4=18
n≥3时，
当有n+1个扇形时，共有a(n+1)种染色方法
当有n+2个扇形时，
分类考虑
（1）相当于在n+1个扇形时，加入1个扇形
即在原来的任意两个扇形中插入1个，
注意到这两个扇形的颜色是不同的，
∴ 新扇形的染色方法只有一种
（2）相当于在n个扇形时，加入1个扇形（注意是1个，并且n=1时无法使用此规律）
∴ 即相当于将原来的任意一个扇形一分为二，在中间插入1个新扇形
此时分开的两个扇形是同色的
∴ 新扇形的染色方法有两种
∴ a(n+2)=a(n+1)+2a(n) n≥2
a1=3,a2=6,a3=6

如果写成n与n-1,n-2的形式
为a(n)=a(n-1)+2a(n-2) n≥4
a1=3,a2=6,a3=6

Answer 2

设 An 为染色方法数， n =1,2,...
A1=3, A2=6
对 n>2, ：

将n个位置依次称为 1，2，。。。，n
任给An种排法中的一个排法。 然后去掉第n个扇形，（即把间隔第n-1个与第n个扇形的半径去掉，把第n个扇形上染上与第n-1个扇形同样的颜色），两种情形：
1.第n-1个与第1个扇形的颜色不同。于是 这成为了个圆分成n-1个不相等的扇形，然后按规定着色的A（n-1)中的一种。而且这种情形的对应关系是1-1的。
2.第n-1个与第1个扇形的颜色相同。这时，可以把第n-1个与第1个扇形看成合并成一个了。于是 这成为了个圆分成n-2个不相等的扇形，然后按规定着色的A（n-2)中一种。这种情形的对应关系是 2-1 的。 例如 1 红 n黄 n-1红 ； 1红 n蓝 n-1红 两个排法别的位置的颜色如果都相同的话， 去掉 第n个位置的黄 后，得到的染色完全共同。

于是
对 n>2, 有：
An=A（n-1)+2A(n-2)

Answer 3

假设分成n份的涂法有A(n)种
对于分成n+1份的情况，考虑还剩某一格没涂，相邻两侧的颜色相同时可以将其看为是n-1的问题（将两块看成一块则满足n-1的要求），该格有两种涂法（即与两侧的颜色不同），故为A(n-1)*2；对于两侧颜色不同的情况，则可以看成n的问题，只有一种涂法，故为A(n)
所以A(n+1)=A(n)+2*A(n-1)

分类讨论啊,NUM代表某一块着色的方法,则NUM=1,2或3

分两种情况

1.第N块相邻的两块颜色不同,这样第N块的NUM=1,由于其相邻两块颜色不同,那么将第N块拿掉也不影响整个染色方法.即NUM*a[n-1]=a[n-1]

2.第N块相邻的两块颜色相同,这样第N块的NUM=2,由于其相邻两块颜色相同,那么将其中的一块拿掉也不影响整个染色方法,拿掉这两块后又构成了一个整圆.即NUM*a[n-2]=2*a[n-2]

Answer 4

 

希望我的回答对你有帮助，采纳吧O(∩_∩)O！