令A??1，2，?，73?，A1??a1,a2,?,a37?,A2??b1,b2,?,b37?,则A1?A2?A.如果
A1?A2??，则
A?A1?A2?A1?A2?37?37?74,这与A?73矛盾，所以A1?A2??，从而存在
ak?A1,bl?A2,使得ak?bl,即ak?al?13,ak?al?13,这表明该学生从第l?1天到第k天共做了13道数学题。
5．证明 ：C(2n,2)?2C(n,2)?n。这里，C(m,n)表示从m个对象中取n个的方法数。 答案：等式左边表示从2n个不同的球中取两个球的方法数。我们把2n个球平均分成A，B两组，选球的方法有以下两类：去自同一组的选法数为N1?2C(n,2); 取自不同组的球的方法数为N2?[C(n,1)]?n
6．如n, r∈N且n≥r≥2，则P(n,r)= r×P(n-1,r-1)+P(n-1,r) 。
证明：当r≥2时，把集合A的r?排列分为两大类：一类包含A中的某个固定元素，不妨设为a1，另一类不包含a1 。第一类排列相当于先从A-{a1}中取r-1个元素进行排列，有P(n-1,r-1)种取法，再将a1放入每一个上述排列中，对任一排列，a1都有r种放法。由乘法法则，第一类排列共有r×P(n-1,r-1)个。第二类排列实质上是A-{a1}的r?排列，共有P(n-1,r)个。再由加法法则有 P(n,r)= r×P(n-1,r-1)+P(n-1,r) 证毕。
7．用非降路径法证明：
222C(m?n,n)?C(m?n?1,n?1)?C(m?n?1,n)
这里，C(m,n)表示从m个对象中n取个元素的方法数。
答案：（0,0）到（m,n）的路径数为C(m+n , n); 又，(0,0)到(m,n) 的任一路径必过(m-1,n)或 (m.n-1)。故，等式成立；
?m??n??m??n??m??n??m?n????8．证明：????????????????。
0r1r?1r0r??????????????
应用题
1．一次宴会，5位来宾寄存他们的帽子，在取帽子的时候有多少种可能使得没有 一位来宾取回的是他自己的帽子？
44种可能使得没有一位来宾取回的是他自己的帽子。 解：属于重排问题，所求为D5。D5?5（!1?11111????）?44………（6分） 1！2！3！4！5！n对夫妻围圆桌就座，要求每对夫妻不相邻，问有多少种入座方式？
2．平面上有n(n?2)个圆，任何两个圆都相交但无3个圆共点，求这n个圆把平
面划分成多少个不连通的区域。
解：设这n个圆分平面为an个不连通区域.若再增加一个圆，则增加的圆与原来的圆共有2n个交点，也就分成了2n段，每一段分所在区域为两个区域，即增加了2n个区域. 所以an?1?an?2n
an?an?1?2(n?1) ?1?
………
a2?a1?2?1 ?n?1? ………（3分）
将以上?1?至?n?1?等式相加得：
an?a1?n?n?1??2?n?n?1??n2?n?2。 ………（6分）
3．用17张100元钱买3支股票，不要求每支股票都买，但要求买A股钱数必须 是200的倍数，买B股钱数是400的倍数，求有多少种买法？ 25种买法。
解：此题等同于求方程x1?2x2?4x3?17的非负整数解的个数。 ………（1分）
方程通过换元可变为：y1?y2?y3?17，其中y1为非负整数，y2为非负偶数，y3为
非负的4的倍数的整数。………（3分）
由此构造常生函数： (1?t?t??)(1?t?t??)(1?t?t??)所求为常生成函数的t17的系数，化简生成函数为：
223481111824?2，可求得公式得的系数为25。……（6t???(1?t)(1?t)(1?t)241?t1?t1?t分）
4．方程x1?x2?x3?x4?30有多少满足x1?2，x2?0，x3??5，x4?8的整数解？ 解 进行变量代换：
y1?x1?2，y2?x2，y3?x3?5，y4?x4?8
则方程变为
y1?y2?y3?y4?25
原方程满足条件的解的个数等于新方程的非负整数解的个数。新方程的非负整数解的个数为
?25?4?1??28??28?28?27?26??3276 ?25?????25?????3???3!??????5．用四种颜色（红、蓝、绿、黄）涂染四台仪器A,B,C和D。规定每台仪器只能用一种颜
色并任意两台仪器都不能相同。如果B不允许用蓝色和红色，C不允许用蓝色和绿色，D不允许用绿色和黄色，问有多上种染色方案？
6．一个学生有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小时。
7．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}中的不同整数，则|Ai1???Aik|?(7?k)!。
i?1 ?Ai|?1。因此，
8?8??8??8??8??8??8??8?|A1???A8|?7!???1??6!???2??5!???3??4!???4??3!???5??2!???6??1!???7??0!?1?1625
??????????????她们可以有1625种方法改变座位。
8．把2n?1个苹果送给3个孩子，若使得任意两个孩子得到的苹果总数大于另一个孩子的苹果树，问有多少种分法？