題根（計數(shù)原理）

倪偉

題 （1）如圖1，將一個四棱錐P-ABCD的每個頂點染上一種顏色，并使同一條棱的兩端異色，若只有5種顏色可供使用，求不同的染色方法總數(shù).

（2）甲、乙、丙3人互相傳1只籃球，開始球在甲手中，經(jīng)過5次傳球后，球還在甲手中，求不同的傳球方法總數(shù).

一、尋根

這兩道題目的共同點在于都是計數(shù)問題，計數(shù)問題最根本的解決方法是一一數(shù)之（枚舉法）和綜合利用計數(shù)原理（分類與分步計數(shù)原理）.對于題（2），方法種數(shù)不多，可以使用枚舉法，但是為了更好地解決一類問題，我們常常需要建立一些數(shù)學模型.

如若題（1）中去掉“四棱錐”的這一包裝，題即變?yōu)椋河?種顏色給P，A，B，C，D5個點染色，每個點染一種顏色，相鄰兩點不同色.五點中，除A與C、B與D不相鄰，其余都相鄰，求不同的染法種數(shù).在解決該問題時，我們可以聯(lián)想計數(shù)問題中的一道經(jīng)典染色問題（見題根）.

題（2）是一個傳球問題，和題（1）能否聯(lián)系起來呢？亦即是要找到題中的“點”和“顏色”，若我們將甲、乙、丙看作“點”，傳球方式看成在染色，發(fā)現(xiàn)難以轉(zhuǎn)化，因為無法理解相鄰異色.而本題中隱藏條件“自己不能傳給自己”疑似和“相鄰兩點不同色”相關(guān)，因此我們可以試著將傳給誰看成染什么色，把5次傳球看作5個“點”，問題即轉(zhuǎn)化為：用紅、黃、藍三種顏色給P，A，B，C，D5個點染色，每個點染一種顏色，相鄰兩點不同色，其中點D只能染紅色，P，A，B，C，D圍成一圈，依次相鄰，如圖2所示，因此我們可以發(fā)現(xiàn)這兩道題都可以看成同一類問題——染色問題.

二、題根

題根：如圖3，用5種不同的顏色給圖中4個區(qū)域染色，每個區(qū)域染一種顏色，要使相鄰區(qū)域不同色，求不同的染色方法種數(shù).

分析一：首先我們要搞清本題需要完成的一件事——將4塊區(qū)域染好顏色.

這件事我們分四步完成：

第一步：我們?nèi)?號區(qū)域，共有5種方法；

第二步：染2號區(qū)域，只能從余下的顏色中選一種，共有4種方法；

第三步：染3號區(qū)域，由于其和2號相鄰，因此也有4種方法；

第四步：染4號區(qū)域，4號和1號與3號均相鄰，而3號與1號可能同色，也可能異色，因此我們需要重新對3號區(qū)域的染色分析.完成這件事我們將其分為兩類：第一類是當3號與1號同色，則染3號區(qū)域只有1種方法，此時染4號區(qū)域，共有4種方法；第二類是當3號與1號異色，則染3號有3種方法，此時染4號區(qū)域，共有3種方法.

因此共計有5×4×（1×4+3×3）=260種方法.

分析二：上述方法，是按區(qū)域進行分步染色，我們也可以理解為這樣完成一件事——先選好顏色，再染色.通過觀察，1號區(qū)域和3號區(qū)域、2號區(qū)域和4號區(qū)域不相鄰，這兩組區(qū)域可以同色，也可以異色，因此4塊區(qū)域用到2、3或4種不同的顏色.

完成這件事我們可以分三類：

于是我們可以將該問題一般化：

用m種不同的顏色給圖4中n個區(qū)域染色，每個區(qū)域染一種顏色，要使相鄰區(qū)域不同色，求不同的染色方法種數(shù).

我們試著按區(qū)域進行分步染色，1號區(qū)域有m種方法，2號區(qū)域有（m-1）種方法，3號區(qū)域有（m-1）種方法……（n-1）號區(qū)域有（m-1）種方法，最后染n號區(qū)域時，需要考慮1號和（n-1）號是否同色，而它們是否同色，還需思考1號和（n-2）號是否同色……如果直接去分類，就很困難了.但我們換個角度，暫不考慮n號區(qū)域受1號區(qū)域影響，直接染n號區(qū)域時，出現(xiàn)兩類：一類是1號區(qū)域和n號區(qū)域異色，這是我們需要的情況；另一類是1號區(qū)域和n號區(qū)域同色，這是我們不需要的，而這種情況中，我們將1號區(qū)域和n號區(qū)域看成整體，就相當于用m種不同的顏色給（n-1）個區(qū)域染色，即用遞推關(guān)系去解決問題.

通過將問題一般化，我們就得到了一個涂色問題的模型，亦即該類問題的“題根”.三、解答（1）第一步，先將P點染色，共有5種方法；第二步，再染其他4個點，相當于題根故本題共有5×84=420種方法.

（2）方法一：枚舉法（畫出樹狀圖，如圖5所示）.其右10種.

計數(shù)問題中有很多經(jīng)典的模型，可以看作“題根”，在解決一些新的問題時，我們試著將問題轉(zhuǎn)化為與題根相關(guān)的問題，會達到事半功倍的效果.