Question

日本高考排列题

一列n个小球，用红黄蓝三种颜色上色，要求相邻的小球颜色不一样。不一定每种颜色都出现。两端的小球颜色一样的时候排列数为An，两端的小球颜色不一样的时候排列数为Bn。求An和Bn。
很遗憾，下面热心网友的An=Bn=6的答案是错的。用枚举法就可以轻易知道A5=18，A6=30

Answer 1

N个球排成一列且相邻颜色不同的有3*2^(n-1)种，即An+Bn= 3*2^(n-1)；任意Bn中的一个排列在末尾放上和开头颜色一样的球得到An+1中的一个排列，反之亦然，因此An+1=Bn。将An+1=Bn代入An+Bn= 3*2^(n-1)得An-2^(n-1)= -(An+1-2^(n+1-1))，所以An-2^(n-1)是公比为1的等比数列。由于A2=0，所以An-2^(n-1)= -2*(-1)^n，An=2^(n-1)-2*(-1)^n，所以Bn =2^n+2*(-1)^n
^是乘方符号，因为没法打上下标，于是这么表示，下标就没办法了。虽然跳了一点步骤，应该可以看懂吧？

Answer 2

当球有1个2个不成立，即n>2。将球涂成3个颜色，可以理解为三种颜色的球排队。但队伍里面不一定取到全部3种颜色，因为如果n=3，依题意只能取两种颜色的球。
n=3，有3*2种=6种。比如两端的球任取一种颜色为红色，则中间一个球可以为黄色或者蓝色。
n=4，有3*2种=6种。同理两端任取一种颜色，有3种可能。中间两个球只能取2种颜色有两种排法。
n=5，有3*2种=6种。
利用归纳法，不论n的个数有多少，只有6种排法。
An=6。
n=1不成立，n>1.
n=2时，3*2种=6种。第一个球可以取3种颜色中的任一种，有3种取法。第二个只能在第一球确定下取另外两种中的一个，共有2种取法。
n=3时，3*2种=6种。第一个球3种取法，第二个球2种取法，第3个球1种取法。
n=4时，3*2种=6种。第一个球3种取法，最后一个球2种取法，中间两个球只能有一种取法。比如第一个球取了红，最后一个取了蓝，则第2、3个球只能是黄、红，即红黄红蓝。
利用归纳法，无论n为大于1的何值，取法都为6种。
Bn=6。