Question

對一個邊長互不相等的凸n（n≥3）邊形的邊染色，每條邊可以染紅、黃、藍三種顏色中的一種，但是不允許相鄰的邊有相同的顏色．所有不同的染色方法記為P（n）
（1）求P（3），P（4），P（5）； 
（2）求P（n）

Answer 1

【答案】分析：（1）直接利用著色方案分別求出P（3），P（4），P（5）； 
（2）直接利用類比推理，推出凸n（n≥3）邊形的邊染色與凸n-1邊形的不同染色方法數的種數P_n-1的關系，P_n=3×2^n-1-P_n-1，然后求出染色方法數為P_n=2ⁿ+（-1）ⁿ•2，
解答：解  （1）對于邊a₁，有3種不同的染法，由于邊a₂的顏色與邊a₁的顏色不同，
所以，對邊a₂有2種不同的染法，第三邊有一種方法，所以P（3）=6，
類似四邊形時對于邊a₁，有3種不同的染法，由于邊a₂的顏色與邊a₁的顏色不同，
對邊a₂有2種不同的染法，第三邊有2種方法，如果與a₁的顏色不同，則第四邊為1種染色方法，
如果與a₁的顏色相同，第四邊有2種染色方法，P（4）=3×2×1×1+3×2×1×2=18，
類似可求P（5）=30； …（3分）
（2）設不同的染色法有P_n種．易知．
當n≥4時，首先，對于邊a₁，有3種不同的染法，由于邊a₂的顏色與邊a₁的顏色不同，
所以，對邊a₂有2種不同的染法，
類似地，對邊a₃，…，邊a_n-1均有2種染法．對于邊a_n，用與邊a_n-1不同的2種顏色染色，
但是，這樣也包括了它與邊a₁顏色相同的情況，
而邊a₁與邊a_n顏色相同的不同染色方法數就是凸n-1邊形的不同染色方法數的種數P_n-1，
于是可得P_n=3×2^n-1-P_n-1，
P_n-2ⁿ=（P_n-1-2^n-1）．
于是P_n-2ⁿ=（-1）^n-3（P₃-2³）=（-1）^n-1•（-2），
P_n=2ⁿ+（-1）ⁿ•2，n≥3．
綜上所述，不同的染色方法數為P_n=2ⁿ+（-1）ⁿ•2，．…（10分）
點評：本題考查分步計數原理、分類計數原理的綜合應用，涉及幾何圖形有關的涂色問題，分析時注意結合圖形分析．