王慧興(正高級(jí)教師 特級(jí)教師)

(清華大學(xué)附屬中學(xué))

組合計(jì)數(shù)是強(qiáng)基計(jì)劃?？嫉谋乜碱}目,但現(xiàn)行高中數(shù)學(xué)課標(biāo)弱化了組合計(jì)數(shù)的教學(xué)要求.滿足于常態(tài)數(shù)學(xué)學(xué)習(xí)難以應(yīng)對(duì)強(qiáng)基計(jì)劃校考,因此學(xué)生在強(qiáng)基備考時(shí)很有必要系統(tǒng)地掌握組合計(jì)數(shù)問(wèn)題的探究、求解策略.

1 知識(shí)與技能

1.1 知識(shí)梳理

表1

1.2 要點(diǎn)解析

(1)滿足不定方程x1＋x2＋…＋xn＝m(m,n∈N?)的一個(gè)有序數(shù)組(x1,x2,…,xn),稱為其一個(gè)解,其正整數(shù)解(xi∈N?,i＝1,2,…,n)與非負(fù)整數(shù)解(xi∈N,i＝1,2,…,n)可以相互轉(zhuǎn)化.現(xiàn)探求其正整數(shù)解個(gè)數(shù),這里先給出一種求法——插板法.

把m＝1＋1＋…＋1想象成沒(méi)有區(qū)別的m個(gè)小球,把變量x1,x2,…,xn想象成n個(gè)不同的盒子,轉(zhuǎn)化為求把這m個(gè)相同的小球裝入n個(gè)不同的盒子里的不同裝法數(shù).

我們先把m個(gè)相同的小球排成一行,只有1種方法,再?gòu)膍－1個(gè)空隙里任選n－1個(gè)空隙插入沒(méi)有區(qū)別的隔板,把小球分成n段,最后逐段依次定序裝入n個(gè)盒子里,這種不同裝法數(shù)就等于分段方法數(shù),因此,按照方程對(duì)變量x1,x2,…,xn賦值得到的方程的正整數(shù)解(x1,x2,…,xn)個(gè)數(shù)就是,其中m＞n.

對(duì)方程x1＋x2＋…＋xn＝m的任一非負(fù)整數(shù)解(x1,x2,…,xn),由x1＋x2＋… ＋xn＝m,得(x1＋1)＋(x2＋1)＋…＋(xn＋1)＝m＋n,令xi＋1＝y(tǒng)i(i＝1,2,…,n),則(x1＋1,x2＋1,…,xn＋1)就是方程y1＋y2＋…＋yn＝m＋n的一個(gè)正整數(shù)解.這就給出原方程的非負(fù)整數(shù)解與新方程的正整數(shù)解之間的一一對(duì)應(yīng)關(guān)系,所以原方程的非負(fù)整數(shù)解的個(gè)數(shù)是

(2)容斥原理:有限集合X的元素個(gè)數(shù)記作|X|,則n個(gè)有限集合Ai(1≤i≤n)的并集元素個(gè)數(shù)算法為

這個(gè)算法稱為容斥原理,當(dāng)其中任意兩個(gè)集合交集都是空集時(shí),就是加法原理.

(3)映射轉(zhuǎn)移:兩個(gè)有限集合A,B之間的映射f:A→B,如果f是單射,則|A|≤|B|;如果f是滿射,則|A|≥|B|;如果f是雙射,則|A|＝|B|;倍數(shù)映射——B中每個(gè)元素在A中都恰有k個(gè)原像,則|A|＝k|B|.

