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

《湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題20》由會(huì)員分享，可在線閱讀，更多相關(guān)《湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題20（6頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、習(xí)題二十 1. 由5個(gè)字母和8個(gè)字母能組成多少個(gè)非空字母集合? 分析：本題主要是對(duì)每一種出現(xiàn)的情況分別討論，然后根據(jù)多重集定理就可以求得。 解：此問題可化為多重集，則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-組合有：

2、 ，此種情況排列種數(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.用字母來形成3個(gè)字母的一個(gè)序列,滿足以下條件的方式各有多少種? (1)允許字母重復(fù); (2)不允許任何字母重復(fù); (3)含字母的序列不允許重復(fù); (4)含字終的序列允許

3、重復(fù). 分析：本題主要是排列組合的簡(jiǎn)單應(yīng)用。 解：（1）由于允許字母重復(fù)，所以每個(gè)都有6種排法，所以總共有63=216種排列. (2)不允許任何字母重復(fù)情況下，也就是用6個(gè)字母排列成3序列，所以共有 （3）這種情況可以有兩種情形：（1）每個(gè)序列沒有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ù)

4、，而不含字母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é)

5、果為 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)過B到C可以乘飛機(jī)和火車.問: (1)從A到C可以有多少種不同的方法? (2)從A到C,最后又回到A有多少種方法? 解：（1）該

6、種情況可以有兩種情形：第一種，直接從A到C有兩種，第二種，從A出發(fā)經(jīng)過B到C，由于從A到B有3中方法，從B到C有2種方法，所以從A出發(fā)經(jīng)過B到C有3×２＝６種，綜合這兩種情況可以知道共有２＋６＝８種方法從Ａ到Ｃ。 （２）由于從Ｃ到Ａ仍然有８種方法，而從Ａ到Ｃ然后又從Ｃ到Ａ才完成所有的過程，所以是分部，所以共有８×８＝６４種方法。 5.在5天內(nèi)安排3門課程的考試. (1)若每天只允許考1門,有多少種方法? (2)若不限于每天考試的門 ,有多少種方法? 解：（１）如果每天只考一門，所以也就是把３門課放進(jìn)５天中間中的某３天，所以共有中排列方法。 （２）如果不限每天考試的門，則有如下幾種情

7、況：第一種，一天考完，但是３門課不同，則安排的次序有３種，共有３×５＝１５種方法；第二種兩天考完，必定會(huì)出現(xiàn)某一天考兩門，則有排法，某一天考一門，有種排法，所以安排完考試，共有種排法；第三種三天考完也就是（１）的情況，排法為６０，所以若不限每天考試的門數(shù)，共有１５＋４０＋６０＝１１５種排列方法。 6．排列26個(gè)字母，使得和之間正好有7個(gè)字母，問有多少種排列法? 解：由于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)行全排列共有，所以總的排列方法為：。 7

8、．10個(gè)男孩與5個(gè)女孩站成一排．如果沒有兩個(gè)女孩相鄰，問有多少種方法? 解：首先把10個(gè)男孩排好，中間形成9個(gè)空，加上兩邊的2個(gè)空，總共形成11個(gè)空；排列10個(gè)男孩共有種排列方法，然后把5個(gè)女孩插入到11個(gè)空中，就有種排列方法，所以總的排列方法為。 8．10個(gè)男孩與5個(gè)女孩站成一個(gè)圓圈．如果沒有兩個(gè)女孩相鄰，問有多少種方法? 解：首先把10個(gè)男孩排好，中間形成10個(gè)空，然后把5個(gè)女孩插入到這10個(gè)空中；排列10個(gè)男孩的共有（這是因?yàn)殡m然有序，但是沒有首尾之分），然后把5個(gè)女孩插入到10個(gè)空中，就有種排列方法，所以總的排列方法為。 9．從1，2，…，300之中任取3個(gè)數(shù)，使得它們的和能被

9、3整除，問有多少種方法? 解：將1，2，…，300按照模3剩余類進(jìn)行劃分為3個(gè)集合：、 任取1，2，…，300中的3個(gè)數(shù)的和能被3整除，那只有如下2種情況：第一種，所取的數(shù)全部來自，此時(shí)共有；第二種，所取的數(shù)全部來自，此時(shí)共有；第三種，所取的數(shù)全部來自，此時(shí)共有；第四種，所取的三個(gè)數(shù)來自三個(gè)不同的集合，此時(shí)共有；所以共有種方法； 10．證明：對(duì)一切，有 證明:該題有兩種證法。第一種使用公式，因?yàn)?；第二種使用組合論的觀點(diǎn)解釋，從n個(gè)人中選出r個(gè)人去參加會(huì)議，剩下的人留在家里和從n個(gè)人中選出n-r個(gè)人留在家里，剩下的人去參加會(huì)議的含義是一樣的，所結(jié)論成立。 11．6個(gè)字母有多少種排

10、列? 解：該題可以此問題可化為多重集，則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è)朋友的明信片不同，那么共有種方法；如

11、果每個(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ù)公式有 類似地分析可得 由容斥原理有：