最新組合數(shù)學習題答案(1-4章全)

1、第1章 排列與組合1.1 從1,2,50中找一雙數(shù)a,b，使其滿足：解 (a) 將上式分解，得到a = b5，a=1，2，45時，b6，7，50。滿足a=b-5的點共50-5=45個點.a = b+5，a=5，6，50時，b0，1，2，45。滿足a=b+5的點共45個點.所以，共計245=90個點.(b) 。1.2 5個女生，7個男生進行排列，(a) 若女生在一起有多少種不同的排列？(b) 女生兩兩不相鄰有多少種不同的排列？(c) 兩男生a和b之間正好有3個女生的排列是多少？解 (a) 女生在一起當作一個人，先排列，然后將女生重新排列。（71）!5!=8!5!40320120=4838400(

2、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 m個男生，n個女生，排成一行，其中m，n都是正整數(shù)，若(a) 男生不相鄰(mn+1)；(b) n個女生形成一個整體；(c) 男生a和女生b排在一起；分別討

3、論有多少種方案.解 (a) 先將n個女生排列，有n!種方法，共有n+1個空隙，選出m個空隙，共有種方法，再插入男生，有m!種方法，按乘法原理，有：n!m!n!m!=種方案。(b) n個女生形成一個整體，看作一個人，與m個男生做重排列，然后，n個女生內(nèi)部再作排列，按乘法原理，有(m+1)!n!種方案。(c) 男生a和女生b排在一起，看作一人，和其余n-1+m-1=n+m-2個人一起，作排列，共有(n+m-2+1)=(n+m-1)!種方法，a，b兩人內(nèi)部交換，故有2(n+m-1)!種方案。1.4 26個英文字母進行排列，要求x和y之間有5個字母的排列數(shù).解 選入26224個字母中選取5個字母，有種

4、方法，5個字母內(nèi)部排列，有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所以，結(jié)果為2.4731916641.5 求3000到8000之間的奇整數(shù)的數(shù)目，而且沒有相同的數(shù)字.解 30008000中各位不同的奇數(shù)，分類討論：首位3，187

5、4（末位不能取3）首位4，1875（末位全取）首位5，1874首位6，1875首位7，1874從而，由加法原理，得：87（45454）=56221232個。1.6 計算解 (參見p14) 1.7 試證被2n除盡.證 故能被整除。1.8 求1040和2030的公因數(shù).解因為1040=240540，2030=(225)30=260530,所以它們的公因數(shù)為形如2m5n的數(shù)，其中0m40，0n30，故它們的公因數(shù)的數(shù)目為(40+1)(30+1)=1271。1.9 試證n2的正除數(shù)的數(shù)目是奇數(shù).證當n=1時，因數(shù)為10；當n=2時，因數(shù)為20，21，22；當n=3時，因數(shù)為30，31，32；設(shè)，(均為

6、質(zhì)數(shù))，則的正除數(shù)可表示為，其中均為整數(shù)，且，所以的正除數(shù)的個數(shù)為，結(jié)果是奇數(shù)的乘積為奇數(shù)。1.10 證明任一正整數(shù)n可惟一地表示成如下形式：證.(1)可表示性：令m=(am-1,am-2,a2,a1):0aii，i=1,2,m-1，顯然|m|=m!；n=0,1,2,m!-1，顯然|n|=m!，其中m是大于n的任意整數(shù)。定義函數(shù)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)!+

7、(m-2)(m-1)!+22!+11!= m!-1 （見p14）即0 f(am-1,am-2,a2,a1)m!-1由于f是用普通乘法和普通加法所定義的，故從而f無歧義。從而有一確定的數(shù)k（0km!-1），使k=f(am-1,am-2,a2,a1)為證n中的任一數(shù)均可表示成上邊(*)的形式，只要證明f是滿射函數(shù)即可。但由于在兩相等且有限的集合上定義的函數(shù)，滿射性與單射性、雙射性是等價的，故只須證明f是單射函數(shù)即可。否則，設(shè)存在某數(shù)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

