发布时间 : 星期四 文章组合数学引论课后答案更新完毕开始阅读
2.13 证明：对于任意大于等于2的正整数n，都有R(2,n)=n。 2.13证明：
要证R（2，n）= n，用红蓝两色涂色Kn的边。 当n=2时，R(2,2)=2，因为不管用红还是蓝色都是完全二边形。
假设当n=k时 成立 ，即存在R(2,k)=k（没有一条红边，只有蓝边）， 当n=k+1时，R（2，k+1）
若无红边，要想有完全k+1边形，必得有k+1个点，即R（2，k+1）=k+1。证明成立。
习题三
3.1 有10名大学生被通知参加用人单位的面试，如果5个人被安排在上午面试，5个人被安排在下午面试，则有多少种不同的安排面试的顺序？ 解：上午的5个人全排列为5！ 下午的5个人全排列为5！
5所以有C10*5!*5!?10!，共14400种不同的安排方法。
3.2 某个单位内部的电话号码是4位数字，如果要求数字不能重复，那么最多可有多少个号码？如果第一位数字不能是0，那么最多能有多少个电话号码？
解：由于数字不能重复，0-9共10个数字，所以最多有10*9*8*7=5040种号码；若第一位不能是0，则最多有9*9*8*7=4536种号码。
3.3 18名排球运动员被分成A,B,C三个组，使得每组有6名运动员，那么有多少种分法？如果是分成三个组（不可区别），使得每组仍有6名运动员，那么有多少种分法？
666解：1)C18种 *C12*C6 2)
666/3! C18*C12*C63.4 教室有两排，每排8个座位。现有学生14人，其中的5个人总坐在前排，4个人总坐在后排，求有多少种方法将学生安排在座位上？
解：前排8个座位，5人固定，共C85*5!种方法；后排8个座位，4人固定，共C84*4!种方法；前排和后排还剩7个座位，由剩下的5人挑选5个座位，共C75*5!种方法；则一共有
55C8*C84*C7*5!*5!*4!种安排方法。
3.5 将英文字母表中的26个字母排序，要求任意两个元音字母不能相邻，则有多少种排序方法？
解：先排21个辅音字母，共有21！ 再将5个元音插入到22个空隙中，P
522故所求为21!?P
522(插入法)
3.6 有6名先生和6名女士围坐一个圆桌就餐，要求男女交替就坐，则有多少种不同的排坐方式？ 解：6男全排列6!；6女全排列6！；6女插入6男的前6个空或者后6个空，即女打头或男打头6!*6!*2；再除以围圈重复得(6!*6!*2)/12=6!*5! 或
男6的圆排列为5！，对每个男的排列，女要在他们之间的6个位置，进行线性排列6！（而不是5！）。
（圆排列可以通过线性排列来解决）
3.7 15个人围坐一个圆桌开会，如果先生A拒绝和先生B和C相邻，那么有多少种排坐方式？ 解：15人圆排列14！； A与B相邻有2*14!/14=2*13!； A与C相邻有2*14!/14=2*13!； A与BC同时相邻有2*13!/13=2*12!；
于是A不与B、C相邻的坐法共14!- 2*13!- 2*13!+ 2*12!（用到了容斥原理）
3.8 确定多重集M?{3?a,4?b,5?c}的11-排列数？ 解：M的11排列=[M-{a}]的11排列+[M-{b}]的11排列+[M-{c}]的11排列，即
11!11!11!=27720 ??2!4!5!3!3!5!3!4!4!当然了，容斥原理，生成函数也可以做。