湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題20

習(xí)題二十1. 由5個(gè)字母和8個(gè)字母能組成多少個(gè)非空字母集合?分析：本題主要是對(duì)每一種出現(xiàn)的情況分別討論，然后根據(jù)多重集定理就可以求得。解：此問(wèn)題可化為多重集，則S的（1）1-組合有：，此種情況排列種數(shù)為：，（2）2-組合有： ，此種情況排列種數(shù)為：，（3）3-組合有：，此種情況排列種數(shù)為：，（4）4-組合有：，此種情況排列種數(shù)為：，（5）5-組合有：，此種情況排列種數(shù)為：，（6）6-組合有：，此種情況排列種數(shù)為：，（7）7-組合有：，此種情況排列種數(shù)為：，（8）8-組合有：，此種情況排列種數(shù)為：，（9）9-組合有：，此種情況排列種數(shù)為：，（10）10-組合有：，此種情況排列種數(shù)為：，（11）11-組合有：，此種情況排列種數(shù)為：，（12）12-組合有：，此種情況排列種數(shù)為：，（13）13-組合有：，此種情況排列種數(shù)為：所以總的非空序列為所有的r-組合（）數(shù)目之和，即：2+4+8+16+32+63+120+219+381+427+957+1287+1287=4803.2.用字母來(lái)形成3個(gè)字母的一個(gè)序列,滿足以下條件的方式各有多少種?(1)允許字母重復(fù);(2)不允許任何字母重復(fù);(3)含字母的序列不允許重復(fù);(4)含字終的序列允許重復(fù).分析：本題主要是排列組合的簡(jiǎn)單應(yīng)用。解：（1）由于允許字母重復(fù)，所以每個(gè)都有6種排法，所以總共有63=216種排列.(2)不允許任何字母重復(fù)情況下，也就是用6個(gè)字母排列成3序列，所以共有（3）這種情況可以有兩種情形：（1）每個(gè)序列沒(méi)有e，這種情形下序列允許重復(fù)也就是用a,b,c,d,f去填充序列的3個(gè)分量，就是。（2）每個(gè)序列都有一個(gè)e，這種情況下，每個(gè)分量都不能相同，首先從3個(gè)序列中選出一個(gè)分量填充e，選擇方法為然后用其余的a,b,c,d,f填充序列的剩余2個(gè)分量，所以這種情況下排列方法為：；將這兩種情形加和得到125+60=185。（4）因?yàn)楹帜竐的序列可以重復(fù)，而不含字母e的也可以重復(fù)，所以該題和（1）同樣的結(jié)果。3.由數(shù)字1,2,3,4,5構(gòu)成一個(gè)3位數(shù),滿足下列條件的方法各有多少種?(1)是一個(gè)偶數(shù);(2)可以被5整除;(3).分析：（1）因?yàn)閍是一個(gè)偶數(shù)，所以個(gè)位為偶數(shù)，所以個(gè)位有2，4兩種排法，但是前面可以任意排列。（2）因?yàn)閍可以被整除，則個(gè)位為，只有一種排法，前面兩位可以任意排列。（3）由于，所以百位只能排，三種排列方法，其余兩位可以任意排。解：（1）a是一個(gè)偶數(shù)，所以個(gè)位為偶數(shù)，所以個(gè)位有2，4兩種排法，前面兩位可以用1，2，3，4，5進(jìn)行任意排列，有52=25種排法，由于是分部排列，所以用乘法結(jié)果為2×。（）a可以被整除，則個(gè)位為，只有一種排法，前面兩位可以用1，2，3，4，5任意排列，有52=25種排法，由于是分部排列，所以用乘法結(jié)果為×。（）由于，所以百位只能排，三種排列方法，其余兩位可以任意排列1，2，3，4，5，共有52=25種排法，由于是分部排列，所以用乘法結(jié)果為×。4. 設(shè)A,B,C是三個(gè)城市.從A到B可以乘飛機(jī),火車,也可以乘船;從B到C可以乘飛機(jī)和火車;從A不經(jīng)過(guò)B到C可以乘飛機(jī)和火車.問(wèn):(1)從A到C可以有多少種不同的方法?(2)從A到C,最后又回到A有多少種方法?解：（1）該種情況可以有兩種情形：第一種，直接從A到C有兩種，第二種，從A出發(fā)經(jīng)過(guò)B到C，由于從A到B有3中方法，從B到C有2種方法，所以從A出發(fā)經(jīng)過(guò)B到C有3×種，綜合這兩種情況可以知道共有種方法從到。（）由于從到仍然有種方法，而從到然后又從到才完成所有的過(guò)程，所以是分部，所以共有×種方法。5.在5天內(nèi)安排3門課程的考試.(1)若每天只允許考1門,有多少種方法?(2)若不限于每天考試的門 ,有多少種方法?解：（）如果每天只考一門，所以也就是把門課放進(jìn)天中間中的某天，所以共有中排列方法。（）如果不限每天考試的門，則有如下幾種情況：第一種，一天考完，但是門課不同，則安排的次序有種，共有×種方法；第二種兩天考完，必定會(huì)出現(xiàn)某一天考兩門，則有排法，某一天考一門，有種排法，所以安排完考試，共有種排法；第三種三天考完也就是（）的情況，排法為，所以若不限每天考試的門數(shù)，共有種排列方法。6排列26個(gè)字母，使得和之間正好有7個(gè)字母，問(wèn)有多少種排列法?解：由于a和b之間恰有7個(gè)字母，則從26個(gè)字母中取7個(gè)字母共有，然后對(duì)這7個(gè)字母進(jìn)行全排列共有，然后把a(bǔ)，b在這7個(gè)字母的兩端共有2種排法，最后將a，b以及所取出的7個(gè)字母一起作為一個(gè)整體進(jìn)行全排列共有，所以總的排列方法為：。710個(gè)男孩與5個(gè)女孩站成一排如果沒(méi)有兩個(gè)女孩相鄰，問(wèn)有多少種方法?解：首先把10個(gè)男孩排好，中間形成9個(gè)空，加上兩邊的2個(gè)空，總共形成11個(gè)空；排列10個(gè)男孩共有種排列方法，然后把5個(gè)女孩插入到11個(gè)空中，就有種排列方法，所以總的排列方法為。810個(gè)男孩與5個(gè)女孩站成一個(gè)圓圈如果沒(méi)有兩個(gè)女孩相鄰，問(wèn)有多少種方法?解：首先把10個(gè)男孩排好，中間形成10個(gè)空，然后把5個(gè)女孩插入到這10個(gè)空中；排列10個(gè)男孩的共有（這是因?yàn)殡m然有序，但是沒(méi)有首尾之分），然后把5個(gè)女孩插入到10個(gè)空中，就有種排列方法，所以總的排列方法為。9從1，2，300之中任取3個(gè)數(shù)，使得它們的和能被3整除，問(wèn)有多少種方法?解：將1，2，300按照模3剩余類進(jìn)行劃分為3個(gè)集合：、任取1，2，300中的3個(gè)數(shù)的和能被3整除，那只有如下2種情況：第一種，所取的數(shù)全部來(lái)自，此時(shí)共有；第二種，所取的數(shù)全部來(lái)自，此時(shí)共有；第三種，所取的數(shù)全部來(lái)自，此時(shí)共有；第四種，所取的三個(gè)數(shù)來(lái)自三個(gè)不同的集合，此時(shí)共有；所以共有種方法； 10證明：對(duì)一切，有證明:該題有兩種證法。第一種使用公式，因?yàn)椋坏诙N使用組合論的觀點(diǎn)解釋，從n個(gè)人中選出r個(gè)人去參加會(huì)議，剩下的人留在家里和從n個(gè)人中選出n-r個(gè)人留在家里，剩下的人去參加會(huì)議的含義是一樣的，所結(jié)論成立。116個(gè)字母有多少種排列?解：該題可以此問(wèn)題可化為多重集，則S的排列數(shù)N由定理有。12由0，l，2三個(gè)數(shù)字可組成多少個(gè)位數(shù)字串?解：本題中可以化成多重集，因?yàn)槊恳晃欢伎梢杂衝中排法，則S的n排列數(shù)是3n。13設(shè)有5種明信片，每種張數(shù)不限，現(xiàn)分別寄給2個(gè)朋友，若給每個(gè)朋友只寄1張明信片，有幾種方法?若給每個(gè)朋友寄l張明信片，但每個(gè)朋友得到的明信片都不相同，有幾種方法?若給每個(gè)朋友寄2張不同的明信片，不同的人可以得到相同的明信片，有幾種方法?解：若每個(gè)朋友只寄一張明信片，則由于每個(gè)人的明信片可以相同，則每個(gè)人都有5種郵寄方法，所以共有52=25種方法；如果每個(gè)朋友的明信片不同，那么共有種方法；如果每個(gè)朋友2張，不同的人可以得到相同的明信片，那么從5種明信片中選出2張，共有種選法，每個(gè)人得到的2張明信片可能屬于任何一種選法，于是所求的方法數(shù)是。14有相同的紅球4個(gè)，蘭球3個(gè)，白球3個(gè)如果將它們排成一條直線，則有多少方法?如果是排成一個(gè)圓圈又有多少種方法?解：設(shè)球的集合，如果將它們排成一條線，根據(jù)定理可以立即得到其排列方式為：；如果排成一個(gè)圓圈，由于圓排列是線排列的1/10,所以所得到的結(jié)果為420.15求多重集中的所有元素構(gòu)成的排列數(shù)，要求同類字母的全體不能相鄰例如排列等是不允許的解：多重集S的全排列數(shù)為，令所有這樣的排列構(gòu)成集合T，如下構(gòu)造T的子集：為了計(jì)數(shù)這些子集的元素?cái)?shù)，可將連續(xù)的字母看成一個(gè)打字母，從而有根據(jù)對(duì)應(yīng)的計(jì)數(shù)公式有類似地分析可得由容斥原理有：