數(shù)學(xué)奧賽輔導(dǎo)_第八講_組合計數(shù)

1、數(shù)學(xué)奧賽輔導(dǎo) 第八講 組合計數(shù)知識、方法、技能組合計數(shù)就是計算集合的元素個數(shù)。它是組合數(shù)學(xué)的重要組成部分.在具體問題中給出的集合各式各樣，都具有實際意義，而且集體中的元素是由某些條件所確定的，要判定一個元素是否屬于某集合A，已非易事，要確定A的元素個數(shù)就更難了.這正是研究計算問題的原因。解決組合計算問題雖然不需要高深理論知識，卻需要重要的計算原理與思想方法.幾種特殊的排列、組合1圓排列定義1：從幾個元素中任取r個不同元素僅按元素之間的相對位置而不分首尾排成一個圓圈，這種排列稱為n個不同元素的r圓排列。r圓排列數(shù)記為.定理1：證：對n個不同元素取r個的任一圓排列，均有r種不同的方式展開成r個不同

2、的直線排列，且不同的圓排列展開的直線排列也彼此不同，故有r·=Prn，得正.2重復(fù)排列定義2：從n個不同元素中允許重復(fù)的任取r個元素排成一列，稱為n個不同元素的r可重復(fù)排列.定理2：n個不同元素的r可重排列數(shù)為nr.證：在按順序選取的r個元素中，每個元素都有n種不同的選法，故由乘法原理有，其排列數(shù)為nr.3不全相異元素的全排列定義3：設(shè)n個元素可分為k組，每一組中的元素是相同的，不同組間的元素是不同的，其中第i組的元素個數(shù)為ni(i=1, 2, , k ), n1+n2+nk=n . 則這n個元素的全排列稱為不全相異元素的全排列.定理3：n個元素的不全相異元素的全排列個數(shù)為證：先把每

3、組中的元素看做是不相同的，則n個不同元素的全排列數(shù)為n!，然后分別將每個組的元素還其本來面目看成是相同的，則在這n!個全排列中，每個排列都重復(fù)出現(xiàn)了n1！n2!nk！次，所以不全相異元素的全排列數(shù)4多組組合定義4：將n個不同的元素分成k組的組合稱為n個不同元素的k組合.定理4：對于一個n個不同元素的k組合，若第i組有ni個元素（i=1, 2, ，k），則不同的分組方法數(shù)為證：我們把分組的過程安排成相繼的k個步驟.第一步，從n個不同元素中選n1個，有種方法；第二步，從nn1個元素中選n2個有種方法；第k步，從n（n1+n2+nk1）個元素中選nk個元素，有（n1+n2+nk1）種方法，再由乘法原

4、理得證.5重重組合定義5：從n個不同元素中任取r個允許元素重復(fù)出現(xiàn)的組合稱為n個不同元素的r可重組合.定理5：n個不同元素的r可重組合的個數(shù)為Crn+r1 .證：設(shè)（a1 , a2 ,，ar）是取自1，2，n中的任一r可重復(fù)組合，并設(shè)a1a2ar .令 bi=ai+i1(1ir).從而b1=a1 , b2=a2+1 , b3=a3+2, br=a+r1r .顯然下面兩組數(shù)是一對一的：a1a2a3ar ,1a1<a2+1<a3+2<<ar+r1n+r1.設(shè) A=（a1 , a2 ,，ar）|ai1，2，n，a1a2ar ， B=（b1, b2,，br）|bi1，2，n+r

5、1，b1< b2<<br.則由A、B之間存在一一對應(yīng)，故|A|=|B|=Crn+r1 .枚舉法所謂枚舉法就是把集合A中的元素一一列舉出來，從而計算出集體A的元素個數(shù)。它是最基本，也是最簡單的計算數(shù)方法。應(yīng)用枚舉法計數(shù)的關(guān)鍵在于一一列舉集合中的元素時必須做到既不重又不漏。映射法（略，見第一講）分類計數(shù)原理與分步計數(shù)原理分類計算原理 完成一件事，有幾種方式，第一種方式有m種方法，第二種方式有n種方法，最后一種方式有r種方法.不管采取哪一種方法都能完成這件事，則完成這件事的方法總數(shù)為m+n+r .分步計數(shù)原理 完成一件事，有幾個步驟，第一步有m種方法，第二步有n種方法，最后一步有r

