染色问题中的公式An+An-1=2^(N-1)能具体的讲解下么？？背景问题：“3人传球，从甲开始到乙算一次，共传了5次，最后回到甲，共有几种传法？”然后我们老师又转换成多边形染色问题，。

Question

染色问题中的公式
An + An-1 = 2^(N-1)
能具体的讲解下么？？

背景问题：
“3人传球，从甲开始到乙算一次，共传了5次，
最后回到甲，共有几种传法？”
然后我们老师又转换成多边形染色问题，。。不懂啊``

Answer 1

答案是10
您好，
这个问题可以这样转换。不妨设三个人名字为
甲 乙 丙
为了方便描述 设
甲为红色 乙为绿色 丙为蓝色
假设传球动作耗时1单位时间
现画一个5边形 ABCDE
A的颜色表示球第1时刻在谁手上
B的颜色表示球第2时刻在谁手上
...类推
最后回到A
由题意得A为红色
因为球必须传出 所以相邻的2点颜色不同
所以问题转换成多边形染色方案总数。
染色问题:N边形中起点和起点颜色都确定，相邻两点颜色必须不同，求不同的染色方案总数。
在只有三种颜色染多边形的问题中，有公式： Fn + Fn-1 = 2^(n-1)
n为多边形边数 Fn (n>1)表示n边形的染色方案总数 特殊的，n=2时为线段
公式的说明:
化简为 Fn = 2^(n-1) - Fn-1
先对小数据检验 发现正确。
现在考虑对一个n边形染色，我们首先不考虑起点与终点的连边，从起点连续的染n个点使得相邻颜色不同，那么每次都有3-1=2种染色法，总共2^(n-1)种。
但是其中包含起点与终点颜色相同的不合法方案。
对于不合法的方案，如果现在删除终点，把起点与倒数第二点连接起来，就一定会变成一个n-1边形的合法方案，而且他们一一对应。所以用2^(n-1)减去Fn-1记得到Fn。