關(guān)于競賽數(shù)學(xué)中排列組合問題的解題策略

廣東省深圳市前海港灣學(xué)校(518000) 李可欣

從20 世紀(jì)60年代華羅庚先生倡導(dǎo)數(shù)學(xué)競賽至今,已經(jīng)過去了50 多年.近年來,為了發(fā)掘和培育人才,數(shù)學(xué)競賽活動在全世界蓬勃發(fā)展,并逐漸形成了一門特殊的數(shù)學(xué)學(xué)科——競賽數(shù)學(xué).競賽數(shù)學(xué)介乎于中小學(xué)與大學(xué)教學(xué)之間,不斷推陳出新,發(fā)掘新問題、新方法、新結(jié)果,將現(xiàn)代化的內(nèi)容與趣味性的問題有機結(jié)合,把普遍性的問題與獨創(chuàng)性的技巧有機結(jié)合,在展現(xiàn)數(shù)學(xué)魅力的同時,利用自己所處的位置,大量地、方便地吸收最前沿的成果,大力開發(fā)同學(xué)們的數(shù)學(xué)思維,培養(yǎng)同學(xué)們的數(shù)學(xué)興趣.而排列組合是高中數(shù)學(xué)人教版選修2-3 的內(nèi)容,隸屬組合數(shù)學(xué),是高中數(shù)學(xué)學(xué)習(xí)的一個重難點,作為引申,在各類高中數(shù)學(xué)競賽中也常見其身影.本文將歸納出解決競賽數(shù)學(xué)中的排列組合問題常用的兩種解法.

下面我們結(jié)合例題對排列組合解題常用的分類討論、構(gòu)造不定方程及利用遞推關(guān)系三種解題策略進(jìn)行展開.

1 分類討論

分類討論的關(guān)鍵在于如何分類及具體分幾類,根據(jù)不同的分類方法一道題目可以有許多不同的解法.

例1 在0 和10000 之間有多少個整數(shù)恰好有一位數(shù)字是5?

令S為0 和10000 之間恰好有一位數(shù)字是5 的整數(shù)的集合.

解法一我們對S做如下劃分:S1是S中的一位數(shù)的集合,S2是S中的兩位數(shù)的集合,S3是S中的三位數(shù)的集合,S4是S中的四位數(shù)的集合.S中沒有五位數(shù).顯然,我們有|S1|=1.S2的數(shù)很自然地分成兩種類型:

(1)個位數(shù)字是5,(2)十位數(shù)字是5.

個位數(shù)字是5 的數(shù)一共有8 個(十位數(shù)字既不能是0 也不能是5),十位數(shù)字是5 的數(shù)一共有9 個(個位數(shù)字不能是5).故|S2|= 8 + 9 = 17.用類似的推理我們得到|S3|= 8·9 + 8·9 + 9·9 = 225.以 及|S4|= 8·9·9 + 8·9·9 + 8·9·9 + 9·9·9 = 2673.因此,|S|=1+17+225+2673=2916.

解法二通過添加前導(dǎo)零(如6 看作0006,25 看作0025,352 看作0352),可以把S中的每一個數(shù)都當(dāng)作4 位數(shù).現(xiàn)在我們根據(jù)數(shù)字5 是位于第一位、第二位、第三位還是第四位而把S劃分成S′1,S′2,S′3,S′4,其中S′i表示數(shù)字5 處于第i位的集合(i= 1,2,3,4).這四個集合中的每一個都含有9·9·9 = 729 個整數(shù),從而S所含整數(shù)的數(shù)目等于4·729=2916.

例2(第一屆美國數(shù)學(xué)邀請賽第7 題)某個國王的二十五位騎士圍坐在他們的圓桌旁,他們中間的三位被選派去殺一條惡龍(設(shè)三次挑選都是等可能的),令P是被挑到的三位騎士中至少有兩位是鄰座的概率.若把P寫成一個既約分?jǐn)?shù),其分子與分母之和是多少?

