組合數(shù)學第一章答案

1、.從中找兩個數(shù)，使其滿足（1） ；（2）解：（1）根據(jù) 可得 則有 共有90種。（2）根據(jù) 得 則：當時，有 ， ， 則有 6種 ， ， 則有7種 ， ， 則有8種 ， ， 則有 9種 ， ， 則有10種當時，有 ， ， 則有 11種 ， ， 則有 11種 . . . . . . . . . ， ， 則有11種當時，有 ， ， 則有 10種 ， ， 則有 9種 ， ， 則有 8種 ， ， 則有 7種 ， ， 則有 6種故：共 1.2 （1）先把女生進行排列，方案為5！，然后把女生看成1個人和7個男生進行排列，總方案數(shù)為5！×8?。?）女生不相鄰，則先把男生進行排列，方案為7！再把女生

2、插入男生之間的8個空位種的任意5個，總方案數(shù)為7！×（3）應該是A 女生x 女生y 女生z B,或是B女生x 女生y 女生z A的形式，從5個女生中選出3人進行排列，方案為，考慮A,B可以換位，方案為2×，然后把這個看成一個整體，和剩下的2個女生，5個男生，一共7個人進行排列，總方案數(shù)2××8！1.3 m個男生,n個女生,排成一行,其中m,n都是正整數(shù),若（a）男生不相鄰（mn+1）；（b）n個女生形成一個整體；（c）男生A和女生B排在一起；分別討論有多少種方案。 解：(a)n!p(n+1,m)(b)(m+1)!n!(c)2(m+n-1)!14 26個英

3、文字母進行排列，求X和Y之間有五個字母的排列數(shù)？解:排列數(shù)為C(24,5)*5！*2*20！1.5 求3000到8000之間的奇整數(shù)的數(shù)目，且沒有相同的數(shù)字。解：設四位數(shù)為n3n2n1n0.由已知可知，n3只能取，3，4，5，6，7，8，n0只能取1,3,5,7,9.分以下兩種情況討論：1.當n3取3，5，7的時候，由于是不能重復的，所以n0只能有4種選擇，而剩下的n2,n1分別有8，7種選擇。所以符合條件的數(shù)，根據(jù)乘法原理有：3*4*8*7=672.個 2.當n3取4，6，8時，由于是不能重復的,所以n0有5種選擇，而剩下的n2,n1分別有8，7種選擇，所以符合條件的數(shù)，根據(jù)乘法原理有： 3

4、*5*8*7=840個 所以綜上所述，符合條件的數(shù)，根據(jù)加法原理共有： 672+840=1512個1.6 1*1!+2*2!+3*3!+(n-1)*(n-1)! 根據(jù)公式得 1*1!+2*2!+3*3!+(n-1)*(n-1)!=n!-11.7 試證 （n+1）(n+2)(2n)被除盡。證明：所以（n+1）(n+2)(2n)能被除盡。1.8 求1040和2030的共因數(shù)的數(shù)目. 解: 10 40=2 40 * 5 40 20 30=260 * 5 30 1040和2030的公因子有40*30=1200 個1.9 試證n的平方的正除數(shù)的數(shù)目是奇數(shù)答案：因為n的平方一定是兩個數(shù)的乘積，一定是兩個不

5、同的數(shù)的乘積或唯一的一個相同的 數(shù)的乘積。例如，16可以是1*16，2*8或4*4，前面的都是成對出現(xiàn)的，只有4是一個 數(shù)，所以他們的和一定是奇數(shù)。1.10 證明任一正整數(shù)n可唯一地表示成如下形式： n=, , 證明：對n用數(shù)學歸納法 當n=0,1時，0=01! , 1=11!。命題成立。 假設對于小于n的非負整數(shù)，命題成立。 對于n，設，即由，對命題成立。設，其中， (原因是而不能等于)，那么，其中，命題成立。再證唯一性：設，不妨設，即，假設，則j=3。那么，因為與前j項相等，上式兩邊均減去前j項，即，即 將上式兩邊都除以，得 可以看出，上式的余數(shù)為=與假設矛盾。因此是唯一的1.11求證：n

