有$n$个正方形排成一行,今用红,白,黑三种颜色给这$n$个正方形染色,每个正方形只能染一种颜色.如果要求染这三种颜色的正方形都是偶数个,问有多少种不同的染色方法.
解答:
设有$a_n$种不同的染法,则${a_n}$对应的指数型母函数为
$f(x)=left(1+dfrac{x^2}{2!}+dfrac{x^4}{4!}+cdots+dfrac{x^{2n}}{2n!}+cdots
ight)^3=left(dfrac{1}{2}{e^x+e^{-x}}
ight)^3$
$=dfrac{1}{8}sumlimits_{n=0}^{infty}{3^n+2+3(-1)^n+(-1)^n3^n}dfrac{x^n}{n!}$
故
$$a_n=
egin{cases}
0,&n extbf{为奇数}\
dfrac{3^n+3}{4}&n extbf{为偶数}
end{cases}$$
当然我们也可以直接写出$n$为偶数时的递推式:$a_n=3a_{n-2}+2(3^{n-2}-a_{n-2}),a_2=3$