(4)轉(zhuǎn)化化歸:情境轉(zhuǎn)化是組合計(jì)數(shù)常態(tài),通過(guò)情境轉(zhuǎn)化,在新情境中計(jì)數(shù)對(duì)象之間邏輯關(guān)系清晰,使得分步、分類(lèi)變得容易,便于整體把握,從根本上化難為易.“轉(zhuǎn)化化歸”是一種思想、觀點(diǎn),“映射轉(zhuǎn)移”就是一種典型的具體策略,“插板法”又是映射轉(zhuǎn)移方法的一種具體表現(xiàn).由于計(jì)數(shù)情境的多樣性,轉(zhuǎn)化化歸不僅表現(xiàn)多樣,而且往往富有技巧性.下面再給出探究上述不定方程兩類(lèi)解的個(gè)數(shù)的另一種轉(zhuǎn)化方法.

記方程x1＋x2＋…＋xn＝m(m＞n)的所有正整數(shù)解構(gòu)成集合A.任取(x1,x2,…,xn)∈A,則

換元,令(x1,x1＋x2,…,x1＋x2＋…＋xn－1)＝(y1,y2,…,yn－1),則得到一個(gè)定序排列1≤y1＜y2＜…＜yn－1≤m－1,記所有這種定序排列的集合為B,則這種換元建立了一個(gè)雙射f:A→B,故方程的正整數(shù)解的個(gè)數(shù)為

記x1＋x2＋…＋xn＝m的所有非負(fù)整數(shù)解構(gòu)成一個(gè)集合A′,任取(x1,x2,…,xn)∈A′,則

等價(jià)轉(zhuǎn)化為

換元,令x1＋x2＋…＋xi＋i－1＝y(tǒng)i(1≤i≤n－1),得1≤y1＜y2＜…＜yn－1≤m＋n－1,所有這種定序排列構(gòu)成的集合記作B′,得到雙射f:A′→B′,故上述方程的非負(fù)整數(shù)解的個(gè)數(shù)為

(5)生成函數(shù):又稱母函數(shù),把計(jì)數(shù)方法與特定多項(xiàng)式中某種項(xiàng)形成對(duì)應(yīng),但通常是多對(duì)一,甚至是所有方法與同一種項(xiàng)對(duì)應(yīng),因此所求計(jì)數(shù)結(jié)果等于所構(gòu)造的多項(xiàng)式中對(duì)應(yīng)項(xiàng)的系數(shù).因此,母函數(shù)方法本質(zhì)上也是轉(zhuǎn)化化歸思想的一種具體表現(xiàn).讀者可結(jié)合下文例15理解.

2 典例精析

2.1 計(jì)數(shù)基本技能

計(jì)數(shù)對(duì)象之間關(guān)聯(lián)簡(jiǎn)單,計(jì)數(shù)邏輯清晰,分步與分類(lèi)簡(jiǎn)單易行,歷練這些方法是促進(jìn)思維進(jìn)階、發(fā)展計(jì)數(shù)高階思維必經(jīng)環(huán)節(jié).

1)窮舉法

窮舉法是一項(xiàng)基本技能,常用于元素不多的情境中.古典概型概率計(jì)算本質(zhì)上是兩個(gè)計(jì)數(shù)之比,但現(xiàn)行高中數(shù)學(xué)課標(biāo)卻要求先學(xué)習(xí)古典概型,后續(xù)再學(xué)習(xí)排列組合,就是強(qiáng)調(diào)教學(xué)必須重視引領(lǐng)學(xué)生歷練、掌握窮舉法.

例16位同學(xué)在畢業(yè)聚會(huì)活動(dòng)中進(jìn)行紀(jì)念品的交換,任意兩位同學(xué)之間最多交換一次,進(jìn)行交換的兩位同學(xué)互贈(zèng)一份紀(jì)念品.已知6位同學(xué)之間共進(jìn)行了13 次交換,則收到4 份紀(jì)念品的同學(xué)人數(shù)為( ).

A.1或3 B.1或4 C.2或3 D.2或4

由于|V|＝6,稱圖G(V,E)為6階簡(jiǎn)單圖,如果其中每?jī)蓚€(gè)頂點(diǎn)之間都連一條邊,則稱之為完全圖,記作K6,其邊數(shù)應(yīng)當(dāng)是,但這里|E|＝13,所以圖G(V,E)可以從完全圖K6中去掉兩條邊得到,而去掉兩條邊的方式有兩種,如圖1所示.

