[理學]組合數學第三版+盧開澄+習題答案

1、第一章：排列與組合第1章 排列與組合經過勘誤和調整，已經消除了全部的文字錯誤，不過仍有以下幾個題目暫時沒有找到解答：1.81.91.16 1.41（答案略）1.42（答案略）1.1 從1,2,50中找一雙數a,b，使其滿足：解 (a) 將上式分解，得到a = b5，a=6，7，50時，b0，1，2，,45。滿足a=b-5的點共50-5=45個點.a = b+5，a=1，2，45時，b6，7，,50。滿足a=b+5的點共45個點.所以，共計245=90個點.(b) 。1.2 5個女生，7個男生進行排列，(a) 若女生在一起有多少種不同的排列？(b) 女生兩兩不相鄰有多少種不同的排列？(c) 兩男

2、生A和B之間正好有3個女生的排列是多少？解 (a) 女生在一起當作一個人，先排列，然后將女生重新排列。（71）!5!=8!5!40320120=4838400(b) 先將男生排列有7!種方案，共有8個空隙，將5個女生插入，故需從8個空中選5個空隙，有種選擇。將女生插入，有5!種方案。故按乘法原理，有：7!5!=33868800(種)方案。(c) 先從5個女生中選3個女生放入A，B之間，有種方案，在讓3個女生排列，有3!種排列，將這5個人看作一個人，再與其余7個人一塊排列，有(7+1)! = 8!由于A，B可交換，如圖*A*B* 或 *B*A*故按乘法原理，有：23!8!=4838400（種）1

3、.3 m個男生，n個女生，排成一行，其中m，n都是正整數，若(a) 男生不相鄰(mn+1)；(b) n個女生形成一個整體；(c) 男生A和女生B排在一起；分別討論有多少種方案.解 (a) 先將n個女生排列，有n!種方法，共有n+1個空隙，選出m個空隙，共有種方法，再插入男生，有m!種方法，按乘法原理，有：n!m!n!m!=種方案。(b) n個女生形成一個整體，看作一個人，與m個男生做重排列，然后，n個女生內部再作排列，按乘法原理，有(m+1)!n!種方案。(c) 男生A和女生B排在一起，看作一人，和其余n-1+m-1=n+m-2個人一起，作排列，共有(n+m-2+1)=(n+m-1)!種方法，

4、A，B兩人內部交換，故有2(n+m-1)!種方案。1.4 26個英文字母進行排列，要求x和y之間有5個字母的排列數.解 選入26224個字母中選取5個字母，有種方法，5個字母內部排列，有5!種方案，再將X*Y這7個字母看作一個，與其余19個合起來作排列，共有(19+1)!=20!種方案，又因為X與Y可交換，故按乘法原理，有：25!20!=25!20!=4024! 40又因為：ln40+0.5(lg+lg48)+24(lg24lge)1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481)=25.39325777所以

5、，結果為2.4731916641.5 求3000到8000之間的奇整數的數目，而且沒有相同的數字.解 30008000中各位不同的奇數，分類討論：首位3，1874（末位不能取3）首位4，1875（末位全取）首位5，1874首位6，1875首位7，1874從而，由加法原理，得：87（45454）=56221232個。1.6 計算解 (參見p14) 1.7 試證被2n除盡.證 故能被整除。1.8 求1040和2030的公因數.解1.9 試證n2的正除數的數目是奇數.解1.10 證明任一正整數n可惟一地表示成如下形式：證.(1)可表示性：令M=(am-1,am-2,a2,a1):0aii，i=1,2

6、,m-1，顯然|M|=m!；N=0,1,2,m!-1，顯然|N|=m!，其中m是大于n的任意整數。定義函數f : MN f(am-1,am-2,a2,a1)=am-1(m-1)!+am-2(m-1)!+a22!+a11! (*)顯然，0= 0(m-1)!+0(m-1)!+02!+01! am-1(m-1)!+am-2(m-1)!+a22!+a11! (m-1)(m-1)!+(m-2)(m-1)!+22!+11!= m!-1 （見P14）即0 f(am-1,am-2,a2,a1)m!-1由于f是用普通乘法和普通加法所定義的，故從而f無歧義。從而有一確定的數K（0Km!-1），使K=f(am-1,

7、am-2,a2,a1)為證N中的任一數均可表示成上邊(*)的形式，只要證明f是滿射函數即可。但由于在兩相等且有限的集合上定義的函數，滿射性與單射性、雙射性是等價的，故只須證明f是單射函數即可。否則，設存在某數K0N,有(am-1,am-2,a2,a1)(bm-1,bm-2,b2,b1)均屬于M，使K0=f(am-1,am-2,a2,a1)且K0=f(bm-1,bm-2,b2,b1)由于不相等,故必有某個j(m-1)，使ajbj。不妨設這個j是第一個不使相等的，即ai=bi，ajbj且ajbj，從而由am-1(m-1)!+am-2(m-1)!+a22!+a11!= bm-1(m-1)!+bm-2

