Question

6．設正整數(shù)n≥2，對2×n格點鏈中的2n個結點用紅（R）、黃（Y）、藍（B）三種顏色染色，左右端點中的三個結點己經(jīng)染好色，如圖所示．若對剩余的2n-3個結點，要求每個結點恰染-種顏色，相鄰結點異色，求不同的染色方法數(shù)．

Answer 1

分析 需要分類討論，記P=R（或Y），Q=B時的著色數(shù)目為a_n，記P=B，Q=R（或Y）時的著色數(shù)目為b_n，記P=R，Q=Y或者P=Y，Q=R時的著色數(shù)目為c_n，根據(jù)端點的個數(shù)不同，分別求出找到相應的規(guī)律，即可得到a_n=2b_n-1+c_n-1=a_n-1+b_n-1+c_n-1=3^n-2，問題得以解決．

解答 解：2×n格點鏈中的2n個結點用紅（R）、黃（Y）、藍（B）三種顏色染色，其中最左端點染成紅色與黃色，設右端點染色為P，Q，如圖所示：

記P=R（或Y），Q=B時的著色數(shù)目為a_n，
記P=B，Q=R（或Y）時的著色數(shù)目為b_n，
記P=R，Q=Y或者P=Y，Q=R時的著色數(shù)目為c_n，
我們注意到：（1）若右端沒有約束時，每增加一個格子都有3種不同的著色方法，則a_n+b_n+c_n=3^n-1，
（2）由對稱性，即將圖形山下翻轉，并且顏色R與Y互換，可知a_n=b_n，
（3）考慮相互的遞推特征，如圖：則a_n=2b_n-1+c_n-1，

所以，$\left\{\begin{array}{l}{{a}_{n}+_{n}+{c}_{n}={3}^{n-1}}\\{{a}_{n}=_{n}}\\{{a}_{n}=2_{n-1}+{c}_{n-1}}\end{array}\right.，n∈N*$
這樣a_n=2b_n-1+c_n-1=a_n-1+b_n-1+c_n-1=3^n-2，
即為問題所求的不同的染色方法數(shù)．

點評 本題考查了著色問題，關鍵是需要分類討論，以及找到相應的規(guī)律，屬于難題．