纸币折心-如何开公司

习题一（排列与组合）
1．在1到9999之间，有多少个每位上数字全不
相同而且由奇数构成的整数？
2．比5400小并具有下列性质的正整数有多少个？
排交错开来，试求从某一特定引擎开始点火
有多少种方案？
15．试求从1到1 000 000的整数中，0出现了几
次？
（1）每位的数字全不同；
（2）每位数字不同且不出现数字2与7；
3．一教室有两排，每排8个座位，今有14名学
生，问按下列不同的方式入座，各有多少种做
法？
（1）规定某5人总坐在前排，某4人总坐在后
排，但每人具体座位不指定；
（2）要求前排至少坐5人，后排至少坐4人。
4．一位学者要在一周内安排50个小时的工作时
间，而且每天至少工作5小时，
问共有多少种安排方案？
5．若某两人拒绝相邻而坐，问12个人围圆周就
坐有多少种方式？
6．有15名选 手，其中5名只能打后卫，8名只能
打前锋，2名只能打前锋或后卫，今欲选出11
人组成一支 球队，而且需要7人打前锋，4人
打后卫，试问有多少种选法？
7．求
(xy2 zw)
8
展开式中
x
2
y
2
z
2
w
2
项的系
数。
8．求
(xyz)
4
的展开式。
9．求
(x
36
1
x
2
x
3
x
4
x
5
)
10
展开式中
x
2
x
3
x
4
的
系数。
10．试证任一整数n可唯一表示成如下形式：

n

a
i
i!,0a
i
i,i1,2,< br>
i1
11．证明
nC(n1,r)(r1)C(n,r1)
，并给出
组合意义。
12．证明

n
kC(n,k)n
n
2
1
。
k1
13．有n个不同的整数，从中取出两组来，要求
第一组数里的最小数大于第二组的最大 数，
问有多少种方案？
14．六个引擎分列两排，要求引擎的点火次序两

16．n个男n个女排成一男女相间的队伍，试问有
多少种不同的方案？
17．n个完全一样的球，放到r个有标志的盒子，
nr
，要求无一空盒，
试证其方案数为


n1


r1

。

18．设
np


1
1
p< br>2
2
p
k
k
，
p
1
,p
2
,,p
k
是k个
素数，
试求能整除尽数n的正整数数目。
19．试求n个完全一样的骰子能掷出多少种不同
的方案？
20．凸十边形的任意三 个对角线不共点，试求这
凸十边形的对角线交于多少个点？又把所有
的对角线分割成多少段？
21．试证一整数n是另一整数的平方的充要条件
是除尽n的正整数的数目为奇数。
22．统计力学需要计算r个质点放到n个盒子里去，
并分别服从下列假定之一，问有多少种不同
的图像？假设盒子始终是不同的。
（1）Maxwell- Boltzmann假定：r个质点是不
同的，任何盒子可以放任意个；
（2）Bose-Einstein假定：r个质点完全相同，
每一个盒子可以放任意个。
（3）Fermi-Dirac假定：r个质点都完全相同，
每盒不得超过一个。
23．从26个英文字母中取出6个字母组成一字，
若其中有2或3个母音，
问分别可构成多少个字（不允许重复）？
24．给出


n


r





n1


r1



n2

r2




nm

r

m< br>
0

m1

1


< br>
m2


2



0

m


m





nr1


m


的组合意义。
25．给出
1


r

r1
 
r2







rrr

的组合意义。
26．

n

n1






r

r1

证明
32．由n个0及n个1组成的字符串，其任意前k
个字 符中，0的个数不少于1的个数的字符串有多
少？


m
m




m1

m





m


m


n
n
习题二（母函数及其应用）

m
2

0

n

1

n1

n

0