圖1

在圖1-甲中,從K6中刪除有公共頂點(diǎn)的兩條邊A1A3,A1A5,得到圖G(V,E),其度數(shù)(每個(gè)頂點(diǎn)引出的邊的條數(shù))序列為(d1,d2,d3,d4,d5,d6)＝(3,5,4,5,4,5);在圖1-乙中從K6中刪除無(wú)公共頂點(diǎn)的兩條邊A1A3,A2A4,得到圖G(V,E),其度數(shù)序列為(d1,d2,d3,d4,d5,d6)＝(4,4,4,4,5,5).

綜上,本題5階簡(jiǎn)單圖G(V,E)中度數(shù)是4的點(diǎn)數(shù)是2或4,故選D.

2)先組合后排列

例2安排3名志愿者完成4項(xiàng)工作,每人至少完成1項(xiàng),每項(xiàng)工作由1人完成,則不同的安排方式共有( ).

A.12種 B.18種 C.24種 D.36種

3)特殊元素優(yōu)先安排

例3用0,1,…,9十個(gè)數(shù)字,可以組成有重復(fù)數(shù)字的三位數(shù)的個(gè)數(shù)為( ).

A.243 B.252 C.261 D.279

4)相鄰元素捆綁處理

例4把5件不同產(chǎn)品擺成一排.若產(chǎn)品A與產(chǎn)品B相鄰,且產(chǎn)品A與產(chǎn)品C不相鄰,則不同的擺法有_________種.

第一步,捆綁A,B整合成一個(gè)“新產(chǎn)品”的方法數(shù)是;第二步,把C之外的2件產(chǎn)品與“新產(chǎn)品”排成一列的方法數(shù)是;第三步,再把產(chǎn)品C插入已排好的4件產(chǎn)品之間的方法數(shù)都是(無(wú)論A在何處)種方法.由分步乘法原理,滿足題意的5件產(chǎn)品擺放方法數(shù)是

5)隔離問(wèn)題插空處理

例5某次聯(lián)歡會(huì)要安排3個(gè)歌舞類(lèi)節(jié)目、2個(gè)小品類(lèi)節(jié)目和1個(gè)相聲類(lèi)節(jié)目的演出順序,則同類(lèi)節(jié)目不相鄰的排法種數(shù)是( ).

A.72 B.120 C.144 D.168

第一類(lèi),把2個(gè)小品類(lèi)節(jié)目與1個(gè)相聲類(lèi)節(jié)目排入3個(gè)舞蹈節(jié)目的兩個(gè)空隙與兩端之一,共有種方法.

第二類(lèi),把1個(gè)相聲節(jié)目與兩個(gè)小品類(lèi)節(jié)目之一重組在一起使之相鄰,重組的方法共有,再以兩個(gè)元素排入3個(gè)舞蹈節(jié)目之間的兩個(gè)空隙有種插入方法,這一類(lèi)不同方法數(shù)是.

6)分排問(wèn)題直排處理

例6如圖2所示,在一次射擊比賽中,有8個(gè)泥質(zhì)靶子掛成3列,一位神槍手按如下規(guī)則打掉所有靶子:首先選擇將要有一個(gè)靶子被打掉的一列;然后在被選列中打掉尚存的最下面一個(gè)靶子.求打掉這8個(gè)靶子共有多少種不同的順序.

圖2

7)正難則反,轉(zhuǎn)化情境

例7把5件不同產(chǎn)品擺成一排.若產(chǎn)品A與產(chǎn)品B相鄰,且產(chǎn)品A與產(chǎn)品C不相鄰,則不同的擺法有________種.

