江西省萍鄉(xiāng)市上栗中學 (337009) 黃玉嬌

對一類環(huán)形染色問題的探究

江西省萍鄉(xiāng)市上栗中學 (337009) 黃玉嬌

題1 (2003年全國高考理科第15小題)某城市在中心廣場建造一個花圃，花圃分為6個部分(如圖1)，現(xiàn)要栽種4種不同顏色的花，每部分栽種一種且相鄰部分不能栽種同樣顏色的花，不同的栽種方法有多少種？

圖1

原解答如下：從題意來看6部分種4種顏色的花，又從圖形看知必有2組同顏色的花，可從同顏色的花入手分類求解．

(1)②與⑤同色，則③⑥也同色或④⑥也同色，所以共有N1=4×3×2×2×1=48種；

(2)③與⑤同色，則②④或⑥④同色，所以共有N2=4×3×2×2×1=48種；

(3)②與④且③與⑥同色，則共有N3=4×3×2×1=24種．

∴共有N=N1+N2+N3=48+48+24=120種．

圖2

題2 (2001全國高中數(shù)學聯(lián)賽第12題)在一個正六邊形的六個區(qū)域栽種觀賞植物(如圖2)，要求同一塊中種同一種植物，相鄰兩塊種不同的植物，現(xiàn)有4種不同的植物可供選擇，則有多少種栽種的方案？

原解答如下：為了敘述方便起見，我們給六塊區(qū)域依次標上字母A、B、C、D、E、F．按間隔三塊A、C、E種植植物的種數(shù)，分以下三類．

(1)若A、C、E種同一種植物，有4種種法．當A、C、E種植后，F(xiàn)可從剩余的三種植物中各選一種植物(允許重復(fù))，各有3種方法．此時共有4×3×3×3=108種方法．

根據(jù)加法原理，總共有N=108+432+192=732種栽種方案．

近年來，各類高考復(fù)習參考資料中涉及的田字種草，雨傘著色等，其中的問題都是一種環(huán)形著色問題.這些問題所提供的參考答案都是一些利用分類、分步，排列組合原理的求法，其計算之復(fù)雜，難度之大，令廣大學生難以接受.本文介紹一種利用遞推數(shù)列導出通項公式的方法，給出環(huán)狀著色問題的統(tǒng)一解法.

先看題1.首先，第1塊地上可以先種植，共有4種種法.余下的2-6塊地就是一個五環(huán)著三色的問題.先瞻前不顧后，2,3,4,5，6塊地的種植方法有3×24=48種，但這樣下去，第6塊有可能與第2塊地同色，其效果上就好比四環(huán)種三色，設(shè)其方法數(shù)為a4，若第6塊與第2塊不同色，則是5環(huán)著3色問題，設(shè)其方法數(shù)為a5，這樣由分步計數(shù)原理便有a5+a4=3×24=48，這里a4代表四環(huán)著3色，易知方法有3×2×2+3×2×1×1=18種，從而a5=30，本問題的最后結(jié)果是4×30=120種.

同樣分析題2.設(shè)6環(huán)著4色方法有a6，5環(huán)著4色方法有a5，4環(huán)著4色方法有a4，3環(huán)著4色方法有a3，2環(huán)著4色方法有a2，則a2=4×3=12種，a3+a2=4×32,a3=36-12=24，a4+a3=4×33=108，從而a4=84，a5+a4=4×34，則a5=240，a6+a5=4×35，求得a6=972-240=732種.

一般地，下面我們探索一個n環(huán)土地著4色問題.

圖3

引理 若一個組合數(shù)列{an+1-pan}是一個公比為q的等比數(shù)列，則組合數(shù)列{an+1-qan}必是一個公比為q的等比數(shù)列.

證明：假設(shè)有an+1-pan=q(an-pan-1)?an+1-qan=p(an-qan-1)即證.

特別地，當an+1-pan=c(c為常數(shù))，{an+1-an}必是一個以p為公比的等比數(shù)列.

由an+an-1=4×3n-1得an+1+an=4×3n，由上面的引理可知an+1-3an=(a3-3a2)×(-1)n-2=-12×(-1)n，上面兩式相減可得4an=4×3n+12×(-1)n?an=3n+3×(-1)n.

這樣便得出一個4色著n環(huán)，相鄰區(qū)域不同色的方法總數(shù)an=3n+3×(-1)n.

類比上述方法，不難證明：m色著n環(huán)，相鄰不同色顏色不一定用全的方法數(shù)為an=(m-1)n+(m-1)(-1)n.

證明：an+1+an=m(m-1)n-1，an+1-(m-1)an=[a3-(m-1)a2](-1)n-2，注意到a3=m(m-1)(m-2)，a2=m(m-1)，(-1)n-2=(-1)n，即可得an=(m-1)n+(m-1)(-1)n.

注：本文得到我校肖鋒老師的指導，在此特別致謝！