解法一顯然,在25 位騎士中任選3 位的選法總共有=2300 種,又根據(jù)在三位騎士中至少有兩位是鄰座的條件,可分出兩種情況.

一、三位騎士依次相鄰,那么有25 種選法;二、兩位騎士是鄰座,但第三位騎士不選在已經(jīng)鄰座的兩位騎士的兩旁,也就是說,第三位騎士只能在剩下的21 位中任選一位,這樣有25×21 = 525 種選法.因此,滿足條件的基本事件數(shù)為25+525=550.所以P=分子分母之和為57.

解法二同解法一,在25 位騎士中任選3 位的選法總共有=2300.由于25 位騎士圍坐在圓桌旁,取相鄰兩位騎士的取法有25 種,那么取第三位的取法就有23 種.也就說,被挑到的三位騎士中有兩位是鄰座的取法有25·23 = 575種.然而,相鄰三位騎士的25 種取法被取了兩次,所以被挑到的三位騎士中至少有兩位是鄰座的取法有575?25=550種.因此P=分子分母之和為57.

解法三先從圍坐的25 人選一人,則有25 種可能性,并始終約定被選中的人的右邊(或左邊) 那個人也隨同而去.如此,已選得相鄰兩人,再在余下的人中選一個即可.為避免重復(fù),在與已選兩人不相鄰的21 人中選一人,有21 種選法,然后加上已選兩人之右鄰(或左鄰)的一人的一種,計得+1=22 種選法,故滿足條件的選法有25·22=550 種.于是P=分子分母之和為57.

例3(第一屆美國數(shù)學(xué)邀請賽第10 題)數(shù)1447,1005 和1231 有某些共同點,即每一個都是以1 開頭的四位數(shù),且每個數(shù)恰好有兩個數(shù)字相等.這樣的數(shù)共有多少個?

解法一首先,不難發(fā)現(xiàn)滿足條件的四位數(shù)有六種類型:11AB,1A1B,1AB1,1AAB,1ABB,1ABA.而對于每一類A都有9 種可能,B都有8 種可能,所以這樣的數(shù)共有6·9·8=432 個.

解法二考慮以1 開頭的四位數(shù)的后三位數(shù),分兩種情況.若后三位數(shù)中含有數(shù)字1,那么1 放置的位置有3 種可能,剩下兩位數(shù)中一位有9 種可能性,另一位只有8 種可能,根據(jù)乘法原理,這樣的數(shù)有3·8·9 = 216 個;若后三位數(shù)字中不含1,則其中相同的兩位數(shù)字的位置可能有3 種,而該數(shù)字有9 種可能,剩下一位數(shù)字僅有8 種可能,故共有216 種可能.因此這樣的數(shù)總共有216+216=432 個.

從以上三個例題,我們不難發(fā)現(xiàn),一道題目往往可以從許多不同的角度去分類討論,而難易度也不盡相同.因此我們不止要學(xué)會如何分類討論,還要選取精準(zhǔn)的角度,讓分類盡量簡潔.

2 構(gòu)造不定方程

首先我們了解什么是“隔板法”.

隔板法就是在n個元素中的(n ?1) 個空中放置m(0 ≤m≤n ?1) 個隔板,從而把n個元素分成m+1組的方法.需要注意的是:(1)n個元素互異;(2)隔開的每一組中至少有一個元素;(3)分開的組彼此相異.結(jié)合例4 進(jìn)行進(jìn)一步理解.

例4求方程x+y+z=10 的正整數(shù)解的個數(shù).

解析方程x+y+z=10 可以看成是用2 個隔板插入10 個并列的圓球中,從而把10 個圓球分為3 組,又因為條件要求解為正整數(shù),所以每兩個隔板之間必須有至少一個球,如○○丨○○○丨○○○○○.那么容易看出,每一種隔板的放置方法,對應(yīng)的就是方程的一組解.因此方程x+y+z=10 的正整數(shù)解有=36 個.