因?yàn)锳,B已經(jīng)相鄰,所以總控?cái)?shù)據(jù)匯總C與A相鄰的情形一定是B位于A,C之間的ABC或CAB兩種固定結(jié)構(gòu),以這兩種固定結(jié)構(gòu)之一與另外兩個(gè)自由產(chǎn)品任意排成一列的擺法是,所以總控?cái)?shù)據(jù)中A與C相鄰的擺法是.

綜上,分離出滿足題設(shè)條件的產(chǎn)品擺法是

2.2 分步與分類(lèi)

計(jì)數(shù)對(duì)象之間“膠著糾纏”“不獨(dú)立”,難以用一個(gè)組合數(shù)或排列數(shù)直接給出算法,分步與分類(lèi)就成為求解組合計(jì)數(shù)問(wèn)題的常態(tài)技能.

例8定義“規(guī)范01數(shù)列”{an}如下:{an}共有2m項(xiàng),其中m項(xiàng)為0,m項(xiàng)為1,且對(duì)任意k≤2m,a1,a2,…,ak中0的個(gè)數(shù)不少于1的個(gè)數(shù).若m＝4,則不同的“規(guī)范01數(shù)列”共有( ).

A.18個(gè) B.16個(gè) C.14個(gè) D.12個(gè)

第一類(lèi),前4項(xiàng)都是0,后4項(xiàng)都是1,這樣的“規(guī)范01數(shù)列”個(gè)數(shù)只有1個(gè).

第二類(lèi),前4項(xiàng)中a2,a3,a4恰有1個(gè)1,后4項(xiàng)中a5,a6,a7恰有1個(gè)0,這樣的“規(guī)范01數(shù)列”個(gè)數(shù)是

第三類(lèi),前4項(xiàng)中恰有2個(gè)1,這2 個(gè)1 只能是a2＝a4＝1或a3＝a4＝1,因此,前4項(xiàng)安排方法數(shù)是;后4項(xiàng)中恰有2個(gè)0,這2個(gè)0只能是a5＝a6＝0或a5＝a7＝0,后4項(xiàng)安排方法數(shù)是,因此,這樣的“規(guī)范01數(shù)列”個(gè)數(shù)是

綜上,由分類(lèi)加法原理,滿足題設(shè)條件的“規(guī)范01數(shù)列”個(gè)數(shù)是,故選C.

例9(北京大學(xué))將不大于12的正整數(shù)分為6個(gè)兩兩交集為空集的二元集合,并且每個(gè)集合中的兩個(gè)元素互質(zhì),則不同的分法有________種.

因?yàn)镃＝{2,4,6,8,10,12}中任意兩個(gè)元素都不互質(zhì),所以這6個(gè)數(shù)分別屬于6個(gè)不同的子集,記

其中i∈Ai(i∈C).其余元素1,7,11可以任意放入每一個(gè)子集中,但5?A10,3和9?A6∪A12.分類(lèi)計(jì)數(shù):

情形一,5∈A6∪A12,這時(shí)3 和9∈A2∪A4∪A8∪A10,1,7,11 任意放,所以這一類(lèi)的劃分個(gè)數(shù)為

情形二,5?A6∪A12,則5∈A2∪A4∪A8,3和9含于A2,A4,A8不含5的另外2個(gè)連同A10之中,1,7,11可以任意放,所以這一類(lèi)劃分的個(gè)數(shù)為

2.3 容斥計(jì)數(shù)

例10(上海交通大學(xué))在小于1000的正整數(shù)中,既不是5 的倍數(shù)也不是7 的倍數(shù)的整數(shù)個(gè)數(shù)是________.

2.4 映射轉(zhuǎn)移

計(jì)數(shù)對(duì)象之間“膠著”,關(guān)聯(lián)性強(qiáng),算法邏輯不清晰,計(jì)數(shù)情境轉(zhuǎn)換就成為探求復(fù)雜計(jì)數(shù)問(wèn)題的方法.

例11(清華大學(xué))已知集合A,B,C?{1,2,…,2020},且A?B?C,則有序集合組(A,B,C)的個(gè)數(shù)是________.