6、種方法，要完成這件事，必須通過每一步，則完成這件事的方法總數(shù)為m·nr.應(yīng)用分類計數(shù)原理的關(guān)鍵在于分劃，即把一個所要計數(shù)的集合S分劃成一些兩兩不交的小集合，且使每個小集合都便于計數(shù).應(yīng)用分步計數(shù)原理的關(guān)鍵在于分解，即把一個所要計數(shù)的集合S分解成若干個集合的乘積.對一個集合S 的分劃或分解，沒有一般方法，應(yīng)由具體問題而定，而這正是應(yīng)用兩個原理解題的難點與技巧所在.遞推方法將與正整數(shù)有關(guān)的數(shù)字問題，通過尋求遞推公式，或通過遞推公式，而使問題得到解決的方法，叫做遞推方法.遞推方法幾乎對所有數(shù)學(xué)分支都具有重要的作用，當(dāng)然對組合計數(shù)就更不例外了，它是組合計數(shù)的常用方法.應(yīng)用遞推方法解題，會遇到

7、如下兩類問題：一是如何找到滿足題設(shè)條件的遞推公式，二是推理計算.詳見例題.母函數(shù)法母函數(shù)是一種非常有用的方法.這種方法的最早系統(tǒng)敘述見于Laplace在1812年出版的名著概率解析理論中.這種方法思想簡單，把離散數(shù)列和冪級數(shù)一一對應(yīng)起來，把離散數(shù)列間的相互結(jié)合關(guān)系對應(yīng)成冪級數(shù)間的運算關(guān)系，最后由冪級數(shù)來確定離散數(shù)列的構(gòu)造。簡要地說，母函數(shù)方法是將一個有限或無限的數(shù)列ak=a0, a1, a2 , ak , 和如下形式的多項式f(x)= a0+a1x +a2 x2+ akxk + 聯(lián)系起來，構(gòu)成對應(yīng)關(guān)系 akf(x)這個f(x)就稱為ak的母函數(shù)或生產(chǎn)函數(shù).意思是這個數(shù)列ak是由多項f(x)產(chǎn)生

8、的.例如：組合數(shù)列的母函數(shù)是.因為由二項式定理可得 = 是最常見的母函數(shù).設(shè)an與bn是兩個結(jié)定的數(shù)列，為了確定它們之間的某種關(guān)系，可分別寫出二者所對應(yīng)的母函數(shù)，再研究這兩個母函數(shù)間的某種關(guān)系從而確定兩個數(shù)列之間的關(guān)系，這便是母函數(shù)方法解題的基本思想.子集類一個n元素合X有2n個子集A1，A2，如果以它的部分子集作為元素，又可得到一個集合F=A1，A2，Ak（1k2n），這個集合F的稱為原來集合X的一個子集類.應(yīng)用子集類知識可以幫助我們解決如下二類問題：a什么時候可以把一個整數(shù)（集合）寫成若干個滿足一定條件的整數(shù)（子集）之和（并）.b在可以寫的情況上有多少種寫法.前者是存在性問題，后者組合計數(shù)

9、問題.數(shù)學(xué)歸納法塞題精講例1 數(shù)1447，1005和1231有某些共同點，即每個數(shù)都是首位為1的四位數(shù)，且每個四位數(shù)中恰有兩個數(shù)字相同，這樣的四位數(shù)共有多少個？（第1屆AIME試題，1983年）【解】符合條件的四位數(shù)必含有一個1或者兩個1.（1）含有兩個1的情形從除1之外的其余9個數(shù)字中任取兩個，有C29種取法，再與其中的一個1組成任意排列的三位數(shù)，有P33種，這樣構(gòu)成的首位為1的四位數(shù)共有N1= C29 P33（個）.（2）只含有一個1的情形從其余的9個數(shù)字中任取兩個，有C29 種取法，其中一個數(shù)字被重復(fù)選出，有C12種，這樣的三個數(shù)字組成的三位數(shù)共有，這樣構(gòu)成的首位為1的四位數(shù)共有（個）.