6、C(n-1,r)=(r+1)C(n,r+1)證明：左邊=C(n,1)C(n-1,r)右邊=C(r+1,1)C(n,r+1)=C(n,1)C(n-1,r+1-1)=C(n,1)C(n-1,r)=左邊所以等式成立。112 試證: 證明: (1+x) =C(n,0)+C(n,1)x+C(n,2)x+C(n,n)x 兩邊求導,并令x=1代入n(1+1)=C(n,1)+C(n,2)x+C(n,3)x+ +C(n,n)xn2組合意義: 設有n個不同的小球,A,B兩個盒子,A盒中恰好放1個球,B盒中可放任意個球.有兩種方法放球:第一種: 先從n個球中取k個球(k1),在從k中挑一個放入A盒,方案數(shù)共為,其余

7、放入B盒.第二種: 先從n個球中任取一球放入A盒,剩下n-1個球每個球有兩種可能,要么放入B盒,要么不放,故方案數(shù)為n2, 顯然相等.1.13：有N個不同的整數(shù)，從中取出兩組來，要求第一組的最小數(shù)大于第二組的最大數(shù)。解：本題求取兩組數(shù)的取法。我們首先從N中去M個數(shù)（2<=M<=N）,因為M個數(shù)是不同的，所以存在一個遞增的序列A=a1,a2,a3,a4aM (a1<a2<a3<a4<aM)。 然后我們從序列中按順序取出a1，a1,a2，a1,a2,a3a1,a2,a3,a4aM作為第一組，剩下的作為第二組。就可以保證第一組的最小數(shù)大于第二組的最大數(shù)。從N中去M

8、，共有C（n，m）種，每一種M對應一個序列A，每一個序列A對應M-1種分組方法。所以對于每一個M共有，C（n，m）×（m-1）種分組方法。又因為2<=M<=N，所以總共的分組方法為：1.14 6個引擎分列兩排，要求引擎的點火順序兩排交錯開來，試求從一個特定引擎開始有多少方案？ 解： 設6個引擎分別為1、2、3、4、5、6 不失一般性，我們把1、2、3放在第一排，4、5、6放到第二排。 由題意知從一個特定引擎開始，不妨設從1開始，那么（1）1開啟之后，下一個開始點有4、5、6三種選擇（2）第二排的一個開啟之后，下一個開始點有2，3兩種選擇（3）然后第一排，第二排剩下倆，那么

9、有兩種選擇（4）然后第一排只剩一個，第二排只剩一個，所以就剩一種選擇 所以，由乘法法則方案數(shù)=3×2×2×1×1=121.15試求從1到1000000的整數(shù)中，0出現(xiàn)了多少次？解：先考慮1到99 9999.個位為零的整數(shù)出現(xiàn)99999×1次 為：10999990十位為零的整數(shù)出現(xiàn)9999×10次 為：101999909百位為零的整數(shù)出現(xiàn)999×100次 為：1000999099千位為零的整數(shù)出現(xiàn)99×1000次 為：10000990999萬位為零的整數(shù)出現(xiàn)9×10000次 為：100000909999而1

10、00 0000本身有6個零所以從1到1000000的整數(shù)中，0出現(xiàn)的次數(shù)為：99999×1+9999×10+999×100+99×1000+9×10000+6=4888951.16 n個完全一樣的球放在r個有標志的盒子里面 ，無一空盒，問有多少種方案？ 解：r個盒子無一空盒，說明先要從n個球中取出r個先放每個盒中一個； 余下n-r個無標志的球，放入r個有標志的盒子中，根據(jù)定理可以得出 結果是 。1.17 n和r都是正整數(shù)，而且rn，試證下列等式1) 2) 3) 4) 5) 1） 證明：左邊=n*(n-1)（n-r+1） 右邊= n*(n-1)（

11、n-r+1）所以 左邊=右邊同理：（2）（3）（4）得證。5）證明：利用（4）， =等式右邊118 8個盒子排成一列，5個有標志的球放到盒子中，每個盒子最多放一個球，要求空盒子不相鄰，問有多少種排列方案。 解： P( 5 , 5 )*C( 6 , 3)=2400（種）答：共有2400種方案。1.19n + m 位由m個0，n個1組成的符號串，其中nm+1，試問不存在兩個1相鄰的符號串的數(shù)目。解：該題可以看作是往m個0里插入n 個1，即從m+1個空中選取n個空放1，這樣就使得不存在兩個1相鄰，總的解決方案數(shù)為：1.20 甲單位有10個男同志，4個女同志，乙單位有15個男同志，10個女同志，由他們