與例4 相似,我們可以利用隔板法得到

引理不定方程x1+x2+···+xm=n(m≤2,n≤2,m≤n)的正整數(shù)解有組.

推論不定方程x1+x2+···+xm=n(m≤2,n≤2,m≤n)的非負(fù)整數(shù)解有組.

接下來,跟住以上的引理和推論,我們可以構(gòu)造不定方程解決競賽中的一些排列組合題.

例5(1990年全國高中數(shù)學(xué)聯(lián)賽)8 個女孩和25 個男孩圍成一圈,任意兩個女孩之間至少站兩個男孩.問:共有多少種不同的排列方法(只要把圈旋轉(zhuǎn)一下就重合的排法認(rèn)為是相同的)?

解析先考慮8 個女孩圍成一圈,則有=7!種不同的排列,其中8 個女孩中的7 個空要排入25 個男孩,不妨設(shè)每一個空中的男孩數(shù)分別為x1,x2,··· ,x8,且x1+x2+···+x8= 25.由于條件要求任意兩個女孩之間至少站兩個男孩,故上述不定方程有限制條件x1≤2,x2≤2,··· ,xn≤2.將不定方程化為(x1?1)+(x2?1)+···+(x8?1) = 17,再令y1=x1?1,y2=x2?1,··· ,y2=x8?1,即得y1+y2+···+y8= 17,且yi≤1(其中1 ≤i≤8).于是上述問題就轉(zhuǎn)化為以上不定方程的正整數(shù)解的組數(shù).由引理知其正整數(shù)解個數(shù)為.

由因為25 個男孩有25!種排列,所以符合條件的排列方法有7!25!種.

例6(1989年全國高中數(shù)學(xué)聯(lián)賽)從數(shù)1,2,··· ,14 中按由小到大的順序取出a1,a2,a3,使得同時滿足a2?a1≤3與a3?a2≤3.則所有符合要求的不同取法有多少種?

解析首先由條件知a1≤1,a2?a1≤3,a3?a2≤3,a3≤ 14,令a1=x1,a2?a1=x2,a3?a2=x3,14?a3=x4,則x1+x2+x3+x4=14.于是問題轉(zhuǎn)化為求不定方程x1+x2+···+x8=14 在條件x1≤1,x2≤3,x3≤3,x4≤0 下的整數(shù)解的組數(shù).

將方程轉(zhuǎn)化為x1+(x2?2)+(x3?2)+(x4+1)=11.令y1=x1,y2=x2?2,y3=x3?2,y4=x4+1,即得y1+y2+y3+y4=11,且yi≤1(其中1 ≤i≤4).由引理知y1+y2+y3+y4= 11 的正整數(shù)解的組數(shù)是= 120 個,所以符合要求的不同取法有120 種.

通過以上的三個例子,可以發(fā)現(xiàn)根據(jù)題目的條件列出不定方程是解題的突破口,而在列出不定方程后,要不斷利用換元法,使方程轉(zhuǎn)化為滿足每一個未知數(shù)都≤1 或都≤0 的不定方程,再根據(jù)引理或推論得到其正整數(shù)解的個數(shù),從而得出答案.下面,我們來解析一道難度較大的排列組合題.

例7(2002年全國高中數(shù)學(xué)聯(lián)賽)在世界杯足球賽前,F國教練為了考察A1,A2,··· ,A7這七名隊員,準(zhǔn)備讓他們在三場訓(xùn)練比賽(每場90 分鐘)中均上場.假設(shè)在比賽的任何時刻,這些隊員中有且僅有一人在場上,且A1,A2,A3,A4每人上場的總時間(以分鐘為單位)均能被7 整除,A5,A6,A7每人上場的總時間(以分鐘為單位)均能被13 整除.若每場換人次數(shù)不限,則按每名隊員上場的總時間計算,共有多少種不同的情形?

