Question

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

Answer 1

解 （1）對(duì)于邊a₁，有3種不同的染法，由于邊a₂的顏色與邊a₁的顏色不同，
所以，對(duì)邊a₂有2種不同的染法，第三邊有一種方法，所以P（3）=6，
類似四邊形時(shí)對(duì)于邊a₁，有3種不同的染法，由于邊a₂的顏色與邊a₁的顏色不同，
對(duì)邊a₂有2種不同的染法，第三邊有2種方法，如果與a₁的顏色不同，則第四邊為1種染色方法，
如果與a₁的顏色相同，第四邊有2種染色方法，P（4）=3×2×1×1+3×2×1×2=18，
類似可求P（5）=30； …（3分）
（2）設(shè)不同的染色法有P_n種．易知．
當(dāng)n≥4時(shí)，首先，對(duì)于邊a₁，有3種不同的染法，由于邊a₂的顏色與邊a₁的顏色不同，
所以，對(duì)邊a₂有2種不同的染法，
類似地，對(duì)邊a₃，…，邊a_n-1均有2種染法．對(duì)于邊a_n，用與邊a_n-1不同的2種顏色染色，
但是，這樣也包括了它與邊a₁顏色相同的情況，
而邊a₁與邊a_n顏色相同的不同染色方法數(shù)就是凸n-1邊形的不同染色方法數(shù)的種數(shù)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．
綜上所述，不同的染色方法數(shù)為P_n=2ⁿ+（-1）ⁿ•2，．…（10分）
分析：（1）直接利用著色方案分別求出P（3），P（4），P（5）；
（2）直接利用類比推理，推出凸n（n≥3）邊形的邊染色與凸n-1邊形的不同染色方法數(shù)的種數(shù)P_n-1的關(guān)系，P_n=3×2^n-1-P_n-1，然后求出染色方法數(shù)為P_n=2ⁿ+（-1）ⁿ•2，
點(diǎn)評(píng)：本題考查分步計(jì)數(shù)原理、分類計(jì)數(shù)原理的綜合應(yīng)用，涉及幾何圖形有關(guān)的涂色問(wèn)題，分析時(shí)注意結(jié)合圖形分析．