组合数学题库答案

5．一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。

证明 设从第一天到第i天她共学习了ai小时。因为她每天至少学习1小时，所以

a1,a2,?,a37和a1?13,a2?13,?,a37?13都是严格单调递增序列。因为总的学习时间

不超过

60

小时，所以a37?60，a37?13?73。a1,a2,?,a37,

a1?13,a2?13,?,a37?13是1和73之间的74个整数，由鸽巢原理知道，它们中存在相

同的整数，有ai和aj?13使得ai?aj?13，ai?aj?13，从第j?1天到第i天她恰好学习了13小时。

6．8个女孩围坐在旋转木马上。她们可以有多少种方法改变座位，使得每个女孩前面的女孩都与原先的不同？

解 令S为{1,2,3,4,5,6,7,8}的全部7!个循环排列的集合，Ai为出现模式i(i?1)的循环排列的集合（1?i?7），A8为出现模式81的循环排列的集合。若1?k?7且i1,?,ik是集合{1,2,3,4,5,6,7,8}中的不同整数，则|Ai???Ai|?(7?k)!。|1ki?1 ?Ai|?1。因此，

8?8??8??8??8??8??8??8?????????????|A1???A8|?7!??6!?5!?4!?3!?2!?1!??1??2??3??4??5??6??7??0!?1?1625 ??????????????她们可以有1625种方法改变座位。

7．把2n?1个苹果送给3个孩子，若使得任意两个孩子得到的苹果总数大于另一个孩子的苹果树，问有多少种分法？

根据题意写出生成函数如下(1?yn?1)3A(y)?(1?y?y???y)?(1?y)32n3?(1?3yn?1?3y2n?12n?2?y3n?3)?n?0???n?22上述展开式中yN?项的系数为1)n??3???(n?2n?22

?2n?1?22