12、產生一個7人的代表團，要求其中甲單位占4人，而且7人中男同志5位，試問有多少種方案？ 解： 根據(jù)題意，符合要求的組合法有3種：（1）甲單位4男0女，乙單位1男2女；（2）甲單位3男1女，乙單位2男1女；（3）甲單位2男2女，乙單位3男0女。則對應的組合數(shù)為：（1），（2）， （3）。因此，符合條件的方案數(shù)共有：141750+504000+122850=768600種。1.21 一個盒子里有7個無區(qū)別的白球，5個無區(qū)別的黑球。每次從中隨機取走一球，已知前面取走6個，其中3個是白的。試問第6個球是白球的概率？解：設6個球的編號分別為1、26。6個球中第6個球是白球的所有可能方案為：126、136、

13、146、156、236、246、256、346、356、456，既有10種可能。那么第6個球是白球的概率為10/C（6，3）=1/2。1.22 求圖1-22中從0到P的路徑數(shù)。（1）路徑必須經過A點（2）路徑必須過道路AB（3）路徑必須過A點和C點（4）道路AB封鎖（但A,B兩點開放）解題：（1） （2） （3） （4）1.23 令，試證：解題：（1）：因為x,y的最小值為1，所以 當z=2時：x=y=1, 當z=3時：x,y各有兩種選擇 當z=n+1時：x,y各有兩種選擇即： （2）：因為且。當x=y時，從取兩個數(shù)，大的給z，小的給x,y,有。當時，取三個數(shù)，大的給z，小的給x或y，有，即：

14、1.24 A=(a,b)|a,bZ,0a9,0b5(1) 求x-y平面上以A作頂點的長方行數(shù)目；(2) 求x-y平面上以A作頂點的正方形數(shù)目；如圖所示132450678912345解：思想是分別以縱坐標0、1、2、3、4為起點，橫坐標和縱坐標一起夠成的長方形即：4*C（9，1）+4*C（9，2）+4*C（9，3）+4*C（9，4）+4*C（9，5）+5*C（9，6）+5*C（9，7）+5*C（9，8）+5 + 3*C（9，1）+3*C（9，2）+3*C（9，3）+3*C（9，4）+4*C（9，5）+4*C（9，6）+4*C（9，7）+4*C（9，8）+4 + 2*C（9，1）+2*C（9，2）

15、+2*C（9，3）+3*C（9，4）+3*C（9，5）+3*C（9，6）+3*C（9，7）+3*C（9，8）+3+ C（9，1）+C（9，2）+C（9，3）+C（9，4）+C（9，5）+C（9，6）+C（9，7）+C（9，8）+1=13374即以A作頂點的長方形數(shù)目為13374個。同理以A作頂點的正方形數(shù)目為：C（9，1）+C（9，2）+C（9，3）+C（9，4）+C（9，5）+C（9，1）+C（9，2）+C（9，3）+C（9，4）+C（9，1）+C（9，2）+C（9，3）+C（9，1）+C（9，2）+C（9，1）=1071即以A作頂點的正方形數(shù)目為1071個。1.25 平面上有15個點，P1

16、，P2，P15，其中P1，P2，P3，P4，P5共線，此外不存在3點共線的。（a）求至少過15個點中兩點的直線的數(shù)目；（b）求由15個點中3點組成的三角形的數(shù)目。 解：（a）根據(jù)題意，符合條件的直線有三種可能：（1）P1，P2，P3，P4，P5構成的直線，有1條；（2）P6P15中的任選兩點構成的直線，有條；（3）由P1P5中的一個點及P6P15中的一個點構成的直線，有條。因此，符合要求的直線共有1+45+50=96條。（b）根據(jù)題意，符合條件的三角形有三種可能：（1）P1P5中任選兩個點及P6P15中任選一個點構成三角形：有個；（2）P1P5中任選一個點及P6P15中任選兩個點構成三角形：有

