湘潭大学 刘任任版 离散数学课后习题答案 习题20

习题二十

1. 由5个字母a和8个字母b能组成多少个非空字母集合?

分析：本题主要是对每一种出现的情况分别讨论，然后根据多重集定理就可以求得。 解：此问题可化为多重集S?{5?a,8?b}，则S的

1!1!??2{1?a,0?b},{0?a,1?b}（1）1-组合有：，此种情况排列种数为：1!?0!1!?0!，

（2）2-组合有： {0?a,2?b},{2?a,0?b},{1?a,1?b}，此种情况排列种数为：

2!2!2!???1?1?2?42!?0!2!?0!1!?1!，

1?a,2?b},{2?a,1?b},{3?a,0?b},{0?a,3?b}，此种情况排列（3）3-组合有：{3!3!3!3!????3?3?1?1?82!?1!2!?1!3!?0!3!?0!种数为：，

（4）4-组合有：{0?a,4?b},{4?a,0?b},{1?a,3?b},{3?a,1?b},{2?a,2?b}，此

4!4!4!4!4!?????1?1?4?4?6?164!?0!4!?0!3!?1!3!?1!2!?2!种情况排列种数为：，

（5）5-组合有：

{0?a,5?b},{5?a,0?b},{1?a,4?b},{4?a,1?b},{2?a,3?b},{3?a,2?b}，此种

情况排列种数为：

5!5!5!5!5!5!??????1?1?5?5?10?10?325!?0!5!?0!4!?1!4!?1!3!?2!3!?2!，

（6）6-组合有：

{0?a,6?b},{1?a,5?b},{5?a,1?b},{2?a,4?b},{4?a,2?b},{4?a,2?b}，此种情况排列种数为：

6!6!6!6!6!6!??????1?6?6?15?15?20?636!?0!5!?1!5!?1!2!?4!4!?2!3!?3!，

（7）7-组合有：

{0?a,7?b},{1?a,6?b},{2?a,5?b},{5?a,2?b},{3?a,4?b},{4?a,3?b}，此种

情况排列种数为：

7!7!7!7!7!7!??????1?7?21?21?35?35?1207!?0!1!?6!2!?5!5!?2!3!?4!4!?3!，

（8）8-组合有：

{0?a,8?b},{1?a,7?b},{2?a,6?b},{3?a,5?b},{4?a,4?b},{5?a,3?b}，此种

情况排列种数为：

8!8!8!8!8!8!??????1?8?28?56?70?56?2190!?8!1!?7!2!?6!3!?5!4!?4!5!?3!，

（9）9-组合有：

{1?a,8?b},{2?a,7?b},{3?a,6?b},{4?a,5?b},{5?a,4?b}，此种情况排列种数为： 9!9!9!9!9!?????9?36?84?126?126?3811!?8!2!?7!3!?6!4!?5!5!?4!，

（10）10-组合有：

{2?a,8?b},{3?a,7?b},{4?a,6?b},{5?a,5?b}，此种情况排列种数为： 10!10!10!10!????45?120?210?252?4272!?8!3!?7!4!?6!5!?5!，

（11）11-组合有：

{3?a,8?b},{4?a,7?b},{5?a,6?b}，此种情况排列种数为： 11!11!11!???165?330?462?9573!?8!4!?7!5!?6!，

（12）12-组合有：

{4?a,8?b},{5?a,7?b}，此种情况排列种数为： 12!12!??495?792?12874!?8!5!?7!，

（13）13-组合有：

{5?a,8?b}，此种情况排列种数为： 13!?12875!?8!

所以总的非空序列为所有的r-组合（r?1,2,?,13）数目之和，即：2+4+8+16+32+63+120+219+381+427+957+1287+1287=4803.

2.用字母a,b,c,d,e,f来形成3个字母的一个序列,满足以下条件的方式各有多少种?

(1)允许字母重复;

(2)不允许任何字母重复;

(3)含字母e的序列不允许重复;

(4)含字终e的序列允许重复.

分析：本题主要是排列组合的简单应用。 解：（1）由于允许字母重复，所以每个都有6种排法，所以总共有63=216种排列. (2)不允许任何字母重复情况下，也就是用6个字母排列成3序列，所以共有

P63?120

（3）这种情况可以有两种情形：（1）每个序列没有e，这种情形下序列允许重复也就

35?125。是用a,b,c,d,f去填充序列的3个分量，就是（2）每个序列都有一个e，这

1C种情况下，每个分量都不能相同，首先从3个序列中选出一个分量填充e，选择方法为3然后用其余的a,b,c,d,f填充序列的剩余2个分量

P25，所以这种情况下排列方法为：

12C3P5?60；将这两种情形加和得到125+60=185。

（4）因为含字母e的序列可以重复，而不含字母e的也可以重复，所以该题和（1）同样的结果。

3.由数字1,2,,3,4,5构成一个3位数a,满足下列条件的方法各有多少种?

(1)a是一个偶数; (2)a可以被5整除; (3)a?300. 分析：（1）因为a是一个偶数，所以个位为偶数，所以个位有2，4两种排法，但是前面可以任意排列。（2）因为a可以被５整除，则个位为５，只有一种排法，前面两位可以任意排列。（3）由于a?300，所以百位只能排３，４，５三种排列方法，其余两位可以任意排。

解：（1）a是一个偶数，所以个位为偶数，所以个位有2，4两种排法，前面两位可以用1，2，3，4，5进行任意排列，有52=25种排法，由于是分部排列，所以用乘法结果为 2×２５＝５０。

（２）a可以被５整除，则个位为５，只有一种排法，前面两位可以用1，2，3，4，5任意排列，有52=25种排法，由于是分部排列，所以用乘法结果为 １×２５＝２５。

（３）由于a?300，所以百位只能排３，４，５三种排列方法，其余两位可以任意排列1，2，3，4，5，共有52=25种排法，由于是分部排列，所以用乘法结果为 ３×２５＝７５。

4. 设A,B,C是三个城市.从A到B可以乘飞机,火车,也可以乘船;从B到C可以乘飞机和火车;从A不经过B到C可以乘飞机和火车.问:

(1)从A到C可以有多少种不同的方法? (2)从A到C,最后又回到A有多少种方法? 解：（1）该种情况可以有两种情形：第一种，直接从A到C有两种，第二种，从A出发经过B到C，由于从A到B有3中方法，从B到C有2种方法，所以从A出发经过B

到C有3×２＝６种，综合这两种情况可以知道共有２＋６＝８种方法从Ａ到Ｃ。

（２）由于从Ｃ到Ａ仍然有８种方法，而从Ａ到Ｃ然后又从Ｃ到Ａ才完成所有的过程，所以是分部，所以共有８×８＝６４种方法。

5.在5天内安排3门课程的考试.

(1)若每天只允许考1门,有多少种方法? (2)若不限于每天考试的门 ,有多少种方法? 解：（１）如果每天只考一门，所以也就是把３门课放进５天中间中的某３天，所以共有P53?60中排列方法。

（２）如果不限每天考试的门，则有如下几种情况：第一种，一天考完，但是３门课不同，则安排的次序有３种，共有３×５＝１５种方法；第二种两天考完，必定会出现某一天

11考两门，则有C5种排法，所以安排完考试，共有?P22排法，某一天考一门，有C411C5?P22?C4?40种排法；第三种三天考完也就是（１）的情况，排法为６０，所以若

不限每天考试的门数，共有１５＋４０＋６０＝１１５种排列方法。

6．排列26个字母，使得a和b之间正好有7个字母，问有多少种排列法?

7解：由于a和b之间恰有7个字母，则从26个字母中取7个字母共有C26，然后对这77个字母进行全排列共有C26然后把a，b在这7个字母的两端共有2种排法，最后将a，P77，18b以及所取出的7个字母一起作为一个整体进行全排列共有P18，所以总的排列方法为：7182?C26P77?P18。

7．10个男孩与5个女孩站成一排．如果没有两个女孩相邻，问有多少种方法?

解：首先把10个男孩排好，中间形成9个空，加上两边的2个空，总共形成11个空；

10

排列10个男孩共有P10种排列方法，然后把5个女孩插入到11个空中，就有P11种排列方105法，所以总的排列方法为P?P1011。

58．10个男孩与5个女孩站成一个圆圈．如果没有两个女孩相邻，问有多少种方法?

解：首先把10个男孩排好，中间形成10个空，然后把5个女孩插入到这10个空中；排列10个男孩的共有P99（这是因为虽然有序，但是没有首尾之分），然后把5个女孩插入

55到10个空中，就有P10种排列方法，所以总的排列方法为P99?P10。

9．从1，2，…，300之中任取3个数，使得它们的和能被3整除，问有多少种方法?

解：将1，2，…，300按照模3剩余类进行划分为3个集合：、

S0?{3,6,?,300},S1?{1,4,?,298},S2?{2,5,?,299},任取1，2，…，300中的3

3个数的和能被3整除，那只有如下2种情况：第一种，所取的数全部来自S0，此时共有C100；3第二种，所取的数全部来自S1，此时共有C100；第三种，所取的数全部来自S2，此时共有

33；第四种，所取的三个数来自三个不同的集合，此时共有33?33?33?33；所以共C1003有3?C100?333种方法；

10．证明：对一切r?n，有

rn?r Cn?Cn证明:该题有两种证法。第一种使用公式，因为

rCn?n!n!n!r?rr；第二种使用组合论的,Cn???Cn(n?r)!?r!(n?(n?r))!?(n?r)!(n?r)!?r!观点解释，从n个人中选出r个人去参加会议，剩下的人留在家里和从n个人中选出n-r个人留在家里，剩下的人去参加会议的含义是一样的，所结论成立。 11．6个字母b,a,c,a,c,a有多少种排列?

解：该题可以此问题可化为多重集S?{3?a,1?b,2?c}，则S的排列数N由定理有

N?6!?60。

3!?1!?2!12．由0，l，2三个数字可组成多少个n位数字串?

解：本题中可以化成多重集S?{??0,??1,??2}，因为每一位都可以有n中排法，则S的n排列数是3n。 13．设有5种明信片，每种张数不限，现分别寄给2个朋友，若给每个朋友只寄1张明信片，有几种方法?若给每个朋友寄l张明信片，但每个朋友得到的明信片都不相同，有几种方法?若给每个朋友寄2张不同的明信片，不同的人可以得到相同的明信片，有几种方法?

解：若每个朋友只寄一张明信片，则由于每个人的明信片可以相同，则每个人都有5种邮寄方法，所以共有52=25种方法；如果每个朋友的明信片不同，那么共有P52种方法；如果每个朋友2张，不同的人可以得到相同的明信片，那么从5种明信片中选出2张，共有

22每个人得到的2张明信片可能属于任何一种选法，于是所求的方法数是(C5 C52种选法，)。

14．有相同的红球4个，兰球3个，白球3个．如果将它们排成一条直线，则有多少方法?

如果是排成一个圆圈又有多少种方法?

解：设球的集合S?{4?红,3?兰,3?白}，如果将它们排成一条线，根据定理可以立即得到其排列方式为：

10!?4200；如果排成一个圆圈，由于圆排列是线排列的1/10,

4!?3!?3!所以所得到的结果为420.

15．求多重集S?{3?a,4?b,2?c}中的所有元素构成的排列数，要求同类字母的全体不能相

,baaaabbccb邻．例如排列abbbbcaac等是不允许的．

解：多重集S的全排列数为??? 9??，令所有这样的排列构成集合T，如下构造T的子集： ??3 4 2?T1?{x|x?T且x中含有连续的3个a}， T2?{x|x?T且x中含有连续的4个b}，T3?{x|x?T且x中含有连续的2个c}，为了计数这些子集的元素数，可将连续的字母看成一个打字母，从而有

x?T1?x为{1?a,4?b,2?c}的全排列， x?T2?x为{3?a,1?b,2?c}的全排列，x?T3?x为{3?a,4?b,1?c}的全排列，根据对应的计数公式有

? 7?? 6?? 8??????|T1|??,|T2|??,|T3|??, ?????1 4 2??3 1 2??3 4 1?类似地分析可得

? 4?? 6?? 8?? 3???????|T1?T2|??,|T?T|?,|T?T|?,|T?T?T|?3323?1 1 2?1?1 4 1?2?3 4 1?1?1 1 1??, ????????由容斥原理有：

|T1?T2?T3|?|T|?(|T1|?|T2|?|T3|)?(|T1?T2|?|T1?T3|?|T2?T3|)?|T1?T2?T3|?? 9?? 7?? 6?? 8?? 4?? 6?? 5?? 3??????????3 4 2??[?1 4 2???3 1 2???3 4 1?]?[??1 1 2?????1 4 1?????3 1 1??]???1 1 1???????????????????9!7!6!8!4!6!5!3!?(??)?(??)??8713!4!2!4!2!3!2!3!4!2!4!3!1!

本文来源：https://www.bwwdw.com/article/q3t3.html