解析設(shè)第i名隊員上場的時間為xi分鐘(1 =1,2,···7),問題即求不定方程x1+x2+···+x7= 270在條件7| xi(1 ≤i≤4)且13| xj(5 ≤j≤7)下的正整數(shù)解的組數(shù).

若(x1,x2,··· ,x7)是滿足不定方程x1+x2+···+x7=270 的一組正整數(shù)解,則應(yīng)有x1+x2+x3+x4= 7m及x5+x6+x7= 13n,其中m,n是正整數(shù).因此,m,n是不定方程7m+ 13n= 270 在條件m≤4 且n≤3 下的一組正整數(shù)解.而不定方程7m+ 13n= 270 可以轉(zhuǎn)化為7(m ?4)+13(n ?3) = 203,令m′=m ?4,n′=n ?3(m′≤0,n′≤0),則上述方程化為7m′+13n′= 203,也就是說,問題轉(zhuǎn)化為求不定方程7m′+13n′=203 的非負(fù)整數(shù)解.

易觀察到7·2+13·(?1) = 1,可推出7·406+13·(?203) = 203,即m0= 406,n0=?203 是7m′+13n′=203 的整數(shù)特解,從而求得其整數(shù)通解為m′= 406?13k,n′=?203+7k,其中k是整數(shù).

由于m′≤0,n′≤0,解得129 ≤k≤31.分別取k=29,30,31 得到不定方程7m′+13n′=203 滿足條件的三組非負(fù)整數(shù)解從而滿足不定方程7m+13n=270 在條件m≤4 且n≤3 下的三組正整數(shù)解是

①在m= 33,n= 3 時,顯然x5=x6=x7= 13 僅有一種可能; 又設(shè)xi= 7yi(i= 1,2,3,4),則由不定方程y1+y2+y3+y4= 33 有= 4960 組正整數(shù)解.即此時不定方程x1+x2+···+x7=270 有3 有=4960 組正整數(shù)解.

②在m= 20,n= 10 時,設(shè)xi= 7yi(i= 1,2,3,4),xj=13yj(i=5,6,7),則由不定方程y1+y2+y3+y4=20有組正整數(shù)解以及y5+y6+y7=10 有組正整數(shù)解.此時不定方程x1+x2+···+x7=270 有=34884組正整數(shù)解.

③在m= 7,n= 17 時,仍設(shè)xi= 7yi(i=1,2,3,4),xj= 13yj(j= 5,6,7),則由不定方程y1+y2+y3+y4=7 有組正整數(shù)解以及y5+y6+y7=17 有組正整數(shù)解.此時不定方程有=2400 組正整數(shù)解.

綜上,滿足條件的正整數(shù)解的組數(shù)有4960+34884+2400=42244 個,即滿足題意的不同情形有42244 種.

3 利用遞推關(guān)系

利用遞推關(guān)系,就是要找到問題一般的關(guān)系式,即遞推關(guān)系式來解決具體問題,而尋找遞推關(guān)系式,往往可以從簡單的問題入手.

首先我們介紹一個經(jīng)典的遞推數(shù)列,即斐波那契數(shù)列,以下為其提出的問題.

在一年的伊始,把新近出生的雌雄一對兔子放進(jìn)一個籠子里.從第二個月開始,每個月這個雌兔子生出雌雄一對兔子.而每對新出生的雌雄兔子也從第二個月開始每個月生出一對雌雄兔子.確定一年后籠子里有多少兔子?

不妨設(shè)fn為第n個月籠子里兔子的對數(shù).不難發(fā)現(xiàn),f1=1,f2=1,f3=2,f4=3,f5=5,f6=8,f7=13,f8=21,f9= 34,f10= 55,f11= 89,f12= 144,f13= 233,因此一年之后籠子里有233 只兔子,并且可以看出fn的遞推關(guān)系式fn=fn?1+fn?2(n≤2),加入初始條件f0= 0,f1= 1,則滿足這個遞推關(guān)系式及初始條件的數(shù)列叫做斐波那契數(shù)列.