17、個；（3）P6P15中任選三個點構成三角形：有個。因此，共可組成三角形100+225+120=445個。1.26。 解：由題知，說明a*b能被5整除。則分為兩種情況： a ,b 同時為5的倍數(shù) 1000中5的倍數(shù)有200個 方案數(shù)為：200*199/2 a ,b 不同時為5的倍數(shù)，即a ,b中有一個不是5的倍數(shù) 方案數(shù)為：800*200總的總的方案數(shù)為：200*199/2+800*200127 6位男賓，5位女賓圍一圓桌而坐，（1） 女賓不相鄰有多少種方案。（2） 所有女賓在一起有多少種方案。（3） 一女賓A和兩位男賓相鄰又有多少種方案。解：（1）5！*P( 6 , 5 )=120*720 =

18、86400 答：女賓不相鄰有86400種方案。 （2）6！*5！=86400答：所有女賓在一起有86400種方案 （3）8！*2*C（6 ，2）=40320*2*3*5=1209600答：一女賓A和兩位男賓相鄰又有1209600種方案。1.28 k和n都是正整數(shù)，kn位來賓圍著k張圓桌而坐，試求方案數(shù)。解; 方案數(shù)為：C(nk,n)*(n-1)!* C(n(k-1),n)*(n-1)! * C(n(k-2),n)*(n-1)!* C(n,n)*(n-1)!整理得：(n-1)!k * C(nk,n)* C(n(k-1),n)*C(n,n)= (n-1)!k *(nk)!/ (n!) k=(nk)

19、!/ n k 1.29 從n個對象中取r個作圓周排列，求其方案數(shù)？ 解：！1.30試證下列等式 證明：（1） （2） （3）1.31 試證明任意r個相臨數(shù)的連乘： 被r！除盡 解： 顯而易見，是一個整數(shù)，由= 由于是整數(shù)，所以是整數(shù)，那么可以被r！除盡1.32： 在 a,b,c,d,e,f,x,x,x,y,y 的排列中，要求y必須夾在兩個X之間，問這樣的排列數(shù)等于多少？解：要求y必須在兩個x之間，所以符合要求的排列必須有結構“xyxyx”，把“xyxyx”看作一個元素，與a,b,c,d,e,f,排列排列數(shù)等于6！。133 已知r,n,k都是正整數(shù),rnk,將r個無區(qū)別的球放在n個有標志的盒子里

20、,每盒至少k個球,試問有多少種方案?解: 先保證每一個盒子至少k個球,因為球無區(qū)別,把n個不同盒子每一個盒子放k個球.共kn個.問題轉化為將(r-nk)個小球放入n個不同盒子,每個盒子可以放任意個球,可以有空盒,根據(jù)可從復組合定理可得共(n+r-nk-1,r-nk)=(n+r-nk-1,n-1)1.34在r，s，t，u，v，w，x，y，z，的排列中求y居于x和z中間的排列數(shù)。解：一共9個位置，y只能放到2到8中間，當x放到第一個位置，y放到第二個位置，其他全排列有7！種方法，第一個位置也可以放z，共有2*7！種方法。y放到第三個位置，y前x有兩種選擇，y后z有6種選擇，其他全排列，所以方法有2

21、*6*6！，總方法有2*2*6*6種方法，以此類推算到y(tǒng)在第5個位置因為后邊是對稱的。總數(shù)=2*（7！+2*6*6！+3*5*6！+4*4*6！）=72000135 凸十邊形的任意三條對角線不共點。試求這凸十邊形的對角線交于多少個點？解： 根據(jù)題意，每4個點可得到兩條對角線，1個對角線交點，從10個頂點任取4個的方案有C(10,4)種，即交于210個點。1.36 試證明一個整數(shù)是另一個整數(shù)的平方的必要條件是除盡它的數(shù)的數(shù)目是奇數(shù)。答案：由：n=，其中是質數(shù)，是正整數(shù)。則n的因子數(shù)有(a1+1)(a2+1)(a3+1)個。得 =，因為(2a1+1),(2a2+1),(2a3+1).都是奇數(shù)，所以

22、 的因子數(shù)為(2a1+1)(2a2+1)(2a3+1).個，也是奇數(shù)個。1.37 給出 的組合意義. y 解: A(-1,m) m B(m-n,m) . . . . . . C(-r-1,0) -r-1 -1 0 m-n 可看作是格路問題:左邊第i項為從點C到點(-1,i)直接經過(0,i)的路徑,再到點B的所有路徑。左邊所有項的和就是從C點到B點的所有路徑數(shù)即為右邊的意義.1.38 給出的組合意義。解：設，從A中取r+1個元素組合成C，考慮以下n-r+1種情況：（1），則A需從中取r個與配合，構成C，共中可能。（2），則需從中取r個，加上構成C，共種可能。（n-r）,則需從中取r個組合，再加