10、因此，符合題意的四位數(shù)共有N=N1+N2=432（個）.例2 在xy平面上，頂點的坐標(biāo)（x ,y）滿足1x4，1y4，且x ,y是整數(shù)的三角形有多少個？（第44屆AHSME試題，1993年）【解】由題設(shè)知，在xy平面上有16個整點，共有C316=560個三點組，要從中減去那些三點共線的.平面上有4條垂直線和4條水平線，每條上有4個點，這8條線上含有8C43=32個三點共線的三點組（如圖I331）.類似的，在斜率為±1的線上三點共線的三點組有2C43+4C33=8+4=12（個）（如圖I332）.此外，沒有其他的三點共線的三點組，所以，組成的三角形的個數(shù)是5603212=516（個）.

11、例3 方程2x1+x2+x3+x10=3有多少個非負(fù)整數(shù)解.【解】設(shè)（x1, x2,x10）是原方程組的一個非負(fù)整數(shù)解，由于xi0（i=1, 2, 10），因此，2x12x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=3即2x13，所以x1=0，1.下面分兩種情形：（1）x1=0，則x2+x3+x10=3, 所以xi=0 , 1, 2 , 3 （i=2, 3 , ，10）.如果有某個xi=3，則其他xi=0，這樣解有C19=9（個）.如果某個xi3，若某個xi=2，則必有一個xj=1，ij，2i, j9，這樣解有C19·C18=72（個）.如果對每個xi2，3，則x2,

12、 x3，x10中必有三個xi（2i10）為1，這樣解有C93=84（個）.（2）x1=1，則x2+x3+x10=1, 因此x1，x2，x3x10中僅有一個是1，這樣解有C19=9（個）.于是原方程組有個非負(fù)整數(shù)解.例4 設(shè)S=1，2，n，A為至少含有兩項的、公并非為正的等差數(shù)列，其項部都在S中，且添加S 的其他元素等于A后均不能構(gòu)成與A有相同公差的等差數(shù)列，求這種A的個數(shù)（這里只有兩項的數(shù)列也看做等差數(shù)列）.（全國高中數(shù)學(xué)聯(lián)賽，1991年）【解】構(gòu)造具有如下要求的集合A：把A中的元素按從小到大的次序排好后，在其最大元素后面添上S的任何元素均不能構(gòu)成具有原公差的等差數(shù)列。這時，當(dāng)A的首項與公差一

13、旦確定，其整個集合A也即確定，不妨設(shè)A的首項為a，公差為d，則a=1, d=1, 2, , n1時的集A有n1個；a=2, d=1, 2, , n2時的集A有n2個；a= n1，d=1時的集A有1個.因此，所求A的總個數(shù)為1+2+（n1）=例5 在扔硬幣時，如果用Z表示正面朝上，F(xiàn)表示反面朝上，那么扔硬幣的序列就表示為用Z和F組成的串，我們可以統(tǒng)計在這種序列中正面緊跟著反面（ZF）的出現(xiàn)次數(shù)，正面緊跟著正面（ZZ）的出現(xiàn)次數(shù)，例如序列ZZFFZZZZFZZFFFF是15次扔幣的結(jié)果，其中有5個ZZ，3個ZF，2個FZ，4個FF.問：有多少個15次扔硬幣的序列，恰好有2個ZZ，3個ZF，4個FZ

14、，5個FF？（第4屆AIME試題，1986年）【解】符合題意的序列具有如下兩種可能形式：（1）F帶頭的：FFZZF；（2）Z帶頭的：ZZFFZZFF.由于題設(shè)要求的序列恰有3個ZF，則序列屬于第（ii）類的，應(yīng)具有如下形式ZZFFZZFFZZFF.其中只有2個FZ，達(dá)不到4個FZ，故不可能，所以符合題設(shè)的序列只能是第（i）種形式.由于序列恰有4個FZ，則在考慮序列中恰有兩個ZZ的情況下可分為如下兩類： ZZZ Z Z Z， ZZ ZZ Z Z.以及Z的不同位置，其中的空格之處應(yīng)填F.設(shè)每個空格處填F的個數(shù)依次為x1 , x2 , x3 , x4，則 x1 + x2 + x3 + x4=9這相當(dāng)

