Question

怎样证明下面的公式

以h(m,n)表示用m种颜色去涂2*n的棋盘，使得相邻格子异色的涂色方案数，求证 h(m,n)=m(m-1)(m*m-3m+3)^(n-1)

Answer 1

假设已经涂好前n-1个，方案数为h(m,n-1)，剩下2个格子，加上相邻的两个格子，编号为
1颜色a 3颜色x
2颜色b 4颜色y
因为已经编号到n-1，所以a和b已经确定了，现在给x分情况
x=b的时候：x已经确定，y两侧都是b色，所以有m-1种选择
x!=b的时候：x不是a和b颜色，有m-2种，y不是b和x的颜色，有m-2种，即(m-2)(m-2)
所以有递推关系：h(m,n) = h(m,n-1)*(m-1+(m-2)(m-2))
h(m,n)/h(m,n-1) = m^2-3m+3
h(m,n-1)/h(m,n-2) = m^2-3m+3
……
h(m,2)/h(m,1) = m^2-3m+3

而h(m,1)很简单等于m*(m-1)，
上面左侧乘起来就得到你要的结果了

最快回答，求给分。。。