利用遞推關(guān)系解排列組合問題,常與斐波那契數(shù)列有關(guān).

例810 個信封只放A/B,則有210= 1024 種可能,除去連續(xù)AAA或BBB的可能,還有幾種可能?

解法一除去連續(xù)AAA或BBB的可能,即任意三個信封中至多只有兩個相同的A或B相鄰,則只有六種可能AAB,ABA,ABB,BAB,BBA,BAA,用樹狀圖列出前三個信封為AAB與ABB的可能性.

首先,從圖1 容易看出,AABABA,AABAAB,AABBAB滿足條件的可能性相同,都有8種,而AABBAA,AABABB都有5 種可能性,也就是說,若前三個信封放置的是AAB,那么除去連續(xù)AAA或BBB的可能,有3·8+5·2=34 種可能性.而從圖2 可以看出,前三個信封為ABB時,有5+8+8=21 種可能性.繼續(xù)利用列舉法,不難發(fā)現(xiàn)前三封信封為AAB,ABA,BBA,BAB的可能性相同,即34·4 = 136 種;前三封信封為ABB,BAA的可能性相同,即21·2=42 種.因此除去連續(xù)AAA或BBB的可能,還有136+42=178 種可能.

圖1

圖2

解法二設(shè)fn為n個信封中只放A/B且除去連續(xù)AAA或BBB的可能性.可以列出如下樹狀圖(圖3).可以看出f1= 1,f2= 2,f3= 3,f4= 5,f5= 8··· ,并且滿足遞推關(guān)系式fn=fn?1+fn?2(n≤2),構(gòu)成了一個斐波那契數(shù)列.繼續(xù)算下去,f6=13,f7=21,f8=34,f9=55,f10=f9+f8= 34+55 = 89,也就是說以A開頭的10 個信封只放A/B且除去連續(xù)AAA或BBB的可能性有89 種.同理以B開頭的可能性也有89 種,因此一共有89+89=178 種可能.

圖3

以上兩種不同解法,顯然利用遞推關(guān)系的解法二要更為簡便.

例9(1991年江蘇省數(shù)學(xué)夏令營)在排成一列的n個方格,用紅、黃、藍(lán)三色染每個方格,每格染一種顏色,要求任何相鄰的格都不同色,且首尾兩格也不同色.問:有多少種染法?

解析設(shè)共有an種不同染法.易得a1=3,a2=6,a3=6,且當(dāng)n≤4 時,將n個方格依次編號后,格子1 顯然與格子n ?1 不相鄰.

(1)若格子n ?1 與格子1 染色不同,此時,格子n只能與格子1 和格子n ?1 都不同的顏色,也就只有一種顏色可以染,而前n ?1 格都滿足條件,則有an?1種不同染法.

(2)若格子n ?1 與格子1 染色相同,此時由于要求任何相鄰格不同色,格子n ?2 的顏色與格子n ?1 不同,即與格子1 顏色不同,那么前n ?2 格都滿足條件,即有an?2種不同染法.又因為格子n要求與格子1 不同顏色,有兩種可能,所以共有2an?2不同染法.

綜上,可得遞推失系式an=an?1+ 2an?2,并可得an=2n+2(?1)n(n≤2).

本文我們主要討論了競賽數(shù)學(xué)中關(guān)于排列組合問題的三種主要解題策略,分別是分類討論、構(gòu)造不定方程及利用遞推關(guān)系.數(shù)學(xué)競賽本就是富有開創(chuàng)性與啟發(fā)性的,與組合數(shù)學(xué)相結(jié)合更是讓人感到趣味十足,充滿活力.對于這個課題,本文探討的還僅僅是冰山一角,但筆者會不斷研究下去,也希望能為讀者帶來收獲.