15、于求其正整數(shù)解的個數(shù)，顯然有C38=56.另一方面，對于，ZZZ的位置有4種，對，ZZ，ZZ，Z，Z的排列方法有6種，所以Z的排列方法有10種.所以，符合題意的序列有10×56=560（個）.例6 ABC的頂點為A=（0，0），B=（0，420），C=（560，0），一個骰子的六個面分別標(biāo)上兩個“A”，兩個“B”，兩個“C”.從ABC內(nèi)部選出一點P1=（k , m），重復(fù)扔骰子，依下列法則選出點P2，P3，：如骰子露出標(biāo)記L的那面LA，B，C，且剛剛選為Pn，那么Pn+1選為的中點，已知P7=（14，92），問k+m=?（第11屆AIME試題，1993年）【解】首先應(yīng)注意到因P1在A

16、BC內(nèi)，則以后的所有Pk在ABC內(nèi).下面，我們將證明一旦任何后繼的Pk給出，則可惟一地確定P1.假定PK=(xk , yk)，因Pk在ABC內(nèi)，則有0<xk<560 , 0<yk<420,0<420xk+560 yk<420·560.若擲出A，則于是Pk+1所在的可能范圍被限制在原三角形的之內(nèi)（圖I333中的一部分），顯然Pk+1在I內(nèi)，從而有420xk+1+560yk+1<×420×560.同樣擲出B，則Pk+1在II內(nèi)，yk+1>210.若擲出C，則Pk+1在內(nèi)，xk+1>280.所以，對k2，Pk必在I，

17、II，III之一內(nèi)，且由它的前一點惟一確定.例如，若Pk（xk , yk），位于II內(nèi)，則Pk必為BPk1的中點，這時Pk1=2PkB=(2 xk , 2yk420).所以，若k2，Pk=（xk , yk），有下面，我們可以由P7推出P1：P7=（14，92）P6=（28，184）P5=（56，368）P4=（112，316）P3=（224，212）P2=（448，4）P1=（336，8）.k+m=336+8=344.例7 已知定義在非負(fù)整數(shù)集上的函數(shù)f(n)由下列條件確定：f(0)=0, f(1)=0, f(2n)=2f(n)+1(n>0)及f(2n+1)=f(2n)1,求最小正整數(shù)m

18、，使f(m)=21990+1.【說明】本題的函數(shù)由遞推關(guān)系給出，由遞推關(guān)系求出函數(shù)表達(dá)式往往不是一件容易的事，通常情況下，求自變量為某一值時的函數(shù)值，只要按遞推關(guān)系式計算而不必求出函數(shù)關(guān)系，可現(xiàn)在的問題是已知函數(shù)值，要求自變量的最小正整數(shù)值，問題就顯得難了，復(fù)雜了，在此我們可直接借助于遞推關(guān)系而避開求函數(shù)表達(dá)式的麻煩.【解】因為 f(2n)=2f(n)+1, f(2n+1)=f(2n)1=(2f(n)+1)1=2f(n)所以偶數(shù)的函數(shù)值為奇數(shù)，奇數(shù)的函數(shù)值為偶數(shù).因為21990+1是奇數(shù)，而f(m)=21990+1，所以m為偶數(shù)，可設(shè)m=2n1，則 f(m)=f(2n1)=2f(n1)+1=2