。
27．对于给定的正整数n， 证明在所有
C(n,r)(r1,2,
中，当
n,


n1
,
n1
,n为奇数

k



22
n
时，


2
，n为偶数
C(n,r)
取得最大值。
28．（1）用组合方法证明
(2n)!
2
n
和
(3n)!
2
n
3
n
都
是整数。
（2）证明
(n
2
)!
(n!)
n1
是整数。
29．（1）在2n个球中，有n个相同，求从这2n
个球中选取n个的方案数。
（2）在
3n1
个球中，有n个相同，求从这
3n1
个球中选取n个的方 案数。
30．证明在由字母表
{0,1,2}
生成的长度为n的字
符串中，
（1）0出现偶数次的字符串有
3
n

1
2
个；
（2）


n

n

0


n

n2

2


2


2


n

nq
3
n
1

q


2 
2
，
其中
q2


n


2


。
31．5台教学仪器供m个学生使用，要求使用第1
台和第2台的人数相等，
有多少种分配方案？

1

．求下列数列的母函数
n
(n0,1,2,)

（1）


(1)< br>n



a


n

< br>

；

（2）
{n5}
；
（3）
{n(n1)}
；
（4）
{n(n2)}

2 ．证明序列
C(n,n),C(n1,n),C(n2,n),
的
母函数为
1
(1x
n
)
1
。
3．设
S{ e
1
,e
2
,e
3
,e
4
}，求序列
{a
n
}
的母函数。
其中，
a
n
是S的满足下列条件的n组合数。
（1）S的每个元素都出现奇数次；
（2）S的每个元素都出现3的倍数次；
（3）
e
1
不出现，
e
2
至多出现一次；
（4）
e
1
只出现1、3或11次，
e
2
只出现2、4< br>或5次；
（5）S的每个元素至少出现10次。
4．投掷两个骰子，点数之和为r
(2r12)
，其
组合数是多少？
5．投掷4个骰子，其点数之和为12的组合数是
多少？
6．红、黄、蓝三色的球各 8个，从中取出9个，
要求每种颜色的球至少一个，问有多少种不同
的取法？
7．将币值为2角的人民币，兑换成硬币（壹分、
贰分和伍分）可有多少种兑换方法？
8．有1克重砝码2枚，2克重砝码3枚，5克重
砝码3枚，要求这8个砝码只许放在天平的一
端，能称几种重量的物品？有多少种不同的称
2

法？
9．证明不 定方程
x
1
x
2

拆数等于n分拆为奇数之和的分拆数。
x
n
r
的正整数解17．求自然数50的分拆总数，要求分拆的每个分< br>项不超过3。

习题三（递推关系）
组的个数为
C(r1,n1)
。
10．求方程
xyz24
的大于1的整数解的个
数。
11． 设
a
n


(C
k0
n
n,
，
2k
1．解下列递推关系：
)k
其中
a
0
1
，
b
n


C(nk,2k1)
，
b
0
0
。
n

a
n
7a
n1
10a
n2
0
（1）


a0,a1
1

0
k0
试证：
（1 ）
a
n1
a
n
b
n1
，
b
n1
a
n
b
n
；
（2）求出
{a
n
}
、
{b
n
}
的母函数
A(x)
，
B(x)
。
12．设
S{e
1
,e
2
,,e
k
}
，求序列
{p
n
}
的母函数 ，
其中
p
n
是S的满足下列条件的n排列数：
（1）S的每个元素都出现奇数次；
（2）S的每个元素至少出现4次；
（3）
e
i
至少出现i次
(i1,2,,k)
；
（4）
e
i
至多出现i次
(i1,2,,k)
；
13．把23本书分给甲乙丙丁四人，要求这四个人
得到的书的数量分别不超过9本、8本、7本、< br>6本，问：
（1）若23本书相同，有多少种不同的分法？
（2）若23本书都不相同，又有多少种不同的
分法？
14．8台计算机分给3个单 位，第一个单位的分配
量不超过3台，第二个单位不超过4台，第
三个单位不超过5台，问共有 几种分配方案？
15．用母函数证明下列等式成立：
222
（1）


n

n


0





1





n
2n

n



n

；

（2）


n




n1





nm
nm1



n

n

n





n1

。

16．证明自然数n分拆为互异的正整数之和的分

（2）


a
n
6a
n1
9a
n2
0
1< br>

a
0
0,a
1

（3）
< br>
a
n
a
n2
0

a
00,a
1
2

（4）


a
n< br>2a
n1
a
n2

a

0
a
1
1
（5）


a
n
a
n1
9a
n2
9a
n3


a
0
0,a
1
1,a
2
2
2．求由A，B，C，D组成 的允许重复的排列中
AB至少出现一次的排列数。
3．求n位二进制数中相邻两位不出现11的数的个
数。
4．利用递推关系求下列和：
n
（1）
S
2
n


k

k0
n
（2）
S
n


k(k1)

k0
n
（3）
S
n


k(k2)

k0< br>n
（4）
S
n


k(k1)(k2)

k0
5．求n位四进制数中2和3必须出现偶数次的数
目。
6．试求由a，b，c三个字母组成的n位符号串中
不出现aa图像的符号串的数目。
3

7．利用递推关系解行列式：
F
1
F
2
F
3
F
4

0
0
0


(1)
n1
F
n
(1)
n1
F
n1
1
abab
1
0
0
1
0< br>0
ab
0
0
0
0
abab
16．有2n 个人在戏院售票处排队，每张戏票票价
为5角，其中n个人各有一张5角钱，另外n
个人各有一 张1元钱，售票处无零钱可换。
现将这2n个人看成一个序列，从第一个人开
始，任何部分子序 列内，都保证有5角钱的
人不比有1元钱的人少，则售票工作能依次
序进行，否则，只能中断， 而请后面有5角
钱的人先上来买票。前一种情况，售票工作
能顺利进行，对应的序列称为依次可 进行的。
问有多少种这样的序列？
17．用
a
n
表示具有整数边长且周长为n的三角形
的个数，证明

1ab
8．在
nm
方格的棋盘上， 放有k枚相同的车，
设任意两枚不能相互吃掉的放法数为
F
k
(n,m)，证明
F
k
(n,m)
满足递推关系：
F
k
(n,m)F
k
(n1,m)(mk1)F
k1
(n1,m)

9．在
nn
方格的棋盘中，令
g(n)
表示棋盘里正< br>方形的个数（不同的正方形可以叠交），试建
立
g(n)
满足的递推关系。 < br>10．过一个球的中心做n个平面，其中无3个平
面过同一直径，问这些平面可把球的内部分成< br>多少个两两无公共部分的区域？
11．设空间的n个平面两两相交，每3个平面有且
仅 有一个公共点，任意4个平面都不共点，这
样的n个平面把空间分割成多少个不重叠的区
域？
12．相邻位不同为0的n位二进制数中一共出现
了多少个0？
13．平面上有两两相交，无3线共点的n条直线，
试求这n条直线把平面分成多少个区域？
14．证明Fibonacci数列的性质，当
n1
时，
n
（1）
F
n
2
1
F
n
F
n2
(1)


a
n3

n1
a
n


n(1)
2

a
n3

4
的个数是
当n是偶数

当n是奇数
18．（1）证明边长为 整数且最大边长为r的三角形

1
r(r2)


4


1
(r1)
2
4
当r是偶数

当r是奇数
（2）设
fn
为边长不超过
2n
的三角形的个数，
g
n
为边长不超 过
2n1
的三角形的个
数，求
f
n
和
g
n
的解析表达式。
19．从1到n的自然数中选取k个不同且不相邻
的整数，
设此选取的方案数为
f(n,k)
。
（1）求
f(n,k)
的递推关系及其解析表达式；
（2）将1与n也算作 相邻的数，对应的选取
方案数记作
g(n,k)
，利用
f(n,k)
求
（2）
F
1
F
2
F
2
F
3

（3）
F
1
F
2
F
2F
3

（
F
2n1
F
2n
F< br>2
2
n

F
2n
F
2n1
F
2
2
n1
1

4）
nF
1
(n1)F
2


15．证明：
（1）
n
2F
n1
F
n
F
n4
(n3)
当
n2
1
时，
g(n,k)
。
20．球面上有n个大圆，其中任何两个圆都相交
于两点，但没有 三个大圆通过同一点，用
a
n
表
示这些大圆所形成的区域数，例如，
4
F
1
2

（

F
2
2

2
F
2
n

F
n
当
F
时，）
n4

a
0< br>1,a
1
2
，试证明：
（1）
a
n1
a
n
2n
；
（2）
a
n
n
2
n2

21．（1）试计算 从平面坐标点
O(0,0)
到
A(n,n)
点
在对角线OA之上但可 以经过OA上的点
的递增路径的条数。
（2）试证明从平面坐标上
O(0,0 )
点到
A(n,n)
点在对角线OA之上且不触及
OA的递增路径的条数是
1

2n
2(2n1



)
n


。
22．有多少个长度为n的0与1串，在这些串中，
既不包含子串010，也不包含子串101？
第二版新增的部分习题

7．求由0，1，2，3作成的含有偶数个2的n可
重排列的个数。
24．设把2n 个人分成n个组且每组恰好有2个人
的不同分组方法有
a
n
种，请给出
a
n
满足的递推关
系并求解。

习题四（容斥原理）
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)D
n
。
9．n个单位各派两名代表出席一个会议，2n位代
表围圆桌而坐，试问：
（1）同一单位的代表相邻而坐的方案数是多
少？
（2）同一单位的代表互不相邻的方案数又是多
少？
10．一书架有m层，分别放置m类不同 种类的书，
每层n册，现将书架上的图书全部取出整理，
整理过程中要求同一类的书仍然放在同 一
层，但可以打乱顺序，试问：
（1）m类书全不在各自原来层次上的方案数
是多少？
（2）每层的n本书都不在原来位置上的方案
数是多少？
（3）m层书都不在原来层次，每层n本书也
不在原来位置上的方案数又是多少？
11．证明错排数的下列性质（
n2
）：
（1）
D< br>n
(n1)(D
n2
D
n1
)