23、上構成C，共種可能。（n-r+1）,這時只有=1種可能。故1.39證明:證：組合意義,右邊：m個球,從中取n個,放入兩個盒子,n個球中每個球都有兩種放法,得到可能的方案數(shù)。左邊：第i項的意義是一個盒子中放i個,另一個盒子放n-i個,所有的方案數(shù)相加應該等于右邊。證畢。1.40 從n個人中選出r個圍成一個圓圈，問有多少種不同方案。解：首先從n個人中選出r個有C(n,r)種方案，r個人進行一個圓周排列，根據(jù)圓周排列公式，共有r!r種方案，既(r-1)!種方案，所以根據(jù)乘法法則，一共有C(n,r)*(r-1)!種方案。1.41 分別寫出按照字典序，由給定排列計算其對應序號的算法及由給定序號計算其對應

24、的算法。解：生成所有排列的數(shù)組A： S1. A0<-<-12N，LEN=1；S2. j<-0;j從0到n，若,則退出；S3. i = max j | ；S4. h = maxk | ；S5.將和 互換的；S6.ALEN<- ,LEN+；S7.將和互換，得；S8.ALEN<- , LEN+,轉到S2;給定排列計算其對應序號的算法S1. 輸入；S2.j<-0,j從0到LEN 若Aj= ，則輸出j，退出； 否則j+；由給定序號計算其對應的算法S1.輸入序號j；S2.輸出Aj，退出；1.42（a）按照習題1.41的要求，寫出鄰位對換法（排列的生成算法之二）的相應算法

25、。解：S1.若p1p2pn沒有數(shù)處于活動狀態(tài)則結束。S2.將處于活動狀態(tài)的各數(shù)中值最大者設為m，則m和它的箭頭所指一側相鄰的數(shù)互換位置，而且比m大的所有數(shù)的箭頭改變方向，即>改為<，<改為>。轉S1。（b）寫出按照鄰位對換法由給定排列生成其下一個排列的算法。解：S1.Ai<1；S2.i從2到n做始Ai<i，Di <i,Ei <-1終；S3.q<0i從1到n輸出Ai;S4.k<n;S5.若k>1則轉S6； S6.Dk <Dk+Ek,p<Dk;S7.若p=k則做Ek <-1,轉S10；S8.若p=0 則做始Ek &

26、lt;1,q<q+1轉S10終；S9.p<p+q，r<Ap,Ap <Ap+1,Ap+1 <i，轉S3;S10.k<k-1轉S5.1.43證明：考慮C(n,k)和C(n,k-1)進行比較。C(n,k)/C(n,k-1)=(n-k+1)/k。當k>n/2時,(n-k+1)/k<1,即C(n,k)<C(n,k-1)當k>n/2時,(n-k+1)/k>1,即C(n,k)>C(n,k-1)得到當k為最接近n/2的數(shù)時，C(n,k)取到最大值。1.44 （1）用組合方法證明和都是整數(shù)。（2）證明是整數(shù)。證明：（1）設有2n個不同的球放

27、入n個不同的盒子里，每個盒子兩個，這個方案數(shù)應該是整數(shù)。而把2個球放入同一個盒子里不計順序，應該把全排列數(shù)除掉這些重復計算的次數(shù)，n個盒子內部的排列共重復計算了次，得到的2n個不同球放入n個不同的盒子里，每盒兩個的方案數(shù)為，得證。同理，若有3n個不同的球，放入n個不同的盒子里，每個盒子3個球，重復的次數(shù)為，故方案數(shù)為，得證。（2）設有個不同的球，將他們放入n個相同的盒子，每盒n個球，這個方案數(shù)應該是整數(shù)。由（1）可知，將個不同的球放入n個不同盒子的方案數(shù)為，若為相同的n個盒子，則應把n個盒子的排列數(shù)去掉，即n！，故個不同的球放入n個相同的盒子，每盒n個球的方案數(shù)為，證畢。1.45 （1）在2n