由分步乘法原理,這種映射的個(gè)數(shù)是42020,所以滿足題設(shè)條件的有序集組(A,B,C)的個(gè)數(shù)是42020.

2.5 遞推傳遞

例12(中國(guó)科學(xué)技術(shù)大學(xué))設(shè)k(k≥3)個(gè)人進(jìn)行互相傳球游戲,每個(gè)拿球的人等可能地把球傳給其他人中的任何一位.若初始時(shí),球在甲手中,則第n次傳球后,球又回到甲手中的概率為_(kāi)_______.

2.6 重建模型

重建模型是積極地改進(jìn)算法,追求更為快捷、清晰的算法的永恒追求,也是映射轉(zhuǎn)移計(jì)數(shù)的一種具體表現(xiàn).

例13(上海交通大學(xué))兩條異面直線稱為一個(gè)異面直線對(duì),連接正方體的8個(gè)頂點(diǎn)得到的所有直線中,異面直線對(duì)的個(gè)數(shù)是_________.

因?yàn)槿我凰拿骟wABCD的六條棱都可以構(gòu)成3個(gè)異面直線對(duì)“AB與CD、AC與BD、AD與BC”,而從正方體的8個(gè)頂點(diǎn)中任取4個(gè)頂點(diǎn)所得的個(gè)四點(diǎn)組中共有個(gè)不共面四點(diǎn)組,這些四點(diǎn)組都可以作為四面體的四個(gè)頂點(diǎn),也就是四面體的個(gè)數(shù),故所求異面直線對(duì)個(gè)數(shù)是

下面用古典概型計(jì)算幾何概型,這是基于對(duì)稱性處理重建模型、改善計(jì)數(shù)情境轉(zhuǎn)化的一種常用策略.

例14(中國(guó)科學(xué)技術(shù)大學(xué))在圓周上獨(dú)立隨機(jī)取n個(gè)點(diǎn),求此n個(gè)點(diǎn)可被半圓周覆蓋的概率P.

2.7 生成函數(shù)

例15(上海交通大學(xué))從2個(gè)紅色球、3個(gè)黑色球、5個(gè)白色球(同色球完全相同)中任意取出6個(gè),則不同取法種數(shù)是________.

因?yàn)檎归_(kāi)式通項(xiàng)為xixjxk,其中i∈{0,1,2},j∈{0,1,2,3},k∈{0,1,2,3,4,5},所以x6的系數(shù)就是方程i＋j＋k＝6滿足條件“i≤2,j≤3,k≤5”的非負(fù)整數(shù)解(i,j,k)的個(gè)數(shù).

按i∈{0,1,2}枚舉可得這種有序非負(fù)整數(shù)三元組(i,j,k)的個(gè)數(shù)是3＋4＋4＝11,故滿足題設(shè)條件取出6個(gè)球的方法數(shù)是11.

2.8 化歸轉(zhuǎn)化

例16(清華大學(xué))給定一個(gè)圓周上十個(gè)等分點(diǎn)Ai(1≤i≤10),則取其中的四個(gè),得到等腰梯形的四個(gè)頂點(diǎn)的取法數(shù)是( ).

A.60 B.45 C.40 D.50

上面定義的正整數(shù)有序三元組(x,y,z)由條件確定,枚舉可得所有(x,y,z)共有6個(gè):(1,1,7),(2,1,6),(3,1,5),(1,2,5),(2,2,4),(1,3,3),所以可以得到等腰梯形四個(gè)頂點(diǎn)的取法數(shù)是10×6＝60,故選A.

例17(復(fù)旦大學(xué))方程18x＋4y＋9z＝2021的正整數(shù)解(x,y,z)的個(gè)數(shù)是________.

