作业1
1. 设想一个监狱有64个囚室组成，这些囚室排列得象一张8X8的棋盘。所有相邻的囚室
之间都有门相通。一个被囚在某个角上囚室中的犯人被告知，如果他能够恰好通过每个囚室一次而到达对角位置上的囚室，他就将被释放。问：该犯人能否得到自由？ 2. 构造一个6阶幻方。
3. 证明3阶幻方必然在中心位置有一个5。试推导：恰好存在8个3阶幻方。
4. 各堆大小分别为22，19，14和11的4-堆Nim取子游戏是平衡的还是非平衡的？游戏
人I的第一次取子方式是从大小为19的堆中取走6枚硬币，游戏人II的第一次取子方式是什么？
5. 一局游戏在两个游戏人之间如下交替进行：游戏从一空堆开始。当轮到一个游戏人时，
他可以往该堆中加进1，2，3或4枚硬币。往堆中加进第100枚硬币的游戏人为得胜者。确定在这局游戏中是游戏人I还是游戏人II能够确保获胜。获胜的策略是什么？
作业2
1． 证明：有理数m/n展开的十进制小数最终是要循环的。
2． 一个学生有37天用来准备考试。根据过去经验，她知道她需要不超过60小时的学习时
间。她还希望每天至少学习1小时。证明，无论她如何安排学习时间（假设每天的学习时间都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13个小时。 3． 证明，从边长为2的正方形中任选5个点，它们当中存在2个点，这2点的距离至多为
根号2。
4． 有一个100人的聚会。每个人都有偶数个（可能是0个）熟人。证明，在这次聚会上存
在3个人有相同个数的熟人。
5． 确定一副牌中（52张）下列类型的一手牌（5张）的数目。
(1) full house（3张一样大小的牌及2张相同点数的另外的牌） (2) 顺牌（5张点数相连的牌） (3) 同花（5张一样花色的牌）
(4) 同花顺（5张点数相连的同样花色的牌） (5) 恰好两个对 (6) 恰好一个对
6． 15人围坐一个圆桌。如果B拒绝挨着A坐，有多少种围坐方式？如果B只拒绝坐在A
的右侧，又有多少种围坐方式？
7． 给定8个车，其中5个红车，3个蓝车。
(1) 将8个车放在8X8棋盘上，使没有两个车可以互相攻击的摆放方法有多少？ (2) 将8个车放在12X12棋盘上，使没有两个车可以互相攻击的摆放方法有多少？
作业3
1. 有20根完全相同的棍列成一行，占据20个位置。要从中选出6根。
(1) 有多少种选择？
(2) 如果所选出的棍中没有两根是相连的，那么又有多少种选择？ (3) 如果在每一对所选的棍之间必须至少有两根棍，有多少种选择？ 2. 将10罐橘子汁、1罐柠檬汁和1罐酸橙汁分发给4位学生，并要求每位学生至少得到一
罐饮料，并且柠檬汁和酸橙汁要分给不同的学生，确定分发的方法数。
3. 证明{1,2,…,n}的排列的逆序的最大个数等于n(n-1)/2。确定具有n(n-1)/2个逆序的唯一
的排列。再确定所有那些具有n(n-1)/2-1个逆序的排列。
4. {1,2,...,n}的r组合A的补是{1,2,...,n}的(n-r)组合A’，它由所有不属于A的元素组成。令
M=????为{1,2,...,n}的r组合的个数和(n-r)组合的个数。证明：如果A1,A2,...,AM是字典序中的r组合，那么A’M,..., A’2,A’1是字典序中(n-r)组合。
5. 用组合学推理证明恒等式??k?????k?????k?1?????k?1?????k?1??
??????????（提示：令S是三个互异元素a,b,c的集合，并计算S的某些k组合）
6. 通过对n用归纳法证明，对n是正整数，
?n?k?1?k????k??zn(1?Z)??k?01??n??r??n??n?3??n?1??n?2??n?3?|z|?1，假设
?1??zk1?Zk?0|z|?1成立
7. 用牛顿二项式定理近似计算30。
8. 现有6个巧克力的面包圈，6个肉桂的面包圈和3个素的面包圈，要配成含12个面包圈
的盒装，问有几种装法？
9. 在一次聚会上，7位男士将他们的帽子上交检查。有多少种方法使得这些帽子被返还时
分别满足下列条件？
(1) 没有男士收到他自己的帽子；
(2) 至少有一位男士收到他自己的帽子； (3) 至少有两位男士收到他们自己的帽子。 10. 证明Dn是偶数当且仅当n是奇数。
作业4
1． 确定方程x1+x2+x3+x4=20满足1≤x1≤6, 0≤x2≤7, 4≤x3≤8, 2≤x4≤6的整数解个
数。
2． 把6个非攻击型车放到具有下图所示禁止位置的6X6棋盘上的方法数是多少？
X X X X X X X X
3． 用红、白和蓝色对1Xn棋盘方格涂色。设hn是没有两个涂成红色的方格相邻的着色方
法数。求出hn所满足的递推关系，然后找出hn的公式。
4． 求解非齐次递推关系hn=6hn-1-9hn-2+2n h0=1,h1=0
5． 在同一平面上画一个圆及n条直线，每条直线均与其他直线在圆内相交。若没有三条以
上直线共点的情形，则这些直线将圆的内部分成几块区域？ 6． 利用生成函数求解下列递推关系：
(1) hn=4hn-2, h0=0,h1=1
(2) hn=hn-1+9hn-2-9hn-3, h0=0,h1=1,h2=2
7． 由0，1，2，3组成的长度为n的序列中，含偶数个0的序列个数记为hn，求hn的递推
关系。
作业5
1． 令hn表示用红、白、蓝和绿色以下述方式给1Xn棋盘上方格涂色的方法数，其中涂成
红色的方格数为偶数，涂成白色的方格数为奇数。确定序列h0,h1,...,hn,...的指数生成函数，并求出hn。
2． 由字母a,b.c,d,e组成的总字母数为n的单词中，要求a与b的个数之和为偶数，问这样
的单词有多少个？
3． 在圆上选择2n个等间隔的点。证明将这些点成对连接起来使得所得到的n条线段不相
交的方法数等于第n个Catalan数。
4． 序列的一般项hn是n的一个3次多项式。如果其差分表的第0行的前4个数是1，-1，
3，10，确定hn，并计算?hk的公式。
k?0n5． 试证明序列h0,h1,...,hn,...的下列k阶差分的公式为?hn??(?1)k?j????hn?j
kj?0k?k??j?6． 证明第二类stirling数满足下列关系 （1）S(n,2)?2n?1?1n?2 （2）S(n,n?1)?????n?1
?n??2?作业6
1． 确定下列每个分拆的共轭分拆
(1) 12=5+4+2+1 (2) 15=6+4+3+1+1
2． 4X5的棋盘，其禁止位置如图所示。
(1) 找出非攻击型车的最多个数，请给出一实例；
(2) 如果用1X2的多米诺骨牌来覆盖，其最大覆盖个数是多少？请给出一实例。
X X
X X X X X
组合数学作业.