19、1990+1，得f(n1)=21989,從而可知n1是奇數(shù)，可設(shè)n1=2n2+1,則f(n1)=2f(n2)=21989, f(n2)= 21989,從而可知n2是奇數(shù)，可設(shè)n2=2n3+1,，可得關(guān)系式 m=2n1, f(n1)= 21989, n1=2n2+1, f(n2)= 21989, nk=2nk+1, f(nk+1)= 219894, n1988=2n1998+1,f(n1989)=2. 因為f(0)=1, f(1)=0,f(2n)=2f(n)+1, f(2n+1)=f(2n)1, n>0.所以當(dāng)n=1時， f(2×1)=2f(1)+1=1, f(2×1+

20、1)=f(2×1)1=11=0. 當(dāng)n=2時， f(2×2)=2f(2)+1=2×1+1=3, f(2×2+1)=f(5)=f(4)1=31=2.因為滿足f(n1989)=2的最小正整數(shù)是 n1989=2×2+1=5 3·21，遞推而上可知 n1988=2 n1989+1=2×5+1=11 3·221， n1987=2 n1988+1=2×11+1=23 3·221即滿足f(n1988)=22的最小正整數(shù)是 n1988=3×221， 滿足f(nk+1)=21989k的最小正整數(shù)是 nk

21、=3·21989k1 滿足f(n1)=21989的最小正整數(shù)是 n1=3·219891.所以，滿足f(m)=21990+1的最小正整數(shù)是 m=2n1=3·219902.例8 從1，2，n中選出k項的嚴(yán)格遞增數(shù)列，每相鄰兩項的差m, m（k1）<n，有多少種不同的選法？【解】設(shè)第一個數(shù)為 x1+1，第二個數(shù)為 （x1+1）+（x2+1）， 第i個數(shù)為 （x1+1）+（xi+1）, 第k個數(shù)為 （x1+1）+（xk+1）其中 0xim1(2ik) 設(shè) x2+x3+xk=r 則 （x1+1）+（xk+1）n，得 0x1nkr,所以x1可取nkr+1個值.把（1+x

22、+xn1）k1展開，則xr的系數(shù)ar就是方程的，滿足條件的整數(shù)解(x2 , x3 ,，xk)的個數(shù)，即（1+x+xm1）k1= 所求的選法共有ar(nkr+1)種.因為ar (nkr+1)=(nk+1) ar rar 所以只要求出ar 與rar 即可.在中令x=1可得 ar=mk1 在中令x=1+y，則的右邊成為 ar（1+y）r =ar（1+ry+ay2+）， 由rar 就是上式中y的系數(shù). 別外，的左邊成為 比較、可得 由、可得本題答案 例9 設(shè)n>1，兩個自然數(shù)的集合 a1 , a2 , , anb1, b2 , , bn,而集ai+aj|1ijn=bi+bj|1ijn 這里的相等