8、(m-1)!+b22!+b11!就可有(bj-aj)j!+(bj-1-aj-1)(j-1)!+(b2-a2)2!+(b2-a1)1!=0但是(bj-aj)j!+(bj-1-aj-1)(j-1)!+(b2-a2)2!+(b2-a1)1!(bj-aj)j!-|bj-1-aj-1|(j-1)!+|b2-a2|2!+|b2-a1|1!j!-(j-1)(j-1)!+22!+11!=j!-(j!-1)=1矛盾，這說明f是單射函數。由于|M|=|N|=m!有限，故f是雙射函數，當然是滿射函數，從而0到m!-1中的任何一個數都可以表示成上邊(*)的形式。故，由nN，都有(am-1,am-2,a2,a1)M，使

9、得n=am-1(m-1)!+am-2(m-1)!+a22!+a11!這就證明了任何n可表示成以上形式。(2)唯一性： 用證明單射的方法，就可以證明表示法的唯一性(表示方法見 P14)，留給讀者。1.11 證明，并給予組合解釋.證.(參見 P28 (1-8-4)組合意義：（等式右邊）由n個元素中取出r+1個元素組合（有C(n,r+1)種），再從每個組合中取出1個（有r+1種），全部結果為C(n,r+1)(r+1)。（等式左邊）由此所得的全部結果相當于從n個元素中直接取1個元素（有n種），但有重復，其重復數等于剩下的n-1個元素中取r個元素的組合C(n-1,r)，故nC(n-1,r)= (r+1)

10、C(n,r+1)。1.12 試證等式：證.證法一：根據二項式定理，(參見 P29 (1-8-5)(1+x)n=1+C(n,1)x+C(n,2)x2+ xn兩邊對求導，有n(1+x)n-1=C(n,1)+2C(n,2)x+ nxn-1令x=1，即得。證法二：組合意義：設有n個不同的小球，并有A、B兩個合子，A合中恰好放入一個球，B合中可放入任意多個球。有兩種放球方法：(1)（等式左邊）先從n個球中選取k個，再從這k個球中任選一個放入A合，剩下的k-1個球全部放入B合中，方案數共為；(2)（等式右邊）先從n個球中任選一個放入A合，剩下的n-1個球每個都有兩種可能，要么放入B合，要么不放，方案數共為

11、n2n-1；顯然，兩種放球方法等效，兩種放球方案數相等，即。1.13 有n個不同的整數，從中取出兩組來，要求第1組的最小數大于另一個組的最大數.解 設這n個不同的數為。若假定第一組取k1個數，第二組取k2個數，并且令m=k1+k2(m2)，則要求第一組數里的最小數大于第二組的最大數，我們只要先從上邊那n個數中任選m個數(有C(n,m)種選法)，再從這m個數中從大到小取k1個數作為第一組數(有k1=1,2,m-1共m-1種取法)，將其余k2個數作為第二組數，即可。故總方案數為（參見第3題等式）。1.14 6個引擎分列兩排，要求引擎的點火順序兩排交錯開來，試求從特定一引擎開始有多少種方案？解 第一

12、次點火僅有一種選擇，即點某個特定引擎的火；第二次點另一組某個引擎的火，有三種選擇；第三次有2種,。即方案數為132211=12。1.15 試求從1到1 000 000的整數中，0出現的次數.解 (參見P8)從1到1 000 000的整數中，0出現的次數相當于10-99，100-999，1000-9999, 10000-99999,100000-999999,以及1 000 000中的0的個數。10-99中的零的個數為： 100-999中的零的個數為： 1000-9999中的零的個數為： =27+486+2 187 =2 70010000-99999中的零的個數為： =36+972+8 748+

13、26 244 =36 000100000-99999中的零的個數為：=45+1 620+21 870+131 220+295 245=450 0001，000，000中的0的個數為： 6故1到1，000，000的整數中0的個數為：9+180+2 700+36 000+450 000+6=488 895。1.16 n個完全一樣的球放到r個有標志的盒（nr）中，無一空盒，試問有多少種方案？解1.17 n和r都是正整數，而且rn，試證下列等式：解 (a) 方法一方法二（組合意義）等式左邊：從n個元素種取r個元素做排列有種，就是等式左邊；等式右邊：先從n個元素中拿出一個元素排在首位，有n種方法，然后再

14、從剩下的n-1個元素中取r-1個元素做后面r-1位的排列，有種方法，按乘法原理，共有n種方法。(b) 方法一方法二（組合意義法）等式左邊：從n個元素中取r個元素做r位排列，有種方案。等式右邊：先從n個元素中取r-1個元素做r-1位排列，有種方法；再從剩下的n-r+1個元素中取1個元素，共有n-r+1種選法，按乘法原理，共有(c) 方法一方法二：（組合意義法）等式左邊：從n個元素中取r個元素做r位排列，其方案數為；等式右邊：從n個元素中先取出一個元素放在第一位，有n種方法，再從剩下的n-1個元素種取出r個元素放在第2位，第r位，第r+1位，有種方法，這樣就多了一位，故應除去第r+1位的選取方法，

15、共有n-r種選法，故總方案為。(d) 方法一方法二：（組合意義）等式左邊：從n+1個不同的元素中取r個元素進行r位排列。其方案為；等式右邊：(a) 不取某特定元素b，則r個元素需從剩下的n個元素中取，然后做r位排列，共有種方案。(b) 取定某特定元素b，則其余r-1個元素需從剩下的n個元素中取，先做r-1位排列，共有種方法，再將特定元素b插入這r-1個元素形成的r個空隙中，有r種方法，故按乘法原理，共有r種方案。(e) 方法一 （根據(d)可得）方法二：組合意義（同樣根據d）等式左邊：從n+1個不同元素取r個元素做r位排列，其方案數為：等式右邊：設是n-r+1個特定元素。(a) 不取特定元素，

16、剩下的r個元素做全排列，有=r!種方案。(b)(1)：取特定元素，但不取特定元素，于是先在剩下的r個元素中取r-1個元素做排列，有種方法，然后將插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有r種方案。(2)：取特定元素，但不取特定元素，于是先在剩下的r+1個元素中取r-1個元素做排列，有種方法，然后，將插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有r種方案。(n-r)：取特定元素，但不取特定元素，于是先在剩下的n-1個元素中取r-1個元素做排列，有種方法，然后，將插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有r種方案。(n-r+1）：取特定元素，先在剩

17、下的n個元素中取r-1個元素做排列，有種方法，然后，將插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有r種方案。最后，按加法原理，共有：1.18 8個盒子排成一列，5個有標志的球放到盒子中，每盒最多放一個球，要求空盒不相鄰，問有多少種排列方案？解 先將5個球進行全排列，有5!種方法，再將三個空格插入5個球的6個空隙中，有種方法，然后將這/元素的排列一對一的放入8個盒子中，即完成了每盒最多一球，空盒不相鄰的放球要求，總方案有：（種）1.19 n+m位由m個0，n個1組成符號串，其中nm+1，試問不存在兩個1相鄰的符號串的數目。解：先將m個0排成一排，再將n個1插入m個0的m+1個空隙

18、（因為nm+1,這可實現）,就得到了無相鄰的n+m位0-1符號串，其方案數為。1.20 甲單位有10個男同志，4個女同志，乙單位有15個男同志，10個女同志，由他們產生一個7人的代表團，要求其中甲單位占4人，而且7人中男同志5位.試問有多少種方案？解 甲單位選4人，則乙單位只能選3人；另外男同志要5人，而乙單位的3人全是男同志，還差2名男同志，故甲單位的男同志人數應至少是2，至多為4。1.21 一個盒子里有7個無區(qū)別的白球，5個無區(qū)別的黑球. 每次從中隨機取走一個球，已知前面取走6個，其中3個是白的. 試問取第6個球是白球的概率.解 已知前面取走6個球，有3個白球，則有3個黑球。故總的取球方案

19、是；第六個球是白球的方案是因此取出第6個球是白球的概率1.22 求下圖中從0到P的路徑數：(a) 路徑必須過A點；(b) 路徑必須過道路AB；(c) 路徑必須過A和C；(d) 道路AB封鎖（但A，B兩點開放）. 解 O(0,0), A(3,2), B(4,2), P(8,5), C(6,3)(a) 路分為兩段：先從O到A，再從A到P，則有：(b)路分為三段：先從O到A，再從A到B；再從A到B；然后從B到P；(c) 路分為三段：先從O到A；再從A到C；然后從C到P；(d) (采用排除法)從O到P的滿足不過AB的路 從O到P的路從O到P經過AB的路，因此：1.23 另s=1,2,3,n+1,n2，

20、試證：證而，故1.24 A=(a, b)|a, bZ, 0a9,0b5(a) 求x-y平面上以A作頂點的長方形的數目.(b) 求x-y平面上以A作頂點的正方形數目.解 (a) 先選定橫作標，再選定縱坐標，其方案數為：(b) 求xy平面上以A作頂點的正方形數目。按邊長分類：邊長為1的正方形：9545邊長為2的正方形：(9-1)(5-1)=32邊長為3的正方形：(9-2)(5-2)=21邊長為4的正方形：(9-3)(5-3)=12邊長為5的正方形：(9-4)(5-1)=5故總的以xy平面上A點作頂點的正方形的數目，按加法原理可得數目為115.1.25 平面上有15個點P1, P2, , P15，其

21、中P1, P2, P3, P4, P5共線，此外不存在3點共線的.(a) 求至少過15個點中兩點的直線的數目.(b) 求由15個點中3點組成的三角形的數目.解 (a) (采用排除法)至少過15個點中兩點的直線數目在15個點中任選2個點將有一條直線從中選2點構成直線所在的直線l(b) (采用排除法)由15個點中3點組成的三角形的數目任在15個點中取3點構成三角形的數目在5個點中取3點構成的“三角形”的數目1.26 S=1, 2, , 1000，a，bS，使ab0 mod 5，求數偶a, b的數目.解 因為 所以 ab5k （k是整數）1a1000, 1b10001ab100000015k1000

22、0001k200000所以滿足 且1a,b1000的a,b的數目為2000001.27 6位男賓，5位女賓圍一圓桌而坐(a) 女賓不相鄰有多少種方案？(b) 所有女賓在一起有多少種方案？(c) 一女賓A和兩位男賓相鄰又有多少種方案？解 (a) 先將6位男賓作圓排列有在將5位女賓插入6個空格，每格一人，共有654321720按乘法原理：有12072086400(b) 5位女賓在一起，可看作一人，與6位男賓一起，先做圓排列，有=6!=720然后5位女賓內部作線排列，有5!120。所以，總方案為：72012086400(c) 先將6個男賓做圓排列，共有=120種方法。再將女賓A隨便插入6個空格中的一

23、個，有6種方法。然后將剩下的4個女賓插入5個空格中，但每個空格不限人數，故相當于將4個有區(qū)別的球放入5個不同的盒子中的放球方案(可重組合)，共有=56781680。所以，按乘法原理，有120616801209600種方案。1.28 k和n都是正整數，kn位來賓圍著k張圓桌而坐，試求其方案數.解 先將kn個來賓分成k堆，每堆n個人，有再將每堆n個人做圓排列，有(n-1)!,共有種方法。故按乘法原理，有1.29 從n個對象中取r個作圓排列，求其方案數目. 已知1rn.解 每一個r個人圍成的圈（圓排列）即每一個r圈相當于r個r排列。故不同的方案數為若不計順逆方向，則為。1.30 試證下列等式證 (a

24、) 方法一方法二：組合意義法：一方面，從n個元素中取出r個元素，然后再做排列，故按乘法原理，其數目為另一方面：先從n個元素中取出1個元素，排在第一位，再從剩下的n-1個元素中取出r-1個元素，并將這r-1個元素排在第2r位，故按乘法原理，其方案數為這兩方面的組合意義相同，故有因此，有：(b) 方法一方法二：組合意義一方面：從n個元素中取出r個元素來，然后，在做排列，故按乘法原理，其方案數為另一方面：先從n個元素中先取出r-1個元素，將其排排列再第1r-1位，再從剩下的n-r+1個元素中取出1個元素排在第r位。故按乘法原理，其方案數為：；這兩方面的組合意義相同，故有所以，有：(c) 方法一方法二

25、：組合意義一方面，從n個元素中取出n-r個元素，然后再做排列，按乘法原理，其方案數為：另一方面，選從n個元素中取出1個元素排再第一位，再從剩下的n-1個元素中選取n-r+1個元素，排在第2n-r位。故按乘法原理，其方案數為這兩方面的組合意義相同，可得：故有：1.31 試證任意r個相鄰數的連乘：被r！除盡.證 由于是從n+r個元素中選取r個元素的組合數，故當然是整數，因此，(n+1)(n+2)(n+r)可以整除r!，其商為組合數。1.32 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必須夾在兩個x之間，問這樣的排列數等于多少？解 由于y必須乘在兩個x之間，故兩

26、個y只能夾在僅有的三個x之間，形成圖象xyxyx，形成6個空檔。其余的6個元素a,b,c,d,e,y,只能放在這6個空格處，這相當于將6個不同的小球放入6個不同的盒子中，允許空盒，且盒內還要排列的方案數。故：1.33 已知r, n, k都是正整數，rnk，將r個無區(qū)別的球放在n個有標志的盒子里，每盒至少k個球，試問有多少種方案？解 先將nk個球放入n個有標志的盒中，每盒k個球，其方案為1。再將剩下的r-nk個球放入這n個盒中，每盒球數不限，其方案數為故總的方案為1.34 在r, s, t, u, v, w, x, y, z的排列中求y居x和z中間的排列數.解 由于y必須居于x和z之間，故形成圖

27、象xyz，形成4個空格。其余r,s,t,u,v,w這6個元素，只能放在這4個空格處，這相當于將6個不同的小球放入4個不同的盒子中，允許空盒，且盒內還要進行排列的方案數。故有：方法2：將9個字母進行全排列，有9!中排列，而x,y,z這3個字母形成的3!個排列只看作一種排列xyz，故有：1.35 凸十邊形的任意三條對角線不共點. 試求這凸十邊形的對角線交于多少個點？解 從一個頂點可引出7條線和第一條（從右到左）交的有17，和第二條交的有26條第 14 頁 共 114 頁故和一個頂點引出的7條線相交的點為： 17+26+35+44+53+62+71=84故和從10點引出的對角線交的點有個8410=8

28、40，但每個點重復了四次（因為每個點在兩條線上，而每條線有兩個端點）。故凸10 邊形（這樣的）對角線交于個點。故也可為第二章 母函數與遞推關系1.36 試證一整數是另一整數的平方的必要條件是除盡它的數的數目是整數.證 “必要性”。若整數n是另一個整數的平方，則n一定可寫成如下形式： （參見P7例4）其中P1,P2,Pe是e個不同的素數。由于第9題可得，除盡n的正整數數目為 (2a1+1)(2a2+1)(2ae+1)為奇數。“充分性”。若除盡正整數n的正整數的數目為奇數。則n一定是某個正整數的平方，否則，n不是平方數，則n一定是可分解成如下形式：其中P1,P2,Pe是e個不同的素數，且b1,b2

29、,be中至少有一個奇數（否則n為平方數）。于是(2b1+1)(2b2+1)(2be+1)必為偶數，與充分性假設矛盾。1.37 給出的組合意義.證 組合意義一：從(n+r+1)個元素1,2,n+r+1中取出個元素i1i2irir+2ir+2 in+r+1-m 的個數是。其中第r+1個位置上的元素ir+1可取r+1,r+2,r+1+m。當ir+1取(r+1+k)時(k=0,1,2,m)，前邊r個數i1,i2,ir可在1,2,r+1+(k-1)這(r+k)個數里取，故有種取法；后邊(n+r+1-m)-(r+1)=n-m個數ir+2,in+r+1-m可在r+1+k+1, ,n+r+1這(n+r+1)-

30、(r+1+k)=n-k個數中取，故有。根據乘法原理，當ir+1=r+1+k時，這樣的組合數為。根據加法原理，對k=0,1,2,m作和，就有。注：參見 Combinatorial Problems and Exercise by L.Lovasz 0143.7 L896cP18-42 (i) P96 P172(i)The number of those(n+r+1-m)-tuples of1,2,n+r+1Whose element is r+k+1is . Summing for k=0,1,2,m,we get the result.第15題圖1D(0, k)C (-1, k)A (-r-1

31、, 0)O (0, 0)組合意義二：（格路方法）等式左端：從點A(-r-1,0)到點C(-1,k)(k=0,1,2,m)直接經過點D(0,k)再到點B(n-m,m)的路徑數(參見本題圖1)；等式右端：從點A(-r-1,0)到點B(n-m,m)的路徑數。1.38 給出的組合意義.證.組合意義一：等式右端是從n+r+1個元素中取出r+1個作不允許重復的組合，結果不外乎有以下幾種情況(參見P25等式3的組合意義)：第16題圖1(1) r+1個元素的組合中含有的，相當于從n個元素中取r個組合，其組合數為（即A）。(2)r+1個元素的組合中不含有，但又含有元素的。即一個(r-1)-組合。依來分，不外乎含

32、和不含；不含的又依分，不外乎含和不含。不含而含的組合，相當于從n-1個元素中取r個元素的組合，然后加上而成，其組合數為。(3)r+1個元素的組合中不含和，但含有元素的。即不含的依來分，不外乎含和不含。不含而含的組合，相當于從n-2個元素中取出r個元素的組合，然后再加上而成，其組合數為。取出的r+1個組合元素中不含，但含有元素的。即不含的，又依來分，不外乎含有和不含有。不含而含的組合，相當于從n-(n-r-1)=r+1個元素中取出r個元素的組合而加上而成，其組合數為。(4)由組成的(r+1)-組合的組合數為。而且組合意義二：等式右端：從n+1個不同元素a1,a2,an,an+1,中任選r+1個元

33、素的組合方案數；等式左端：從n+1個不同元素a1,a2,an,an+1,中選取r+1個元素，一定選元素ar+k+1(k=0,1,2,n-r)，但是不選元素ar+k+2,an,an+1的組合方案數。1.39 證明證.借助P28等式4，可知： (nr) (r=0,1,2,n)從而有 (用了P29等式5)組合意義一：等式右端可看作從m個元素中取出n個元素進行組合。然后對這取出的n個元素進行染色（紅，白）的所有方案，它為；等式左端可看作先從m個元素中取出k個元素（個數為），全部染以紅色。再從剩下的(m-k)個元素中取出(n-k)個元素（個數為），全部染以白色。根據乘法原理，從m個元素中取出n個元素，k

34、個染上紅色，(n-k)個染上白色的方案數為，k=0,1,2,n；而從m個元素中取出n個元素染以紅白兩色的方案可分解成有0個，1個，n個染以紅色的總和。故根據加法原理，17題成立。組合意義二：等式右端：將從m個不同的小球中任意選出的n個小球放入兩個不同的合子里，注意到每個小球都有兩種放法，就得到了可能的放球方案數；等式左端：先從m個球中任選k個球放入第一個合子里(k=0,1,2,n)，再從剩下的m-k個球中任選n-k個球放入第二個合子里，然后對k從0到n求和，就得到了所有可能的放球方案數。1.40 從n個人中選r個圍成一個圓圈，問有多少種不同的方案？解.每一個r個人圍成的圈（圓排列）即每一個r圈

35、相當于r個r排列。故不同的方案數為若不計順逆方向，則為。1.41 分別寫出按照字典序由給定排列計算其對應序號的算法及由給定序號計算其對應排列的算法.解.（略）1.42 (a) 按照1.41的要求，寫出鄰位對換法（排列的生成算法之二）的相應算法.(b) 寫出按照鄰位對換法由給定排列生成其下一個排列的算法.解.（略）1.43 對于給定的正整數n，證明，當時，C(n,k)的最大值.證 取C(n,k)與C(n,k-1)進行比較。C(n,k)/C(n,k-1)=(n-k+1)/k。當k1，即C(n,k)C(n,k-1)；當kn/2時，(n-k+1)/k1，即C(n,k)0；否則g(n,k)=0。因此，可

36、給定初始值：g(2k-1,k)=1，g(2k-2,k)=0。1.50 (a) 在由5個0，4個1組成的字符串中，出現01或10的總次數為4的字符串，有多少個？(b) 在m個0，n個1組成的字符串中，出現01或10的總次數為k的字符串，有多少個？解 (a)先將5個0排成一列：00000，一個1若插在兩個0中間，就形成一個“010”，則同時出現“01”和“10”，計數為2；若插在兩端，則僅出現一個01”或“10”，計數為1?，F在要出現01”或“10”的總次數為4，可有兩種辦法：(1)先把兩個1插入五個0所形成的四個空檔內，再將剩下的兩個1放在已插入的1的前面，比如：011100100。按乘法原理，有C(4,2)C(2+2-1,2)= C(4,2)C(3,