28、個球中，有n個相同，求從這2n個球中選取n個的方案數(shù)。（2） 在3n+1個球中，有n個相同，求從這3n+1個球中選取n個的方案數(shù)。解：（1）相當于從n個不同的小球中分別取出m個小球（），再從n個不同小球中取出n-m個小球。則共有方案數(shù)：（2）相當于從2n+1個不同的小球中分別取出個小球（），再從n個不同小球中取出n-m個小球。則共有方案數(shù)：1.46（1）證明：利用歸納法，當n=1時，0出現(xiàn)偶數(shù)次的實例是1,2，其中0出現(xiàn)0次，而當n1時，1/2=2，是正確的。 假設當nk時是正確的，即0出現(xiàn) 1/2 次，計算0出現(xiàn)奇數(shù)次的方案，因為總方案數(shù)為，0出現(xiàn)奇數(shù)次的方案為1/21/2. 當nk1時，0

29、出現(xiàn)偶數(shù)次的方案數(shù)是前k為出現(xiàn)偶數(shù)次，第k1位是1或2，或是前k位出現(xiàn)奇數(shù)個0，最后一位是0.總方案數(shù)為2×（1）/21/21/2,正是所要證明的形式，所以0出現(xiàn)偶數(shù)次的字符串有1/2個。 （2）證明：等式左邊第一項表示n位中有0個0，用表示，那么這n位只能取1或2，有種可能，所以方案為×，最后一項為當n中有最大偶數(shù)個0出現(xiàn)時的方案數(shù)，所以左邊整體表示為n位字符串中0出現(xiàn)偶數(shù)次的方案數(shù)，右邊也是0出現(xiàn)偶數(shù)次的方案數(shù)，左邊右邊，即證。1.47 5臺教學機器m個學生使用，使用第1臺和第2臺的人數(shù)相等，有多少種分配方案？解：當使用第1臺機器的學生為n個時，使用第2臺機器的學生也為

30、n,從m個學生中選出2n個使用這兩臺機器，剩余的學生可以任意使用剩下的機器的組合數(shù)為C(m,2n)C(2n,n)3(m-2n)。所以總的方案數(shù)為.1.48 在由n個0及n個1構成的字符串中，任意前k個字符中，0的個數(shù)不少于1的個數(shù)的字符串有多少？解：轉化為格路問題,即從(0,0)到(n,n),只能從對角線上方走,可以碰到對角線,故方案數(shù)為C(2n,n)-C(2n,n-1).1.49 在1到n的自然數(shù)中選取不同且互不相鄰的k個數(shù)，有多少種方案？解：根據(jù)不相鄰組合的公式，共有C(n-k+1)種方案k。1.50 (a)在5個0，4個1組成的字符串中，出現(xiàn)01或10的總次數(shù)為4的，有多少個?(b)在m

31、個0，n個1組成的字符串中,出現(xiàn)01或10的總次數(shù)為k的，有多少個？解：(a)先將5個0排成一列：00000，1若插在兩個0中間，“010”，則出現(xiàn)2個“01”或“10”;若插在兩端，則出現(xiàn)1個“01”或“10”;要使出現(xiàn)“01”,“10”總次數(shù)為4，有兩種辦法：(1)把兩個1插入0得空當內，剩下的1插入1的前面。(2)把1個1插入0得空當內，再取兩個1分別插入兩端，剩下的1插入1的前面。故總方案數(shù)為C(4,2)·3+C(4,1)·3=30 (b)m個0產生m-1個空當，若k為奇數(shù),則必有且只有1個“1”插入頭或尾,總方案數(shù)為若k為偶數(shù),總方案數(shù)為第一問，出現(xiàn)4個01或10，說明5個0被分成了3段，四個1被分成了兩段，然后夾在一起形如001101100；或者5個0被分成了2段，四個1被分成了3段，然后夾在一起形如100100011。于是題目的考慮就變成了5個0如何拆分，4個1如何拆分。答案是：C(4,2)*C(3,1)+C(4,1)*C(3,2)1.51 從中選出3個數(shù)，使得沒有兩個數(shù)相鄰，問有多少中方案？解：=種1.52 從S=1,2,n中選k個數(shù),使之沒有兩數(shù)相鄰,求不同方案數(shù).解: 1.53 把n個無區(qū)別的球放進有標志1，2，3，n的盒子里，每個盒子里可以放多余一個球，求有