模9,得4y≡5(mod9),即y≡－1(mod9),y＝9y′－1(y′∈N?),所以原方程化為18x＋4(9y′－1)＋9z＝2021 ?2x＋4y′＋z＝225,從而z是奇數(shù),記z＝2z′－1(z′∈N?),方程繼續(xù)轉(zhuǎn)化為x＋2y′＋z′＝113,從而x＋z′必為奇數(shù),即x,z′一奇一偶,由對(duì)稱性,這兩種情形的解數(shù)一樣多.

不妨設(shè)x是奇數(shù),記x＝2x′－1,z′＝2z″(x′,z″∈N?),繼續(xù)轉(zhuǎn)化上述方程,得x′＋y′＋z″＝57,該方程的正整數(shù)解(x′,y′,z″)的個(gè)數(shù)是,對(duì)應(yīng)地確定個(gè)原方程的正整數(shù)解(x,y,z)＝(2x′－1,9y′－1,4z″－1),故原方程的正整數(shù)解(x,y,z)個(gè)數(shù)是

2.9 換序計(jì)數(shù)

例18給定正整數(shù)n,集合S＝{1,2,…,10}的所有有序子集組(A1,A2,…,An)構(gòu)成一個(gè)集合T,則的值是_________.

另一方面,對(duì)任一a∈S,含這個(gè)a的所有有序子集組(A1,A2,…,An)的個(gè)數(shù)是

因此,所有n＋1元組(A1,A2,…,An,a)的個(gè)數(shù)為

由①②,得

3 實(shí)戰(zhàn)演練

1.從1,3,5,7,9中任取2個(gè)數(shù)字,從0,2,4,6中任取2個(gè)數(shù)字,一共可以組成_________個(gè)沒(méi)有重復(fù)數(shù)字的四位數(shù)(用數(shù)字作答).

2.把5個(gè)不同的小球裝入4個(gè)不同的盒子,要求每個(gè)盒子至少裝入1個(gè)球,則不同裝法有________種.

3.某臺(tái)小型晚會(huì)由6個(gè)節(jié)目組成,演出順序有如下要求:節(jié)目甲必須排在前兩位,節(jié)目乙不能排在第一位,節(jié)目丙必須排在最后一位,該臺(tái)晚會(huì)節(jié)目演出順序的編排方案共有( ).

A.36種 B.42種 C.48種 D.54種

4.(北京大學(xué))已知五項(xiàng)正整數(shù)數(shù)列{an}:a1,a2,a3,a4,a5,滿足|ak＋1－ak|≤1(k＝1,2,3,4),其中存在一項(xiàng)的值是3,則這種數(shù)列的個(gè)數(shù)為_(kāi)________.

5.(復(fù)旦大學(xué))某公司安排甲、乙、丙等7人完成7天的值班任務(wù),每人負(fù)責(zé)1天.已知甲不安排在第一天,乙不安排在第二天,甲和丙安排在相鄰兩天,則不同安排方式的種數(shù)是_________.

6.(上海交通大學(xué))2 條拋物線最多分平面為7份,3條最多分16份,則4條拋物線最多把平面分成_________份.

7.(復(fù)旦大學(xué))方程3x＋4y＋12z＝2020的非負(fù)整數(shù)解(x,y,z)的個(gè)數(shù)是________.

8.(北京大學(xué))如果一個(gè)十位數(shù)F的各位數(shù)字之和等于81,則稱F為一個(gè)“好數(shù)”,則所有好數(shù)的個(gè)數(shù)為_(kāi)_______.

9.(北京大學(xué))現(xiàn)有7把鑰匙,用這些鑰匙隨機(jī)開(kāi)鎖,則D1,D2,D3這三把鑰匙不能打開(kāi)對(duì)應(yīng)的鎖的概率是_________.

10.(北京大學(xué))從一個(gè)六元集合到一個(gè)三元集合的滿射個(gè)數(shù)是________.

答案1.1260. 2.240. 3.B. 4.211. 5.1128 .6.29. 7.14365. 8.48619. 9.

(完)