一个 $7\times 1$ 的板子被型如 $m\times 1$ 的瓷砖无重叠覆盖。每块瓷砖可以覆盖任意数目相邻的正方形，并且每块瓷砖完全落在板上。瓷砖的颜色可为红蓝绿。 $N$ 为整块板子所用瓷砖包含了红蓝绿三种颜色的覆盖方案数。例如，依次用 $1\times 1$ 的红瓷砖，$2\times 1$ 的绿瓷砖，$1\times 1$ 的绿瓷砖，$2\times 1$ 的蓝瓷砖，$1\times 1$ 的绿瓷砖各一块的方案及满足条件。求 $N$ 模 $1000$ 的值
【难度】
【出处】
2013年第31届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
106
【解析】
设 $n\text{,}x$ 分别为板子长度和颜色数。由隔板定理，将板子分为 $k$ 块的方法数为 $\left(\begin{matrix}
n-1 \\
k-1 \\
\end{matrix}\right)$ 。每部分有 ${{x}^{k}}$ 种染色方法。因此总分块染色方法数为 $\displaystyle \chi \left( n\text{,}x\right)\text{=}\sum\limits_{k\text{=}1}^{n}{\left( \begin{matrix}n-1 \\
k-1 \\
\end{matrix}\right){{x}^{k}}\text{=}}x\sum\limits_{k\text{=0}}^{n-1}{\left( \begin{matrix}n-1 \\
k \\
\end{matrix}\right){{x}^{k}}\text{=}}x{{\left( x+1 \right)}^{k-1}}$ 。代入条件中的 $n\text{=}7$，则 $\chi\left( 7\text{,}3 \right)-\left( \begin{matrix}3 \\
2 \\
\end{matrix} \right)\chi \left( 7\text{,2}\right)+\left( \begin{matrix}& 3 \\
& 1 \\
\end{matrix}\right)\chi \left( 7\text{,1} \right)\text{=}3\cdot {{4}^{6}}-3\left( 2\cdot{{3}^{6}} \right)+3\left( 1\cdot {{2}^{6}} \right)\text{=}8106$ 。所求值为 $106$
n-1 \\
k-1 \\
\end{matrix}\right)$ 。每部分有 ${{x}^{k}}$ 种染色方法。因此总分块染色方法数为 $\displaystyle \chi \left( n\text{,}x\right)\text{=}\sum\limits_{k\text{=}1}^{n}{\left( \begin{matrix}n-1 \\
k-1 \\
\end{matrix}\right){{x}^{k}}\text{=}}x\sum\limits_{k\text{=0}}^{n-1}{\left( \begin{matrix}n-1 \\
k \\
\end{matrix}\right){{x}^{k}}\text{=}}x{{\left( x+1 \right)}^{k-1}}$ 。代入条件中的 $n\text{=}7$，则 $\chi\left( 7\text{,}3 \right)-\left( \begin{matrix}3 \\
2 \\
\end{matrix} \right)\chi \left( 7\text{,2}\right)+\left( \begin{matrix}& 3 \\
& 1 \\
\end{matrix}\right)\chi \left( 7\text{,1} \right)\text{=}3\cdot {{4}^{6}}-3\left( 2\cdot{{3}^{6}} \right)+3\left( 1\cdot {{2}^{6}} \right)\text{=}8106$ 。所求值为 $106$
答案
解析
备注