23、計數(shù)及元素的重數(shù)，即如果元素S在的左邊出k次（用k種方法表示成ai+aj的形式），那么S也在的右邊出現(xiàn)k次，證明存在自然數(shù)h，使n=2h.【解】考慮母函數(shù)（注意，這里的ai與bi不是母函數(shù)的系數(shù)，而是指數(shù)） 同樣、中系數(shù)表示和出現(xiàn)的次數(shù)，由題設(shè)知即由于f(1)g(1)=nn=0,所以(x1)|(f(x) g(x),從而存在自然數(shù)h1,使 因此即令.由于n>1，所以h1>1,h11為某一自然數(shù)，從而有n=2h.例10 設(shè)A1，A2，A3是集合1，2，n的具有如下性質(zhì)的分劃：（1）若將每個子集的元素按遞增順序排列，則每兩個相鄰元素的奇偶性不同；（2）A1，A2和A3中恰有一個最小元素是

24、偶數(shù).試求這種分劃的個數(shù).提示 集合的分劃是由一族集合A1，A2，A3確定的，它們滿足：A1A2A3=1，2，n，A1A2= A2A3= A3A1=.集合的另一排列，如A2，A3，A1和A1，A2，A3是同一劃分.（第28屆IMO預(yù)選題，1987年）【解】顯然，題目中的條件（1）和（2）等價于對每個分劃集決定可能放入該集的下一個數(shù)的奇偶性，而且，如果是還沒有放進(jìn)元素的，則由（2）可知放進(jìn)它的第一個數(shù)必是與A中的最小數(shù)有不相同的奇偶性；而對非空子集，下一個數(shù)的奇偶性由（1）決定.不失一般性.假設(shè)1A1，而A2的最小元素小于A3的最小元素，于是2有兩種放法：或放入A1，或放入A2.更進(jìn)一步地，一旦

25、k1被放入A2后，則k就有兩種可能的放法：或放入A2，或放入A3.假設(shè)在某一步，k1可放入Ai1或A i2，不仿放入Ai3（i1, i2 , i3 是集合1，2，3的一種排列）.因為k1與k有不同的奇偶性，所以Ai3成為可放入的，而A i2卻不能放入，而且k放入Ai1也是可能的。如此繼續(xù)下一步及有兩種可能放法.以上給出了歸納推理的步驟.綜上，除1以處，每個數(shù)k均有兩種放法。所以分劃的個數(shù)為2n1.例11 試確定具有下述性質(zhì)的最小正整數(shù)A：把從1001至2000的所有正整數(shù)任作一個排列，都可以其中找出連續(xù)的10項，使這10項之和大于或等于A.（中國臺北第1屆數(shù)學(xué)奧林匹克試題）【解】設(shè)b1, b2

26、 , b1000是1001, 1002,  , 2000的任一個排列. 則 下面，把1001至2000這1000個自然數(shù)排成10行，每行100個數(shù)，奇數(shù)列從左到右，偶數(shù)行從右到左排可得下表：1001 1002 1003 1099 11001200 1199 1198 1102 11011201 1202 1203 1299 1300 1801 1802 1803 1899 19002000 1999 1998 1902 1901從左到右按列的順序，每一列又從上到下記上述數(shù)為a1, a2，a1000。令Si=ai +ai+1+ai+9,（i=1, 2, ，991），則S1=15005，

27、S2=15006,而且容易證明，當(dāng)i為奇數(shù)時, Si=15005，當(dāng)i為偶數(shù)時，Si=15006.所以可得A=15005.例12 （如圖I334）將邊長為正整數(shù)m、n的矩形劃分成若干個邊長均為正整數(shù)的正方形，每個正方形的邊長平行于矩形的相應(yīng)邊.試求這些正方形邊長之和的最小值.（2001年全國高中聯(lián)賽二試試題3）【解法1】記所求最小值為f(m,n)可以證明f(m,n)=m+n(m,n).其中（m, n）表示m和n的最大公約數(shù).事實上，不妨設(shè)mn.（1）關(guān)于m歸納，可以證明存在一種合乎題意的分法，使所得正方形邊長之和恰為 m+n(m,n)當(dāng)m=1時命題顯然成立.假設(shè)當(dāng)mk時，結(jié)論成立（k1）.當(dāng)m

28、=k+1時，若n=k+1，則命題成立，若n<k+1，從矩形ABCD中切去正方形AA1D1D（如圖I335），由歸納假設(shè)矩形A1BCD1有一種方法使得所得正方形邊長之和恰為mn+n(mn,n)=m(m,n ).于是原正方形ABCD有一種分法使得所得正方形邊長之和為m+n(m , n ).（2）關(guān)于m歸納可以證明（*）成立.當(dāng)m=1時，由于n=1，顯然f(m,n)=1=m+n(m , n).假設(shè)當(dāng)mk時，對任意1nm有f(m,n)= m+n(m , n).若m=k+1，當(dāng)n=k+1時顯然f(m,n)=k+1= m+n(m , n).當(dāng)1nk時，設(shè)矩形ABCD按要求分成了P個正方形，其邊長分別

29、為a1, a2 , , ap .不妨設(shè)a1a2 ap .顯然a1=n , 或a1<n .若a1<n ，則在AD與BC之間的與CD平行的任一直線至少穿過二個分成的正方形（或其邊界），于是a1+a2+ap不小于AB與CD之和.所以a1+a2+ap2m>m+n(m , n).若a1=n ，則一個邊長分別為mn和n的矩形可按題目要求分成邊長分別為a2,ap的正方形，歸納假設(shè)a2+apmn+n(m n , n )= m(m , n)從而a1+a2+apm+n(m , n)，于是當(dāng)m=k+1時，f(m, n ) m+n(m , n).再由（1）可知f(m, n ) = m+n(m , n) .【解法2】所求正方形邊長之和的最小值為m+nd，的最大公約數(shù)，即d=（