（2）
DnD
n
n

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
m
2
(m1)
， 试
证其中必有两个盒子有相同的球数。
8．设有三个7位二进制数：
(a
1
a
2
a
3
a
4
a
5
a
6
a
7
)
、
(bb
12
b
3
b4
b
5
b
6
b
7
)
和
(c< br>1
c
2
c
3
c
4
c
5
c< br>6
c
7
)
，试证存在
整数i和j，
1ij7< br>，使得下列等式中至
少有一个成立：

a
i
a< br>j
b
i
b
j
，
b
i
b
j
c
i
c
j
，
c
i
c
j
a
i
a
j

9．证明：把1～10这10个数随机地写 成一个圆
圈，则必有某3个相邻数之和大于或等

于17。若改为1～26，则相邻数之和应
大于或等于41。
10．某学生准备恰好 用11个星期时间做完数学复
习题，每天至少做一题，一个星期最多做12
题，试证必有连续几 天内该学生共做了21道
题。
11．
(m1)
行
(mC
2
m1
1)
列的格子用m种颜色着
色，每格着一种色，证明其中必有一个 4角
的格子同色的矩形。
12．证明：（1）平面上任取5个整点（坐标为整
数的点），其中至少有两个点，
由它们所连线段的中点也是整
点。
（2）从三维空间任取9个整点中至少
有两个点，其连线的中点为整点。
13．在平面直角坐 标系中至少任取多少个整点，
才能保证其中存在3个点构成的三角形的重
心是整点。
第二版新增部分习题：
11．求证在任意给的11个整数中，一定存在6个
整数，它们的和是6的倍数。
12．证明任意给定的52个整数中，总存在两个数
它们的和或差能被100整除。
13．证明：（1）每年至少有一个13日是星期五。
（2）每年至多有三个13日是星期五。
14．设
a
1
,a
2,,a
n
是整数
1,2,,n
的任意一个排
列，证明：当n是奇 数时，乘积
(a
1
1)(a
2
2)(a
n
n )
肯定是偶数。
17．在平面直角坐标系中任取5个整点（两个坐
标都是整数），证 明其中一定存在3个点，由其构
成的三角形（包含3点在一条直线上）的面积是
整数（可以为0 ）。
18．用4种颜色给平面上的完全图
K
66
（66个顶
点，每 个顶点间都有边连接）的边染色，每个边
选一种颜色。证明，染色后必存在一个同色的
K
3
（即三角形）。
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
)
1
1
(x)x
，
f
2
( x
x
，
f
3
(x)1x
，
f(x)
1
1x
，
f(x)
x1x
45
x
，
f
6
(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．试说明群
S
5
的不同格式及其个数。
16．将一正方形均分 为4个格子，用两种颜色对4
个格子着色，问能得到多少种不同的图像？其
中认为两种颜色互换 后使之一致的方案属同
一类。
17．在正四面体的每个面上都任意引一条高，有
多少种方案？
18．一幅正方形的 肖像与立方体的一个面一样大，
6幅相同的肖像贴在正立方体的6个面上有多
少种贴法？
19．（1）本质上有多少种确实是2个输入端的布
尔代数？写出其布尔表达式；
（2）本质上有多少种确实是3个输入端的布
尔电路？
20．用8个相同的骰子垛成一个正六面体，有多
少种方案？
21．正六面体的6个面和8个顶点分别用红、蓝
两种颜色的珠子嵌入。



7