例析幾道競賽組合題的解法

閔書存　閔幼梅

組合數(shù)學(xué)中基本的問題之一是組合計數(shù)問題，這部分內(nèi)容在高中數(shù)學(xué)中通過排列與組合這一章節(jié)進行考察，解決組合計數(shù)問題需要學(xué)生熟練使用常見的組合計數(shù)模型，能夠靈活地設(shè)計分類與分步方法，充分利用對稱思想，靈活地將計數(shù)問題進行轉(zhuǎn)化，適當(dāng)?shù)厥褂谜y則反的思想，建立m對n的對應(yīng)關(guān)系等.本文以近年高中數(shù)學(xué)聯(lián)賽一試中的組合計數(shù)問題為例，剖析其解答過程歸納組合計數(shù)問題常見的幾種解答方法.

例1 在5×5矩陣中，每個元素都為0或1，且滿足：五行的元素之和都相等，但五列的元素之和兩兩不等，這樣的矩陣個數(shù)為.（2022年全國中學(xué)生數(shù)學(xué)奧林匹克競賽預(yù)賽A1卷第8題）

分析1：本題要求五列的元素之和兩兩不等，考慮到一列的和只能取0-5這六種情況，因此五列的列和是0、1、2、3、4、5這些數(shù)字中的5個，又考慮到五行的行和都相等，故矩陣中所有元素之和是5的倍數(shù)，經(jīng)過這樣的分析，我們得到五列的列和只能是0、1、2、3、4或者1、2、3、4、5這兩種情況.

分析2：事實上，我們可以建立五列的列和是0、1、2、3、4這種情況和五列的列和是1、2、3、4、5這種情況的一一對應(yīng)關(guān)系，只需將五列的列和是0、1、2、3、4這種情況中列和為0這一列全部填上1則唯一地對應(yīng)成五列的列和是1、2、3、4、5這種情況.反之，將五列的列和為1、2、3、4、5這種情況中的列和為5這一列全部換成0，則唯一地對應(yīng)成五列的列和是0、1、2、3、4這種情況，這表明兩種情況的計數(shù)數(shù)量相同，因此只需計算其中一種情況的計數(shù)數(shù)量即可.

分析3：考慮列和為1、2、3、4、5的情況的填數(shù)方法數(shù)，利用對稱性，五列的列和的排布方式總數(shù)量5！中的每一種對后續(xù)填數(shù)方法計數(shù)影響一致，故只需考慮圖1中從左到右的列和順序為1、2、3、4、5的情況.

分析4：又由于第一列的1放置在哪一行對后續(xù)計數(shù)影響一致，第5列已經(jīng)全部填寫了1，故只需考慮第1列的1放置在第一行的情形，此時的表格簡化為只需考慮如圖2所示的5×3的表格.

分析5：考慮第四列的0應(yīng)當(dāng)放置在何處，可以分為兩類，一類是0被放置在第一行，一類是0被放置在第二、三、四或者五行，后一類的四種情況對后續(xù)計數(shù)產(chǎn)生的影響一致，因此只需考慮其中一種情況即可.根據(jù)行和為3，部分位置的元素已經(jīng)被確定，故接下來只需對以下圖3、圖4兩種情況進行計數(shù)：

分析6：圖3情況中，根據(jù)行和為5，故從第二行第二列到第五行第三列每一行只能恰有一個1，第一行的第二列和第三列總計一個1，這樣，我們將情況A細分為第一行第二列為1以及第一行第二列為0兩種情況即可，故得到情況A的矩陣個數(shù)為4+C24；圖4情況中只需確定第二列的另外一個1放置位置即可確定矩陣，故情況B的矩陣個數(shù)為3.

綜上分析得到總的矩陣個數(shù)為（（4+C24）+4×3）×5×5！×2=26400.

點評：在本題的分析過程中，不斷地通過對稱思想簡化要填寫的表格，最后通過合理的分類與分步將問題解決，充分體現(xiàn)了對稱思想在處理組合計數(shù)問題中的作用.

例2 一個單位方格的四條邊中，若有兩條邊染了顏色i，另兩條邊分別染了異于i色的另兩種不同顏色，則稱該單位方格是“i色主導(dǎo)”的．如圖5，一個1×3方格表的表格線共含10條單位長線段，現(xiàn)要對這10條線段染色，每條線段染為紅、黃、藍三色之一，使得紅色主導(dǎo)、黃色主導(dǎo)、藍色主導(dǎo)的單位方格各有一個．這樣的染色方式數(shù)為.（2022年全國中學(xué)生數(shù)學(xué)奧林匹克競賽預(yù)賽A卷第8題）

分析1：為方便說明，我們對邊進行如下的編號為如圖6：

由對稱性，三個主導(dǎo)顏色的排列順序?qū)罄m(xù)計數(shù)的影響是相同的，因此，只需考慮從左至右三個主導(dǎo)顏色的排列順序為紅黃藍的情況.

分析2：觀察10條邊的特征，發(fā)現(xiàn)這些單位方格中的兩條公共邊最特殊，它們中的每一個都會對兩個方格的染色方式產(chǎn)生影響，因此從對象的這一特征入手進行分類.考慮到中間的方格是黃色主導(dǎo)，因此，這兩條公共邊的顏色可以同時是黃色或者其中之一為黃色，或者二者均不為黃色.下面對這三種情況分別進行計數(shù).

分析3：如果XY這兩天邊均為黃色，則邊45可任意染成紅色和藍色即可，故方法數(shù)為2；由對稱性，邊123的染色方法數(shù)與邊678的染色方法數(shù)相等.故只需考慮邊123的染色方法數(shù)，只需確定藍色邊的位置即可，故方法數(shù)為3.綜合可得此種情況下，染色方法數(shù)為2×3×3=18.