8、,b1)由于不相等,故必有某個j(m-1)，使ajbj。不妨設(shè)這個j是第一個不使相等的，即ai=bi，ajbj且ajbj，從而由am-1(m-1)!+am-2(m-1)!+a22!+a11!= bm-1(m-1)!+bm-2(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

9、!-(j!-1)=1矛盾，這說明f是單射函數(shù)。由于|m|=|n|=m!有限，故f是雙射函數(shù)，當然是滿射函數(shù)，從而0到m!-1中的任何一個數(shù)都可以表示成上邊(*)的形式。故，由nn，都有(am-1,am-2,a2,a1)m，使得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種），全

10、部結(jié)果為c(n,r+1)(r+1)。（等式左邊）由此所得的全部結(jié)果相當于從n個元素中直接取1個元素（有n種），但有重復(fù)，其重復(fù)數(shù)等于剩下的n-1個元素中取r個元素的組合c(n-1,r)，故nc(n-1,r)= (r+1)c(n,r+1)。1.12 試證等式：證.證法一：根據(jù)二項式定理，(參見 p29 (1-8-5)(1+x)n=1+c(n,1)x+c(n,2)x2+ xn兩邊對求導(dǎo)，有n(1+x)n-1=c(n,1)+2c(n,2)x+ nxn-1令x=1，即得。證法二：組合意義：設(shè)有n個不同的小球，并有a、b兩個合子，a合中恰好放入一個球，b合中可放入任意多個球。有兩種放球方法：(1)（等式

11、左邊）先從n個球中選取k個，再從這k個球中任選一個放入a合，剩下的k-1個球全部放入b合中，方案數(shù)共為；(2)（等式右邊）先從n個球中任選一個放入a合，剩下的n-1個球每個都有兩種可能，要么放入b合，要么不放，方案數(shù)共為n2n-1；顯然，兩種放球方法等效，兩種放球方案數(shù)相等，即。1.13 有n個不同的整數(shù)，從中取出兩組來，要求第1組的最小數(shù)大于另一個組的最大數(shù).解 設(shè)這n個不同的數(shù)為。若假定第一組取k1個數(shù)，第二組取k2個數(shù)，并且令m=k1+k2(m2)，則要求第一組數(shù)里的最小數(shù)大于第二組的最大數(shù)，我們只要先從上邊那n個數(shù)中任選m個數(shù)(有c(n,m)種選法)，再從這m個數(shù)中從大到小取k1個數(shù)作

12、為第一組數(shù)(有k1=1,2,m-1共m-1種取法)，將其余k2個數(shù)作為第二組數(shù)，即可。故總方案數(shù)為（參見第3題等式）。1.14 6個引擎分列兩排，要求引擎的點火順序兩排交錯開來，試求從特定一引擎開始有多少種方案？解 第一次點火僅有一種選擇，即點某個特定引擎的火；第二次點另一組某個引擎的火，有三種選擇；第三次有2種,。即方案數(shù)為132211=12。1.15 試求從1到1 000 000的整數(shù)中，0出現(xiàn)的次數(shù).解 (參見p8)從1到1 000 000的整數(shù)中，0出現(xiàn)的次數(shù)相當于10-99，100-999，1000-9999, 10000-99999,100000-999999,以及1 000 00

13、0中的0的個數(shù)。10-99中的零的個數(shù)為： 100-999中的零的個數(shù)為： 1000-9999中的零的個數(shù)為： =27+486+2 187 =2 70010000-99999中的零的個數(shù)為： =36+972+8 748+26 244 =36 000100000-99999中的零的個數(shù)為：=45+1 620+21 870+131 220+295 245=450 0001，000，000中的0的個數(shù)為： 6故1到1，000，000的整數(shù)中0的個數(shù)為：9+180+2 700+36 000+450 000+6=488 895。1.16 n個完全一樣的球放到r個有標志的盒（nr）中，無一空盒，試問有多少

14、種方案？解1.17 n和r都是正整數(shù)，而且rn，試證下列等式：解 (a) 方法一方法二（組合意義）等式左邊：從n個元素種取r個元素做排列有種，就是等式左邊；等式右邊：先從n個元素中拿出一個元素排在首位，有n種方法，然后再從剩下的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個元素

15、中取r個元素做r位排列，其方案數(shù)為；等式右邊：從n個元素中先取出一個元素放在第一位，有n種方法，再從剩下的n-1個元素種取出r個元素放在第2位，第r位，第r+1位，有種方法，這樣就多了一位，故應(yīng)除去第r+1位的選取方法，共有n-r種選法，故總方案為。(d) 方法一方法二：（組合意義）等式左邊：從n+1個不同的元素中取r個元素進行r位排列。其方案為；等式右邊：(a) 不取某特定元素b，則r個元素需從剩下的n個元素中取，然后做r位排列，共有種方案。(b) 取定某特定元素b，則其余r-1個元素需從剩下的n個元素中取，先做r-1位排列，共有種方法，再將特定元素b插入這r-1個元素形成的r個空隙中，有r

16、種方法，故按乘法原理，共有r種方案。(e) 方法一 （根據(jù)(d)可得）方法二：組合意義（同樣根據(jù)d）等式左邊：從n+1個不同元素取r個元素做r位排列，其方案數(shù)為：等式右邊：設(shè)是n-r+1個特定元素。(a) 不取特定元素，剩下的r個元素做全排列，有=r!種方案。(b)(1)：取特定元素，但不取特定元素，于是先在剩下的r個元素中取r-1個元素做排列，有種方法，然后將插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有r種方案。(2)：取特定元素，但不取特定元素，于是先在剩下的r+1個元素中取r-1個元素做排列，有種方法，然后，將插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有r

17、種方案。(n-r)：取特定元素，但不取特定元素，于是先在剩下的n-1個元素中取r-1個元素做排列，有種方法，然后，將插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有r種方案。(n-r+1）：取特定元素，先在剩下的n個元素中取r-1個元素做排列，有種方法，然后，將插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有r種方案。最后，按加法原理，共有：1.18 8個盒子排成一列，5個有標志的球放到盒子中，每盒最多放一個球，要求空盒不相鄰，問有多少種排列方案？解 先將5個球進行全排列，有5!種方法，再將三個空格插入5個球的6個空隙中，有種方法，然后將這些元素的排列一對一的放入8個盒

18、子中，即完成了每盒最多一球，空盒不相鄰的放球要求，總方案有：（種）1.19 n+m位由m個0，n個1組成符號串，其中nm+1，試問不存在兩個1相鄰的符號串的數(shù)目。解：先將m個0排成一排，再將n個1插入m個0的m+1個空隙（因為nm+1,這可實現(xiàn)）,就得到了無相鄰的n+m位0-1符號串，其方案數(shù)為。1.20 甲單位有10個男同志，4個女同志，乙單位有15個男同志，10個女同志，由他們產(chǎn)生一個7人的代表團，要求其中甲單位占4人，而且7人中男同志5位.試問有多少種方案？解 甲單位選4人，則乙單位只能選3人；另外男同志要5人，而乙單位的3人全是男同志，還差2名男同志，故甲單位的男同志人數(shù)應(yīng)至少是2，至

19、多為4。1.21 一個盒子里有7個無區(qū)別的白球，5個無區(qū)別的黑球. 每次從中隨機取走一個球，已知前面取走6個，其中3個是白的. 試問取第6個球是白球的概率.解 已知前面取走6個球，有3個白球，則有3個黑球。故總的取球方案是；第六個球是白球的方案是因此取出第6個球是白球的概率1.22 求下圖中從0到p的路徑數(shù)：(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到

20、b；再從a到b；然后從b到p；(c) 路分為三段：先從o到a；再從a到c；然后從c到p；(d) (采用排除法)從o到p的滿足不過ab的路 從o到p的路從o到p經(jīng)過ab的路，因此：1.23 另s=1,2,3,n+1,n2，試證：證而，故1.24 a=(a, b)|a, bz, 0a9,0b5(a) 求x-y平面上以a作頂點的長方形的數(shù)目.(b) 求x-y平面上以a作頂點的正方形數(shù)目.解 (a) 先選定橫作標，再選定縱坐標，其方案數(shù)為：(b) 求xy平面上以a作頂點的正方形數(shù)目。按邊長分類：邊長為1的正方形：9545邊長為2的正方形：(9-1)(5-1)=32邊長為3的正方形：(9-2)(5-2)

21、=21邊長為4的正方形：(9-3)(5-3)=12邊長為5的正方形：(9-4)(5-1)=5故總的以xy平面上a點作頂點的正方形的數(shù)目，按加法原理可得數(shù)目為115.1.25 平面上有15個點p1, p2, , p15，其中p1, p2, p3, p4, p5共線，此外不存在3點共線的.(a) 求至少過15個點中兩點的直線的數(shù)目.(b) 求由15個點中3點組成的三角形的數(shù)目.解 (a) (采用排除法)至少過15個點中兩點的直線數(shù)目在15個點中任選2個點將有一條直線從中選2點構(gòu)成直線所在的直線l(b) (采用排除法)由15個點中3點組成的三角形的數(shù)目任在15個點中取3點構(gòu)成三角形的數(shù)目在5個點中取

22、3點構(gòu)成的“三角形”的數(shù)目1.26 s=1, 2, , 1000，a，bs，使ab0 mod 5，求數(shù)偶a, b的數(shù)目.解 因為 所以 ab5k （k是整數(shù)）1a1000, 1b10001ab100000015k10000001k200000所以滿足 且1a,b1000的a,b的數(shù)目為2000001.27 6位男賓，5位女賓圍一圓桌而坐(a) 女賓不相鄰有多少種方案？(b) 所有女賓在一起有多少種方案？(c) 一女賓a和兩位男賓相鄰又有多少種方案？解 (a) 先將6位男賓作圓排列有再將5位女賓插入6個空格，每格一人，共有654321720按乘法原理：有12072086400(b) 5位女賓在一

23、起，可看作一人，與6位男賓一起，先做圓排列，有=6!=720然后5位女賓內(nèi)部作線排列，有5!120。所以，總方案為：72012086400(c)先將6個男賓做圓排列，共有=120種方法。再將女賓a隨便插入6個空格中的一個，有6種方法。然后將剩下的4個女賓插入5個空格中，但每個空格不限人數(shù)，故相當于將4個有區(qū)別的球放入5個不同的盒子中的放球方案(可重組合)，共有=56781680。所以，按乘法原理，有120616801209600種方案。1.28 k和n都是正整數(shù)，kn位來賓圍著k張圓桌而坐，試求其方案數(shù).解 先將kn個來賓分成k堆，每堆n個人，有再將每堆n個人做圓排列，有(n-1)!,共有種方

24、法。故按乘法原理，有1.29 從n個對象中取r個作圓排列，求其方案數(shù)目. 已知1rn.解 每一個r個人圍成的圈（圓排列）即每一個r圈相當于r個r排列。故不同的方案數(shù)為若不計順逆方向，則為。1.30 試證下列等式證 (a) 方法一方法二：組合意義法：一方面，從n個元素中取出r個元素，然后再做排列，故按乘法原理，其數(shù)目為另一方面：先從n個元素中取出1個元素，排在第一位，再從剩下的n-1個元素中取出r-1個元素，并將這r-1個元素排在第2r位，故按乘法原理，其方案數(shù)為這兩方面的組合意義相同，故有因此，有：(b) 方法一方法二：組合意義一方面：從n個元素中取出r個元素來，然后，在做排列，故按乘法原理，

25、其方案數(shù)為另一方面：先從n個元素中先取出r-1個元素，將其排排列再第1r-1位，再從剩下的n-r+1個元素中取出1個元素排在第r位。故按乘法原理，其方案數(shù)為：；這兩方面的組合意義相同，故有所以，有：(c) 方法一方法二：組合意義一方面，從n個元素中取出n-r個元素，然后再做排列，按乘法原理，其方案數(shù)為：另一方面，選從n個元素中取出1個元素排再第一位，再從剩下的n-1個元素中選取n-r+1個元素，排在第2n-r位。故按乘法原理，其方案數(shù)為這兩方面的組合意義相同，可得：故有：1.31 試證任意r個相鄰數(shù)的連乘：被r！除盡.證 由于是從n+r個元素中選取r個元素的組合數(shù)，故當然是整數(shù)，因此，(n+1

26、)(n+2)(n+r)可以整除r!，其商為組合數(shù)。1.32 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必須夾在兩個x之間，問這樣的排列數(shù)等于多少？解 由于y必須乘在兩個x之間，故兩個y只能夾在僅有的三個x之間，形成圖象xyxyx，形成6個空檔。其余的6個元素a,b,c,d,e,y,只能放在這6個空格處，這相當于將6個不同的小球放入6個不同的盒子中，允許空盒，且盒內(nèi)還要排列的方案數(shù)。故：1.33 已知r, n, k都是正整數(shù)，rnk，將r個無區(qū)別的球放在n個有標志的盒子里，每盒至少k個球，試問有多少種方案？解 先將nk個球放入n個有標志的盒中，每盒k個球，其

27、方案為1。再將剩下的r-nk個球放入這n個盒中，每盒球數(shù)不限，其方案數(shù)為故總的方案為1.34 在r, s, t, u, v, w, x, y, z的排列中求y居x和z中間的排列數(shù).解 由于y必須居于x和z之間，故形成圖象xyz，形成4個空格。其余r,s,t,u,v,w這6個元素，只能放在這4個空格處，這相當于將6個不同的小球放入4個不同的盒子中，允許空盒，且盒內(nèi)還要進行排列的方案數(shù)。故有：方法2：將9個字母進行全排列，有9!中排列，而x,y,z這3個字母形成的3!個排列只看作一種排列xyz，故有：1.35 凸十邊形的任意三條對角線不共點. 試求這凸十邊形的對角線交于多少個點？解 從一個頂點可引

28、出7條線和第一條（從右到左）交的有17，和第二條交的有26條,故和一個頂點引出的7條線相交的點為： 17+26+35+44+53+62+71=84故和從10點引出的對角線交的點有個8410=840，但每個點重復(fù)了四次（因為每個點在兩條線上，而每條線有兩個端點）。故凸10 邊形（這樣的）對角線交于個點, 故也可為1.36 試證一整數(shù)是另一整數(shù)的平方的必要條件是除盡它的數(shù)的數(shù)目是整數(shù).證 “必要性”。若整數(shù)n是另一個整數(shù)的平方，則n一定可寫成如下形式： （參見p7例4）其中p1,p2,pe是e個不同的素數(shù)。由于第9題可得，除盡n的正整數(shù)數(shù)目為 (2a1+1)(2a2+1)(2ae+1)為奇數(shù)?！俺?/p>

29、分性”。若除盡正整數(shù)n的正整數(shù)的數(shù)目為奇數(shù)。則n一定是某個正整數(shù)的平方，否則，n不是平方數(shù)，則n一定是可分解成如下形式：其中p1,p2,pe是e個不同的素數(shù)，且b1,b2,be中至少有一個奇數(shù)（否則n為平方數(shù)）。于是(2b1+1)(2b2+1)(2be+1)必為偶數(shù)，與充分性假設(shè)矛盾。1.37 給出的組合意義.證 組合意義一：從(n+r+1)個元素1,2,n+r+1中取出個元素i1i2irir+2ir+2 in+r+1-m 的個數(shù)是。其中第r+1個位置上的元素ir+1可取r+1,r+2,r+1+m。當ir+1取(r+1+k)時(k=0,1,2,m)，前邊r個數(shù)i1,i2,ir可在1,2,r+1

30、+(k-1)這(r+k)個數(shù)里取，故有種取法；后邊(n+r+1-m)-(r+1)=n-m個數(shù)ir+2,in+r+1-m可在r+1+k+1, ,n+r+1這(n+r+1)-(r+1+k)=n-k個數(shù)中取，故有。根據(jù)乘法原理，當ir+1=r+1+k時，這樣的組合數(shù)為。根據(jù)加法原理，對k=0,1,2,m作和，就有。注：參見 combinatorial problems and exercise by l.lovasz 0143.7 l896cp18-42 (i) p96 p172第15題圖1d(0, k)c (-1, k)a (-r-1, 0)o (0, 0)(i)the number of tho

31、se(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.組合意義二：（格路方法）等式左端：從點a(-r-1,0)到點c(-1,k)(k=0,1,2,m)直接經(jīng)過點d(0,k)再到點b(n-m,m)的路徑數(shù)(參見本題圖1)；等式右端：從點a(-r-1,0)到點b(n-m,m)的路徑數(shù)。1.38 給出的組合意義.證.組合意義一：等式右端是從n+r+1個元素中取出r+1個作不允許重復(fù)的組合，結(jié)果不外乎有以下幾種情況(參見p25等式3的組合意義)：第16題圖1(1)

32、 r+1個元素的組合中含有的，相當于從n個元素中取r個組合，其組合數(shù)為（即a）。(2)r+1個元素的組合中不含有，但又含有元素的。即一個(r-1)-組合。依來分，不外乎含和不含；不含的又依分，不外乎含和不含。不含而含的組合，相當于從n-1個元素中取r個元素的組合，然后加上而成，其組合數(shù)為。(3)r+1個元素的組合中不含和，但含有元素的。即不含的依來分，不外乎含和不含。不含而含的組合，相當于從n-2個元素中取出r個元素的組合，然后再加上而成，其組合數(shù)為。取出的r+1個組合元素中不含，但含有元素的。即不含的，又依來分，不外乎含有和不含有。不含而含的組合，相當于從n-(n-r-1)=r+1個元素中取

33、出r個元素的組合而加上而成，其組合數(shù)為。(4)由組成的(r+1)-組合的組合數(shù)為。而且組合意義二：等式右端：從n+1個不同元素a1,a2,an,an+1,中任選r+1個元素的組合方案數(shù)；等式左端：從n+1個不同元素a1,a2,an,an+1,中選取r+1個元素，一定選元素ar+k+1(k=0,1,2,n-r)，但是不選元素ar+k+2,an,an+1的組合方案數(shù)。1.39 證明證.借助p28等式4，可知： (nr) (r=0,1,2,n)從而有(用了p29等式5)組合意義一：等式右端可看作從m個元素中取出n個元素進行組合。然后對這取出的n個元素進行染色（紅，白）的所有方案，它為；等式左端可看作

34、先從m個元素中取出k個元素（個數(shù)為），全部染以紅色。再從剩下的(m-k)個元素中取出(n-k)個元素（個數(shù)為），全部染以白色。根據(jù)乘法原理，從m個元素中取出n個元素，k個染上紅色，(n-k)個染上白色的方案數(shù)為，k=0,1,2,n；而從m個元素中取出n個元素染以紅白兩色的方案可分解成有0個，1個，n個染以紅色的總和。故根據(jù)加法原理，17題成立。組合意義二：等式右端：將從m個不同的小球中任意選出的n個小球放入兩個不同的合子里，注意到每個小球都有兩種放法，就得到了可能的放球方案數(shù)；等式左端：先從m個球中任選k個球放入第一個合子里(k=0,1,2,n)，再從剩下的m-k個球中任選n-k個球放入第二個

35、合子里，然后對k從0到n求和，就得到了所有可能的放球方案數(shù)。1.40 從n個人中選r個圍成一個圓圈，問有多少種不同的方案？解.每一個r個人圍成的圈（圓排列）即每一個r圈相當于r個r排列。故不同的方案數(shù)為若不計順逆方向，則為。1.41 分別寫出按照字典序由給定排列計算其對應(yīng)序號的算法及由給定序號計算其對應(yīng)排列的算法.解.（略）1.42 (a) 按照1.41的要求，寫出鄰位對換法（排列的生成算法之二）的相應(yīng)算法.(b) 寫出按照鄰位對換法由給定排列生成其下一個排列的算法.解.（略）1.43 對于給定的正整數(shù)n，證明，當時，c(n,k)的最大值.證 取c(n,k)與c(n,k-1)進行比較。c(n,

36、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。因此，可給定初始值：g(2k-1,k)=1，g(2k-2,k)=0。1.50 (a) 在由5個0，4個1組成的字符串中，出現(xiàn)01或10的總次數(shù)為4的字符串，有多少個？(b) 在m個0，n個1組成的字符串中，出現(xiàn)01或10的總次數(shù)為k的字符串，有多少個？解 (a)先將5個0排成一列：00000，一個1若插在兩個0中間，就形成一個“010”，則同時出現(xiàn)“01”和“10”，計數(shù)為2；若插在兩端，則僅出現(xiàn)一個01”或“10”，計數(shù)為1?，F(xiàn)在要出現(xiàn)01”或“10”的總次數(shù)為4，可有兩種辦法：(1)先把兩個1插入五個0所形成的四個空檔內(nèi)，再將剩下的兩個1放在已插入的1的前面，比如：011100100。按乘法原理，有c(4,2)c(2+2-1,2)= c(4,2)c(3,2)種方案；(2)先把一個1插入五個0所形成的四個空檔內(nèi)，然后取兩個1分別插入兩端，剩下的一個1放在已插入的1的前面，比如：100011001。按乘法原理，有c(4,1)3種方案；最后，按加法原理，總的方案