a0?1,a1?2，试证明：
（1）an?1?an?2n； （2）an?n2?n?2
21．（1）试计算从平面坐标点O(0,0)到A(n,n)点
在对角线OA之上但可以经过OA上的点的递增路径的条数。
（2）试证明从平面坐标上O(0,0)点到
A(n,n)点在对角线OA之上且不触及
OA
的递增路径的条数是 1?2n2(2n?1???)n?? 。 22．有多少个长度为n的0与1串，在这些串中，既不包含子串010，也不包含子串101？
第二版新增的部分习题
7．求由0，1，2，3作成的含有偶数个2的n可重排列的个数。
24．设把2n个人分成n个组且每组恰好有2个人的不同分组方法有an种，请给出an满足的递推关系并求解。
习题四（容斥原理）
1．试求不超过200的正整数中素数的个数。 2．问由1到2000的整数中：
（1）至少能被2，3，5之一整除的数有多少个？ （2）至少能被2，3，5中2个数同时整除的数
有多少个？
（3）能且只能被2，3，5中1个数整除的数有
多少个？
3．求从1到500的整数中能被3和5整除但不能
被7整除的数的个数。
4．某人参加一种会议，会上有6位朋友，他和其中每一人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，
每五人各相遇2次，与六人都相遇1次，一人也没遇见的有5次。问该人共参加几次会议？ 5．n位的四进制数中，数字1，2，3各自至少出现一次的数有多少个？
6．某照相馆给n个人分别照相后，装入每人的纸袋里，问出现以下情况有多少种可能？ （1）没有任何一个人得到自己的照片； （2）至少有一人得到自己的相片；
（3）至少有两人得到自己的照片；
7．把{a,a,a,b,b,b,c,c,c}排成相同字母互不相
邻的排列，有多少种排法？ 8．把1,2,,n排成一圈，令f(n)表示没有相邻
数字恰好是自然顺序的排列数。 （1）求f(n)；
（2）证明f(n)?f(n?1)?Dn。
9．n个单位各派两名代表出席一个会议，2n位代表围圆桌而坐，试问：
（1）同一单位的代表相邻而坐的方案数是多少？
（2）同一单位的代表互不相邻的方案数又是多少？
10．一书架有m层，分别放置m类不同种类的书，
每层n册，现将书架上的图书全部取出整理，整理过程中要求同一类的书仍然放在同一层，但可以打乱顺序，试问：
（1）m类书全不在各自原来层次上的方案数是多少？
（2）每层的n本书都不在原来位置上的方案数是多少？
（3）m层书都不在原来层次，每层n本书也
不在原来位置上的方案数又是多少？
11．证明错排数的下列性质（n?2）： （1） Dn?(n?1)(Dn?2?Dn?1)
（2） DnDnn?n?1?(?1)
12．n个人参加一晚会，每人寄存一顶帽子和一把
雨伞，会后各人也是任取一顶帽子和一把雨
5
伞，问：
（1）有多少种可能使得没有人能拿到他原来的任一件物品？
（2）有多少种可能使得没有人能同时拿到他
原来的两件物品？
习题五（抽屉原理）
1．证明：在边长为2的等边三角形中任取5点，至少有两个点相距不超过1。
2．在一个边长为1的正方形内任取9个点，证明以这些点为顶点的各个三角形中，至少有一个三角形的面积不大于18。
3．把从1到326的326个正整数任意分成5组，试证明其中必有1组，该组中至少有一个数是同组中某两个数之和，或是同组中某个数的两倍。
4．任意一个由数字1，2，3组成的30位数，从中任意截取相邻的三位，证明在各种不同位置的截取中，至少有两个三位数是相同的。数的位数30还可以再减少吗？为什么？
5．任取11个整数，求证其中至少有两个数的差是10的倍数。
6．一次考试采用百分制，所有考生的总分为10101，证明如果考生人数不少于202，则必有三人得分相同。
7．将n个球放入m个盒子中，n?m2(m?1)，试证其中必有两个盒子有相同的球数。 8．设有三个7位二进制数：(a1a2a3a4a5a6a7)、
(bb12b3b4b5b6b7)和(c1c2c3c4c5c6c7)，试证存在
整数i和j，1?i?j?7，使得下列等式中至少有一个成立：
ai?aj?bi?bj，bi?bj?ci?cj，
ci?cj?ai?aj
9．证明：把1～10这10个数随机地写成一个圆
圈，则必有某3个相邻数之和大于或等
于17。若改为1～26，则相邻数之和应大于或等于41。
10．某学生准备恰好用11个星期时间做完数学复
习题，每天至少做一题，一个星期最多做12题，试证必有连续几天内该学生共做了21道题。
11．(m?1)行(mC2m?1?1)列的格子用m种颜色着色，每格着一种色，证明其中必有一个4角的格子同色的矩形。
12．证明：（1）平面上任取5个整点（坐标为整
数的点），其中至少有两个点，
由它们所连线段的中点也是整
点。
（2）从三维空间任取9个整点中至少有两个点，其连线的中点为整点。 13．在平面直角坐标系中至少任取多少个整点，
才能保证其中存在3个点构成的三角形的重心是整点。
第二版新增部分习题：
11．求证在任意给的11个整数中，一定存在6个整数，它们的和是6的倍数。
12．证明任意给定的52个整数中，总存在两个数它们的和或差能被100整除。
13．证明：（1）每年至少有一个13日是星期五。 （2）每年至多有三个13日是星期五。 14．设a1,a2,,an是整数1,2,,n的任意一个排
列，证明：当n
是奇数时，乘积
(a1?1)(a2?2)(an?n)肯定是偶数。
17．在平面直角坐标系中任取5个整点（两个坐标都是整数），证明其中一定存在3个点，由其构成的三角形（包含3点在一条直线上）的面积是整数（可以为0）。
18．用4种颜色给平面上的完全图K66（66个顶点，每个顶点间都有边连接）的边染色，每个边选一种颜色。证明，染色后必存在一个同色的K3（即三角形）。
6
习题六（Polya定理）
1． 一张卡片分成4?2个方格，每格用红蓝两色
涂染，可有多少种方法？
2．一根木棍等分成n段，用m种颜色涂染，问有
多少种染法？
3．正五角星的五个顶点各镶嵌一个宝石，若有m种颜色的宝石可供选择， 问可以有多少种方案？
4．有一个正方形木筐，用漆刷4边。现有三种不同颜色的漆，
可有多少种不同的涂法？
5．一个圆分成6个相同的扇形，分别涂以三色之一，可有多少种涂法？
6．两个变量的布尔函数f(x,y)的全体关于变量下标可以进行置换时，
其等价类的个数为多少？写出其布尔表达式。 7．红、蓝、绿三种颜色的珠子，每种充分多，取出4颗摆成一个圆环，可有多少种不同的摆法？ 8．某物质分子由5个A原子和3个B原子组成，8个原子构成一个正立方体， 问最多可能有几类分子？ 9．验证下列函数对于运算fg?f(g(x))是一
个群：
f)?11(x)?x，f2(xx，f3(x)?1?x，
f(x)?11?x，f(x)?x?1x45x，f6(x)?x?1
10．用g,r,b,y四种颜色涂染正方体的六个面，
求其中两个面用色g，两个面用色y，其余一面用b，一面用r的方案数。
11．对一正六面体的八个顶点，用y和r两种颜色染色，使其中6个顶点用色y，其余2个顶点用色r，求其方案数。
12．由b,r,g三种颜色的5颗珠子镶成圆环，共有几种不同的方案？
13．一个圆圈上有n个珠子，用n种颜色对这n个珠子着色，问所用颜色数目不少于n的着色
方案数是多少？
14．若已给两个r色的球，两个b色的球，用它装在正六面体的顶点， 试问有多少种不同的方案？ 15．试说明群S5的不同格式及其个数。 16．将一正方形均分为4个格子，用两种颜色对4个格子着色，问能得到多少种不同的图像？其中认为两种颜色互换后使之一致的方案属同一类。
17．在正四面体的每个面上都任意引一条高，有多少种方案？
18．一幅正方形的肖像与立方体的一个面一样大，6幅相同的肖像贴在正立方体的6个面上有多少种贴法？
19．（1）本质上有多少种确实是2个输入端的布尔代数？写出其布尔表达式；
（2）本质上有多少种确实是3个输入端的布尔电路？
20．用8个相同的骰子垛成一个正六面体，有多少种方案？
21．正六面体的6个面和8个顶点分别用红、蓝
两种颜色的珠子嵌入。
7