分析4：如果XY這兩邊其中之一為黃色，有三種情況需要考慮，分別是X和Y為黃色和紅色、X和Y為黃色和藍色、X和Y為紅色和黃色、X和Y為藍色和黃色，其中X和Y為黃色和紅色這種情況與X和Y為藍色和黃色這種情況具有對稱性，X和Y為紅色和黃色這種情況與X和Y為黃色和藍色這種情況具有對稱性，下面又分別考慮它們.

分析5：若X和Y為黃色和紅色，則45應(yīng)為黃藍或者藍黃，故染色方法數(shù)為2；123應(yīng)當(dāng)有兩邊為紅，一邊為藍，故染色方法數(shù)為3.678應(yīng)當(dāng)由兩邊為藍，一邊為黃，故染色方法數(shù)為3；故這種情況下的染色方法數(shù)為2×3×3=18.

分析6：若X和Y為紅色和黃色，則45應(yīng)當(dāng)有一邊為黃，一邊為藍，故染色方法數(shù)為2；123應(yīng)當(dāng)是三個顏色，故染色方法數(shù)為3！=6；678應(yīng)當(dāng)有兩邊為藍，一邊為紅，故染色方法數(shù)為3；故這種情況下的染色方法數(shù)為2×6×3=36.

分析7：如果XY這兩邊均不為黃色，則45必須均為黃色，此時有兩種情況需要考慮，一種是XY為紅色和藍色，一種是XY為藍色和紅色；若XY分別是紅色和藍色，則123應(yīng)當(dāng)是三種顏色，故染色方法數(shù)為3！=6；678應(yīng)當(dāng)也是三種顏色，故染色方法數(shù)為3！=6，故總的染色方法數(shù)為6×6=36；若XY分別是藍色和紅色，則123應(yīng)當(dāng)有兩邊為紅色一邊為黃色，故染色方法數(shù)為3；678應(yīng)當(dāng)有兩邊為藍色一邊為黃色，故染色方法數(shù)為3，總的染色方法數(shù)為3×3=9.

綜上分析可知，總的染色方法數(shù)為（（36+9）+（36+18）×2+18）×3！=1026.

點評：解決該問題需要靈活地設(shè)計分類與分步方法，同時要充分利用對稱思想減少復(fù)雜度.

例3 將6個數(shù)2，0，1，9，20，19按任意次序排成一行，拼成一個8位數(shù)（首位不為0），則產(chǎn)生的不同的8位數(shù)的個數(shù)為.（2019年全國中學(xué)生數(shù)學(xué)奧林匹克競賽預(yù)賽A卷第8題）

分析：為解決該問題，構(gòu)造兩個集合A和B，集合A中的元素是這6個數(shù)按照任意次序排成一列所能產(chǎn)生的所有不同的8位數(shù)，集合B中的元素分為如下幾類（均不包含0在首位）：數(shù)字2后面緊跟0且數(shù)字1后面不是數(shù)字9的所有排列，稱這些排列為X類排列；數(shù)字2后面不是數(shù)字0且數(shù)字1后面緊跟數(shù)字9的所有排列，稱這些排列為Y類排列；數(shù)字2后面不是數(shù)字0且數(shù)字1后面不是數(shù)字9的所有排列，稱這些排列為Z排列；數(shù)字2后面是數(shù)字0且數(shù)字1后面是數(shù)字9的所有排列，稱這些排列為W排列.需要說明的是集合A中的元素是8位數(shù)，集合B中的元素是排列，二者并不相同，比如排列2-0-19-20-1-9和排列20-19-2-0-1-9并不相同，但是它們對應(yīng)的數(shù)字20192019和數(shù)字20192019卻是相同的，接下來將排列和數(shù)字進行對應(yīng)，建立集合A和集合B中的元素的對應(yīng)關(guān)系，X類排列中的每兩個排列對應(yīng)集合A中的一個元素；Y類排列中的每兩個排列對應(yīng)集合A中的一個元素；Z類排列中的每一個對應(yīng)集合A中的一個元素；W排列中的每4個對應(yīng)集合A中的一個元素；我們用|X|表示X類排列的個數(shù)，則可以得到X=5！－4！，其中5！是數(shù)字2后面緊跟0所有排列個數(shù)，4！是數(shù)字2后面緊跟0且數(shù)字1后面緊跟數(shù)字9的所有排列個數(shù)；利用正難則反類似的可以得到Y(jié)=4×4！－4！，W=4！，再結(jié)合X+Y+Z+W=5×5！表示所有可能的排列個數(shù)，可得Z=4×5！－3×4！，綜上可得A=X/2+Y/2+Z+W/4=498.

點評：本題通過構(gòu)造兩個集合的元素之間的映射關(guān)系，巧妙地解決了求解其中一個集合的元素的個數(shù)的問題，這種方法是解決組合計數(shù)問題的常見方法之一.

以上三道試題的剖析，演示了全國高中數(shù)學(xué)聯(lián)賽的組合計數(shù)問題中幾種常見的解答方法和解答思想，總體上，解決組合計數(shù)問題可以歸納為如下思路：（1）在理解問題的基礎(chǔ)上將問題的主要特征提取出來；（2）考慮是否需要對問題進行適當(dāng)轉(zhuǎn)換；（3）根據(jù)提取的特征設(shè)置適當(dāng)?shù)姆诸惻c分步方式；（4）充分地利用對稱思想減少討論的情況數(shù)；（4）在細節(jié)處理上適當(dāng)?shù)厥褂谜y則反的思想；（5）部分不方便計數(shù)的問題可以考慮建立集合與集合之間的映射關(guān)系.