组合数学习题
1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2.
从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个
整数能整除另外一个整数。
任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。
至少有两个L是一样的，则它们的差=(2i-2j)L>=2，题目应该是说差最大为2，而不是除。
2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100.
设52个整数a1，a2，…，a52被100除的余数分别是r1,r2,…,r52，而任意一个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将r1,r2,…,r52放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj，要么有ri＋rj＝100，也就是说ai－aj|100或者ai＋aj|100。
3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。
鸽子洞原理，必有两个数相邻，相邻的两个数互质
4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q).
令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。
在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有
R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为
p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤
R(p,q-1)+R(p-1,q)
5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。
从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人
若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。
若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。
6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats?
6个男的先进行圆排列，然后6个女的插入空位。
6!/6 - 6*5*4*3*2*1
圆排列：P(n,r)/r = n!/(r(n-r)!)
7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?
A．15个人进行圆排列，减去ab组成一个元素的14人的圆排列，然后减去ba 组成一个元素的14人的圆排列。
15!/15-14!/14-14!/14
B．15个人进行圆排列，减去ab组成一个元素的14人的圆排列。
14!-13!
8．Determine the number of 10-combinations of the multiset
S={∞*a,4.b,5*c,7*d}
(1+x+x2+x3+…)( 1+x+x2+…+x4) ( 1+x+x2+…+x5) ( 1+x+x2+…+x7)展开找X~10的系数
9．把n个有编号的球放入m个有编号的盒子中，不允许有空盒子，有多少种放法。
先假设，盒子没有编号，然后乘上组合与排列的关系：
)
,
(
!*
2
m
n
S
m
10．证明在n（n≥2）个人中总有两个人，他们在这群人中所认识的人数目相同。
当n＝2时，如果两个人相互认识，则每个人认识的人只有一个；如果不
认识，则每个人认识的人为0个。
当n>2时，设x i (x=1,2,…,n)表示，第i个人认识的人的数目。（每个人最
多只能认识n-1个人。）
A．如果每个人都有熟人
那么由鸽子洞原理知道至少有两个人i和j认识的人数相同即x i＝x j B．如果只有一个人没有认识的人
那么对于剩下的n－1个人来说能认识的人对多只有n－2个，由鸽
子洞原理知道，这n－1个人中至少有两个人i和j认识的人数一样
即x i＝x j
如果至少有两个人都没有熟人，则满足题设。
11．空间中有30个点，这30个点中无四个点共面，问它们能确定多少个三角形？
能确定多少个四面体？
12．从整数1，2， ，1000中选取三个数，使得它们的和是4的倍数，求这样的选法有多少种？
13．如图所示是一张城市平面图，图中的直线表示街道，直线的交点表示街道的
交叉路口，试证明从交叉路口
()
00
S，到交叉路口()
T m n
，不同的路径共有
m n
m
+
??
?
??。
S
重集B的全排列个数为n!/n1!n2!...nk! 其中n=n1+n2+..+nk
14．一个剧团演出11周，为保证收入和不至于太累，规定每天至少演出一场，每周不超过12场。证明存在连续的若干天，恰好演出21场。
设a1为第一天该剧团的演出的次数，ai表示前i天一共的演出次数。可知道ai 是单调递增的。且有a1>=1,a77<=132。于是有ai＋21(i=1,2,…,77)，也是单调递增的。而a77＋21<=153。则有（a1,a2,..a77,a1+21,a2+21,..,a77+21）这154个数在1到153之间，所以由鸽子洞原理知道，至少存在两个数ai和aj有ai ＝aj＋21即ai－aj＝21
15．任给5个整数，则必能从中选出3个，使得它们的和能被3整除。
正整数按余数分3组，0 1 2 ，5个数放入3个组中。如果一个组中有3个或者以上的整数，则取此组3数，满足题意。余下情况为:a：221，b：212，c:122三个组里面各取一个数，满足题意
16．在边长为1的正三角形中任选5个点，证明必有两个点的距离不超过1/2。
如上图所示，将这个正三角形分割成4个小的正三角形，有每个小正三
角形的边长为1/2。将5个点放入这4个小三角形内，由鸽子洞原理有一
个三角形内部有2个点，因为小三角形的边长为1/2，所以这两个点的最
大距离为1/2。
17．设a
1，a
2
，a
3
，?，a
n
是1，2，3，?，n的一个排列，证明当n是奇数时，
乘积（a
1-1）（a
2
-2）（a
3
-3）?（a
n
-n）是偶数。
假设，当n为奇数时A＝（a1-1）（a2-2）（a3-3）?（a n-n）是奇数，则：
（a i -i）均为奇数，否则A为偶数。也就是说当i为奇数时a i 必须为偶
数；因为n为奇数，所以从1到n的偶数数目为（n-1）/2，奇数数目为（n+1）/2，所以由鸽子洞原理可以知道当i为奇数时，至少有一个（a i -i）为偶数，所以A＝（a1-1）（a2-2）（a3-3）?（a n-n）是奇数。
18．有100个人的舞会，每个人的舞伴数都是偶数，证明必有3个人有相同的舞伴数。
由于每个人的舞伴数是偶数个，所以可能有的舞伴数为0，2，4，6，8，…，98。共有50种可能。
A．如果每个人都有舞伴，可能的舞伴数为2，4，…，98。共49种可能，
相当于把100个球放入49个篮子中，由鸽子洞原理知道至少有一个篮子有
3个球以上，也就是说有3个人有相同的舞伴数。
B．如果只有一个人没有舞伴，剩下的人可能的舞伴数为2，4， (98)
共49种可能，相当于把99个球放入49个篮子中，由鸽子洞原理知道至少
有一个篮子有3个球，也就是说有3个人有相同的舞伴数。
C．如果有两个人没有舞伴，剩下的人可能的舞伴数为2，4，6， (96)
共48中可能。相当于把98个球放入48个篮子中，由鸽子洞原理知道至少
6有一个篮子有3个球以上，也就是说有3个人有相同的舞伴数。
D．如果有至少3个人没有舞伴，则有3个人的舞伴数为0
19．一个学生打算用37天总共60学时自学一本书，他计划每天至少自学1学时，证明：无论他怎样安排自学时间表，必然存在相继的若干天，在这些天内其自学总时数恰好为13学时（假定每天自学学时数为整数）。
20． N 个质点排成一列，涂以红、白、黑三种色，每点涂一色，要求同色的点为
偶数，有多少种？
(1+x 2+x 4+…)3=(211
x -)3
=∑∞=-+02),13(r r
x r r C 21． 有两堆石块，每一石块的重量都小于nkg ，每一堆中的石块重量互不相同。
证明，如果两堆石块的总数不少于n ，那么总可以从两堆中分别选出一块，使两者的总重量是nkg 。
石块按重量可以分成这样几类：{1,n-1},{2,n-2},{3,n-3},…,{ }，共 个集合。
假定第一堆石头有p 块，第二堆有q 块，由题意有p+q>=n 。两堆石头关系等价，所以下面以第一堆为参照。
A ． 考虑第一堆石头都集中在k 类集合里面（除去单出来的石头外，其他石头都两两在一起）。此时如果第二堆石头里面有分布在k 类集合中的元素，则肯定有满足题意的来自两堆石头的两块石头；如果先让第二堆石头分布满在其他的 －k 个集合，因为每堆中石块重量不同，那么现在一共有n －1或n －2块石头分布在集合中，第二堆就多出了1或2个石头，那么这1或2个石头肯定是在前面的k 个集合中，所以这也有满足题意的两块石头。
B ． 如果第一堆石头分布在i （i 从k 到p ）个集合中，同样，显然第二堆石头分布满剩下的 －i 个集合，由于每堆中石块重量都不一样，所以第二堆将会多出q ＋2*i －2* 块石头，那么这些多出来的石头，肯定会分布在第一堆石头所在的i 个集合中，所以有满足题意的两块石头。
22． 在9个人中，或者有3人相互认识，或者有4人相互不认识。
N(3,4) <= N(2,4)+N(3,3) 因为N(2,4)和N(3,3)都为偶数，所以有：
N(3,4) <= N(2,4)+N(3,3)-1 = 4+6-1=9
N(a,2)=a n(3,3)=6 n(3,4)=9 n(3,5)=14
23． 在18个人中，或者有4人相互认识，或者有4人相互不认识。
N(4,4)<=N(3,4)+N(4,3)=9+9=18
24．证明当R(p，q-1)和R(p-1，q)都是偶数时，R(p，q) R(p，q-1)+R(p-1，q)-1。
25．把n个球放入k个盒子，分别考虑球有无编号，盒子有无编号，以及盒子可否空3种情况下的配置数。
A．n个球无编号，k个盒子也没有编号，允许为空
F(k,n)/K! 首先认为盒子是有编号的，然后去掉盒子的编号B．n个球无编号，k个盒子也没有编号，不允许为空：
在每个盒子中先放一个球，剩下n－k个球，任意放。
F(k,n-k)/K! 首先认为盒子是有编号的，然后去掉盒子的编号。
D．n个球无编号，k个盒子有编号，允许空
F(k,n)=C(k+n-1,n)
E ． n 个球无编号，k 个盒子有编号，不允许空
在每个盒子中先放一个球，剩下n －k 个球，任意放。
F(k,n-k)=C(n-1,n-k)
F ． n 个球有编号，k 个盒子无编号，允许空
F ．n 个球有编号，k 个盒有无编号，不允许空
S2(n,k)
G ．n 个球有编号，k 个盒有有编号，允许空
先认为盒子没有编号，然后再乘上每次取盒子的方法数。
H ．n 个球有编号，k 个盒有有编号，不允许空
先认为盒子没有编号，然后再乘上给盒子编号的方法数。
26． 将n 个元素的集合划分为非空子集，有多少种？
可能的划分成的集合数有：1，2，3，…，n 。
相当于将n 个球，分别放入以上数字的篮子中的放法，然后求和。有： ∑=n
k k n S 12
),( （球有编号的时候） ∑=n
k k n k F 1
!),( （球无序的时候） 27． 证明：如果将一个完全17角形的边用红，蓝，白三种颜色任意着色，则一定
存在一个同色的三角形。
一个点要与其他16个点连线，只有三种颜色，所以根据抽屉原理，从一点至少引出6条同色的线段.
不妨设点A 与B 、C 、D 、E 、F 、G 六点是用白色线段连接的.
如果B 、C 、D 、E 、F 、G 这六点之间有一条白线连线，那么就会出现一个三边为白色的三角形.否则，这六个点只能用红、蓝两种颜色连接了.
而平面6点，用双色涂，必然存在一个同色三角形，而用三色，和A 点会出现三角形
28． 设有重量分别为1克，2克，3克，5克，7克的5个砝码，可以称多少种不
同重量的物体。
(1+x)(1+x 2)(1+x 3)(1+x 5)(1+x 7) 展开看有多少项。
29． 有A ，B ，C ，D 四位教师和1，2，3，4四门课程，已知A 和D 不能教1和4，
B 不能教3，
C 不能教2和3。为每位教师恰好安排一门课程的方式有多少种。
30．设有多重集B=｛∞·0，∞·1，∞·2，∞·3｝，可以组成长为r， 0出现偶数次的数字串有多少个。
31．在由26个字母a，b，c， ，z组成的全排列中，求不包含字符串john，paul 和smite的全排列个数。
32．某校有120名学生参加数学竞赛，竞赛试题共有甲，乙，丙三题．竞赛结果为：12名学生三题全对；20名学生只做对了甲题和乙题；16名学生做对了甲题和丙题；28名学生做对了乙题和丙题；48名学生做对了甲题；56名学生做对了乙题；16名学生三题都做错了．试求出做对了丙题的学生人数。
33．10个人圆桌会议，休会后重新入座，每个人都不与原先的人相邻的坐法有多少种。
题目得条件时每个人都不与原先的人相邻，即是说新的圆排列中不出现123，234，345，…，(n-2)(n-1)n，(n-1)n1，n12，这些情况。
设pi表示圆排列具有i(i+1)(i+2)这一性质的，Ai表示具有pi这一性质的圆排列的集合。
n-2个元素进行圆排列 |A1| = (n-3)!，…，|Ai| = (n-3)!
对于 |A1∩A2| ＝ (n-4)!，…，|Ai∩Ai+1| ＝ (n-4)!
……
N=(n-1)! – C(n,1)(n-3)! + C(n,2)(n-5)! +…
一直到C(n,n)
34．在一个班上有n名学生，临时将这n个学生任意编号为1,2,3,…,n，当教师上课按原来的点名册点名时，如果编号为i的学生正好是第i个喊到时，就称为一次巧遇。a．求至少有一次巧遇的概率；b．求恰有m次巧遇的概率。
a．求对立面，即一次巧遇都没有。那么，1号学生选取有n-1种，取到第i号，第i号有n-2种，取到第j号，以此类推，方法数为（n-1）！总共有n！排法，故概率为（n-1）/n。
b．有m次巧遇，从n中选m有C（n，m）种，n个数全排列为n！，故。。。
不确定
35． 证明：从集合{}123S n =???，，，
，中选取k 个数，且无相邻两数，则不同的选取方法数为1n k k -+?? ???
。
36． 在r 位二进制序列里，使数字0不相邻的序列有多少个（用递推方程）？
37． 有张、王、刘、李四位教师和数学、物理、化学、英语四门课程．已知张和
李都不能教数学和英语，王不能教化学，刘不能教物理和化学．若要为每人安排一门他能教的课程，且一门课程只能被一人教，试问有多少种不同的安排方案？
38．有两颗骰子，每个骰子六个面上刻有1，2，3，4，5，6个点．问掷骰子后，点数之和为r，两颗骰子的点数有多少种搭配方式？
39．求由数字2，3，4，5，6，7组成的r位数中，3和5都出现偶数次，2和4至少出现一次的r位数的个数。
40．有无穷多个字母A，B和C．求从中选出n个字母但必须包含偶数个A的方式数。
=(n+2)(n+1)/2+(n+1)/4+1/8+(-1)n/8
a
n
41．对1×n棋盘的每个正方形用红或蓝两种颜色之一着色．设an表示没有任何两个着红色的正方形是相邻的着色的方式数．求an所满足的递归关系并解之。
42．如果用an表示没有两个0相邻的n位三元序列（即由0，1，2组成的序列）的个数．求an所满足的递归关系并解之。
43．某人有n元钱，她每天要去菜市场买一次菜，每次买菜的品种很单调，或者买一元钱的蔬菜，或者买两元钱的猪肉，或者买两元钱的鱼．问，她有多少种不同的方式花完这n元钱?
44．求解递推方程
①f(n)=af(n/b)+Cn n>1
f(1)=C n=1
设n=b k ,C 为常数,a 、b 为正整数
① f(n)=2f(n/2)+C n>1
f(1)=C n=1
设n=2k ,C 为常数
f(n)=2f(n/2)+C
2f(n/2)=4f(n/4)+2C
4f(n/4)=8f(n/8)+4C
…
2k-1(n/2k-1)=2k f(n/2k )+2k-1C
将上面的各等式，左右相加得：
f(n)=C+2C+…+2k-1C+2k f(n/2k )= C+2C+…+2k-1C+2k C
=∑=k i i C 0
2*=C*(2K ＋1-1)
② H(n)=4H(n-1)-4H(n-2) n>1
H(0)=0，H(1)=1
特征方程为x 2-4x+4=0
解为二重根：q 1=q 2=2
通解表示为：H n =C 1*2n +C 2*n2n
由H(0)=0，H(1)=1有：
C 1+0*C 2=0
C 1*2+C 2*2=1
解得:C 1=0 C 2=1/2
H n =n*2n-1
45． Kn=
E=E 1∪E 2，E 1∩E 2=Φ。 证明n>11,若G 1是平面图，则G 2不是。证明G 1和G 2必有一个是连通图。
1、假设G 2也是平面图。那么有e 1<=3n-6,e 2<=3n-6，所以有e<=2(3n-6)。
因为Kn 是完全图所以有e ＝n*(n-1)/2，所以有n*(n-1)/2<=2(3n-6)，
n 2-13n+24<=0，满足不等式得n 得取值为：2～10，所以当n>11时，不等式不成立，所以当n>11时，由假设得出得结论是不成立得，所以假设不成立，所以若G1为平面图，G2肯定不是平面图。
化简得：
2、假设两个图都不是连通图。有e 1<=n-2和e 2<=n-2成立从而有
e<=2(n-2)。
因为Kn 是完全图所以有e=n*(n-1)/2，所以有n*(n-1)/2<=2n-4，解得n 2－5n ＋8<=0。但是n 2－5n ＋8=(n-5/2)2+7/4>0，所以矛盾，所以必有一个图是连通图。
46． Let G be a planar graph of order n in which every vertex has the same
degree k. Prove that k ≤5.
（∑∑==e v d r d i 2)()(,e<=3n-6,n-e+r=2,2e>=3r ）
所有点度的和应该是边数的2倍，即∑=e v d 2)(。由题意由G 的∑=nk v d )(，
那么由nk ＝2e ，对于平面图我们有e<=3n-6，所以有nk<=6n －12，k<=6-12/n ，因为k 为整数，所以有k<=5。
47． Let G be an undirected graph. Prove that κ(G)≤λ(G)≤δ(G).
κ(G): vertex-connectivity,λ(G):edge-connectivity,
δ(G): the smallest degree of a vertex of G.
若G 不连通，则K(G)=λ(G)＝δ(G)=0，则κ(G)≤λ(G)≤δ(G)成立。 若G 连通
证λ(G)≤δ(G)：
假定λ(G)>δ(G)。设a 点时G 中度最小的点，那么δ(G)就是与a 相连的边数，将与a 相连的边全部去掉，那么G 就不在连通，所以λ(G)>δ(G)是不可能成立的。所以有λ(G)≤δ(G)。
证κ(G)≤λ(G)：
若λ(G)＝1，即只需要去掉一条边G 就不在连通，此时记这条边为e 这条边的两个端点记为V1和V2，则e 是这个图的桥，此时有κ(G)＝1，所以κ(G)≤λ(G)成立。
若λ(G)>=2，此时若去掉λ(G)条边G 就不连通了，如果只去掉λ(G)－1条边，则会产生一个桥e ＝(u,v)。对于λ(G)－1条边中的每一条边，都删去一个不同于u ，v 的点，则至少删去λ(G)－1条边。若这样产生的图是不连通的则有κ(G)≤λ(G)－1<λ(G)；若仍连通则产生桥e ＝(u,v)，删去u 或者v G 也不在连通，此时κ(G)<= λ(G).
48． 31. Prove that a connected graph with a bridge does not have a Hamilton
cycle.
习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。
任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。
一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。
第一章： 1.2. 求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。 解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。 1.4. 10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？ 解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。故两人坐在一起的方式数共有2*9！，于是两人不坐在一 起的方式共有 10！- 2*9！。 1.5. 10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？ 解：这是一组圆排列问题，10个人围圆就坐共有10 ! 10 种方式。 两人坐在一起的方式数为9 ! 92? ,故两人不坐在一起的方式数为：9！-2*8！。 1.14. 求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？ 解：(1)在1到9999中考虑，不是4位数的整数前面补足0， 例如235写成0235,则问题就变为求： x 1+x 2+x 3+x 4=5 的非负整数解的个数，故有 F （4，5）=??? ? ??-+=515456 (2)分为求： x 1+x 2+x 3+x 4=4 的非负整数解，其个数为F （4，4）=35 x 1+x 2+x 3+x 4=3 的非负整数解，其个数为F （4，3）=20 x 1+x 2+x 3+x 4=2 的非负整数解，其个数为F （4，2）=10 x 1+x 2+x 3+x 4=1 的非负整数解，其个数为F （4，1）=4 x 1+x 2+x 3+x 4=0 的非负整数解，其个数为F （4，0）=1 将它们相加即得， F （4，4）+F （4，3）+F （4，2）+F （4，1）+F （4，0）=70。 第二章： 2.3. 在边长为1的正三角形内任意放置5个点，则其中至少有两个点的距离≤1/2。 解：将边为1的正三角形分成边是为1/2的四个小正三角形，将5个点放入四个小正三角形中，由鸽笼原理知，至少有一个小正三角形中放有2个点，而这两点的距离≤1/2。 1/2 1/2 1/2
填空题 1．将 5 封信投入 3 个邮筒，有 _____243_种不同的投法． 2． 5 个男孩和 4 个女孩站成一排。如果没有两个女孩相邻，有43200方法． 3． 22 件产品中有 2 件次品，任取 3 件，恰有一件次品方式数为__ 380 ______． 4．( x y)6所有项的系数和是_64_ _．答案：645．不定方程 x1x2x3 2 的非负整数解的个数为 _ 6 ___． 6 ．由初始条件 f (0)1, f (1) 1 及递推关系 f ( n2) f (n1) f ( n) 确定的数列{ f (n)} ( n0) 叫做Fibonacci数列 10 7．（ 3x-2y ）20的展开式中 x10y10的系数是c20310( 2)10． 8．求 6 的 4 拆分数P4(6)2． 9．已知在Fibonacci数列中，已知 f (3)3,f (4)5, f (5) 8 ，试求Fibonacci 数f (20)10946 10 ．计算P4(12) 4 P4 (12)P k (12)P1 (8)P2 (8)P3 (8)P4 (8) k1 34 P1 (8) P2 (8)P k (5)P k (4)14 5 515 k1k 1 11．P4(9)（ D） A． 5 B. 8 C. 10 D. 6 12．选择题 1．集合 A{ a1 , a 2 ,L , a10 } 的非空真子集的个数为（A） C. 1024 2．把某英语兴趣班分为两个小组，甲组有 2 名男同学， 5 名女同学；乙组有 3 名男同学， 6名女同学，从甲乙两组均选出 3 名同学来比赛，则选出的 6 人中恰有 1 名男同学的方式数是（ D ） A． 800 B. 780 C. 900 D.850 3．设( x , y) 满足条件x y10 ，则有序正整数对( x, y) 的个数为（D） A. 100 C. 50 4．求( x03x12x2x3 )6中 x02 x13 x2项的系数是（C） B. 60 5．多项式(2 x0x14x2x3 )4中项 x02x12x2的系数是（C） A． 78 B. 104 C. 96 D. 48 6．有 4 个相同的红球， 5 个相同的白球，那么这9 个球有（ B）种不同的排列方式 A. 63 B. 126 C. 252 7．递推关系 f (n ) 4 f ( n1) 4 f (n 2) 的特种方程有重根2，则（ B ）是它的一般解 A．c12n 1c2 2n B.(c1c2n)2 n C.c(1n)2 n D.c1 2n c2 2n 8．用数字 1,2,3,4（数字可重复使用）可组成多少个含奇数个1、偶数个 2 且至少含有一个 3 的n (n1) 位数（）运用指数生产定理 A. 4n 3n ( 1)n B.4n3n14n2n 1 .4n3n( 1)n 4433
作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明：
第四章 生成函数 1. 求下列数列的生成函数： （1）{0,1,16,81,…,n 4,…} 解：G{k 4 }= 235 (11111) 1x x x x x +++-（） （2）343,,,333n +?????????? ? ? ????? ???? 解：3n G n +?????? ?????=4 1(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=2 1 1x -. （4）{1,k ,k 2,k 3,…} 解：A(x)=1+kx+k 2x 2+k 3x 3+…= 1 1kx -. 2. 求下列和式： （1）14+24+…+n 4 解：由上面第一题可知，{n 4}生成函数为 A(x)=235 (11111)1x x x x x +++-（）=0 k k k a x ∞=∑， 此处a k =k 4 .令b n =14 +24 +…+n 4 ，则b n =0n k k a =∑，由性质3即得数列{b n }的生 成函数为 B(x)= 0n n n b x ∞ =∑=() 1A x x -=34 125(1111)i i i x x x x x i ∞ =++++?? ??? ∑. 比较等式两边x n 的系数，便得 14+24+…+n 4 =b n =1525354511111234n n n n n n n n -+-+-+-++++----???????? ? ? ? ? ???????? 321 (1)(691)30 n n n n n =+++- （2）1·2+2·3+…+n (n +1) 解：{ n (n +1)}的生成函数为A(x)= 3 2(1)x x -=0 k k k a x ∞ =∑，此处a k = n (n +1). 令b n =1·2+2·3+…+n (n +1)，则b n =0 n k k a =∑.由性质3即得数列{b n }的生成 函数为B(x)= n n n b x ∞ =∑= () 1A x x -= 4 2(1)x x -=032n k k k x x k =+?? ?? ?∑. 比较等式两边x n 的系数，便得
组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k
?1.证：对n 用归纳法。先证可表示性： 当n=0,1时，命题成立。 假设对小于n 的非负整数，命题成立。对于n,设k!≤n ＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立， 设n-k!=∑a i ·i!，其中a k ≤k-1,n=∑a i ·i!+k!，命题成立。i=1 k i=1 k 再证表示的唯一性： 设n=∑a i ·i!=∑b i ·i!, 不妨设a j ＞b j ,令j=max{i|a i ≠b i }a j ·j!+a j-1·(j-1)!+…+a 1·1! =b j ·j!+b j-1·(j-1)!+…+b 1·1!,(a j -b j )·j!=∑(b i -a i )·i!≥j!＞∑i·i!≥∑|b i -a i |·i!≥∑(b i -a i )·i! 另一种证法：令j=min{i|a i ≠b i }∑a i ·i!=∑b i ·i!,两边被(j+1)!除,得余数a j ·j!=b j ·j!,矛盾. i=1 k i=1k i=1 j-1i=1 j-1 i=1j-1i=1 j-1 i ≥j i ≥j ?2.证： 组合意义： 等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个； 等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。显然两种方案数相同。 nC(n-1,r) = n ————= ——————— (n-1)! (r+1)·n! r!·(n-r-1)! (r+1)·r!·(n-r-1)! = ——————= (r+1)C(n,r+1).(r+1)·n! (r+1)!·(n-r-1)! ?3.证： 设有n 个不同的小球，A 、B 两个盒子,A 盒中恰好放1个球,B 盒中可放任意个球。有两种方法放球： ①先从n 个球中取k 个球(k ≥1),再从中挑 一个放入A 盒,方案数共为∑kC(n,k),其余球放入B 盒。 ②先从n 个球中任取一球放入A 盒，剩下n-1个球每个有两种可能，要么放入B 盒， 要么不放，故方案数为n2 . 显然两种方法方案数应该一样。 k=1n n-1 ?4.解：设取的第一组数有a 个,第二组有b 个,而 要求第一组数中最小数大于第二组中最大的，即只要取出一组m 个数(设m=a+b),从大到小取a 个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m 个数中取第一组数共有m-1中取法。总的方案数为∑(m-1)C(n,m)=n ·2 +1. ?5.解：第1步从特定引擎对面的3个中取1个有 C(3,1)种取法，第2步从特定引擎一边的2个中 取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。 所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。 m=2 n n-1 ?6.解：首先所有数都用6位表示，从000000到 999999中在每位上0出现了10 次,所以0共出现 了6·10 次,0出现在最前面的次数应该从中去掉， 000000到999999中最左1位的0出现了10 次， 000000到099999中左数第2位的0出现了10 次， 000000到009999左数第3位的0出现了10 次, 000000到000999左数第4位的0出现了10 次, 000000到000099左数第5位的0出现了10 次, 000000到000009左数第6位的0出现了10 次。另外1000000的6个0应该被加上。所以0共出现了 6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。 5 5 5 4 3 2 1 5543210 ?7.解：把n 个男、n 个女分别进行全排列，然后 按乘法法则放到一起，而男女分别在前面,应该 再乘2,即方案数为2·(n!) 个. 围成一个圆桌坐下， 根据圆排列法则，方案数为2 ·(n!) /(2n)个. ?8.证：每个盒子不空，即每个盒子里至少放一 个球，因为球完全一样，问题转化为将n-r 个小球放入r 个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有C(n-r+r-1,n-r) = C(n-1,n-r)中方案。根据C(n,r)=C(n,n-r),可得 C(n-1,n-r)=C(n-1,n-1-(n-r))=C(n-1,r-1)个方案。证毕。 2 2 ?9.解：每个能整除尽数n 的正整数都可以选取每个素数p i 从0到a i 次，即每个素数有a i +1种选择，所以能整除n 的正整数数目为(a 1+1)·(a 2+1)·…·(a l +1)个。 ?10.解：相当于把n 个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。 ?11.解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。
圆梦教育中心 排列组合专项训练 1.题1 (方法对比，二星) 题面：(1)有5个插班生要分配给3所学校，每校至少分到一个，有多少种不同的分配方法？ (2)有5个数学竞赛名额要分配给3所学校，每校至少分到一个名额，有多少种不同的名额分配方法？ 解析：“名额无差别”——相同元素问题 (法1)每所学校各分一个名额后，还有2个名额待分配， 可将名额分给2所学校、1所学校，共两类： 2 1 33C C +(种) (法2——挡板法) 相邻名额间共4个空隙，插入2个挡板，共： 246C =(种) 注意：“挡板法”可用于解决待分配的元素无差别，且每 个位置至少分配一个元素的问题.(位置有差别，元素无差别) 同类题一 题面： 有10个运动员名额，分给7个班，每班至少一个,有多少种分配方案？ 答案：6 9C 详解： 因为10个名额没有差别，把它们排成一排。相邻名额之间形成9个空隙。在9个空档中选6个位置插个隔板，可把名额分成7份，对应地分给7个班级，每一种插板 方法对应一种分法共有69C 种分法。 同类题二 题面： 求方程X+Y+Z=10的正整数解的个数。 答案：36. 详解： 将10个球排成一排，球与球之间形成9个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为x 、y 、z 之值, 故解的个数为C 92=36（个）。 2.题2 (插空法，三星) 题面：某展室有9个展台，现有3件展品需要展出，要 求每件展品独自占用1个展台，并且3件展品所选用的展台既不在两端又不相邻，则不同的展出方法有______种；如果进一步要求3件展品所选用的展台之间间隔不超过两个展位，则不同的展出方法有____种. 答案：60，48 同类题一 题面： 6男4女站成一排，任何2名女生都不相邻有多少种排法？ 答案：A 66·A 47种. 详解： 任何2名女生都不相邻，则把女生插空，所以先排男生再让女生插到男生的空中，共有A 6 6·A 4 7种不同排法． 同类题二 题面： 有6个座位连成一排，现有3人就坐，则恰有两个空座位相邻的不同坐法有( ) A ．36种 B ．48种 C ．72种 D ．96种 答案：C. 详解：恰有两个空座位相邻，相当于两个空位与第三个 空位不相邻，先排三个人，然后插空，从而共A 33A 2 4＝72种排法，故选C. 3．题3 (插空法，三星) 题面：5个男生到一排12个座位上就座，两个之间至少隔一个空位． 1]没有坐人的7个位子先摆好， [2](法1——插空)每个男生占一个位子，插入7个位子所成的8个空当中，有： 58A =6720种排法. (法2)[1]5个男生先排好：55A ； [2]每个男生加上相邻的一个座位，共去掉9个位置，当作5个排好的元素，
排例组合专题训练 1． 将3个不同的小球放入4个盒子中，则不同放法种数有A ．81 B ．64 C ．12 D ．14 2．5个人排成一排,其中甲、乙两人至少有一人在两端的排法种数有 A ．33A B ．334A C ．523533A A A - D ．23113 23233A A A A A + 3．,,,,a b c d e 共5个人，从中选1名组长1名副组长，但a 不能当副组长，不同的选法总数是 A.20 B ．16 C ．10 D ．6 4．现有男、女学生共8人，从男生中选2人，从女生中选1人分别参加数学、物理、化学三科竞赛，共有90种不同方案，那么男、女生人数分别是 A ．男生2人女生6人 B ．男生3人女生5人 C ．男生5人女生3人 D ．男生6人女生2人. 5．在8 2 x ? ?的展开式中的常数项是A.7 B ．7- C ．28 D ．28- 6．5 (12)(2)x x -+的展开式中3 x 的项的系数是A.120 B ．120- C ．100 D ．100- 7．22n x ???展开式中只有第六项二项式系数最大,则展开式中的常数项是 A ．180 B ．90 C ．45 D ．360 8．由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有 A ．60个 B ．48个 C ．36个 D ． 24个 9．3张不同的电影票全部分给10个人,每人至多一张,则有不同分法的种数是 A ．1260 B ．120 C ．240 D ．720 10．n N ∈且55n <,则乘积(55)(56)(69)n n n ---L 等于 A ．5569n n A -- B ．15 69n A - C ．15 55n A - D ．14 69n A - 11．从不同号码的5双鞋中任取4只，其中恰好有1双的取法种数为 A ．120 B ．240 C ．280 D ．60 12．把10 )x -把二项式定理展开，展开式的第8项的系数是 A ．135 B ．135- C ．- D ． 13．2122n x x ??+ ?? ?的展开式中，2 x 的系数是224，则2 1x 的系数是A.14 B ．28C ．56 D ．112 14．不共面的四个定点到面α的距离都相等，这样的面α共有几个A ．3 B ．4 C ．6 D ．7
组合数学课后标准答案
————————————————————————————————作者：————————————————————————————————日期：
习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。
任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。
一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。
第一章什么是组合数学 组合学问题在生活中随处可见。例如，计算下列赛制下总的比赛次数：n个球队参赛，每队只和其他队比赛一次。创建幻方。在纸上画一个网络。用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，笔画出网络因。在玩扑克牌游戏中，计算满堂红牌的手数，以确定出现一手满堂红牌的几率。所有这些都是组合学问题。正如人们想到的．组合数学的历史渊源扎根于数学娱乐和游戏之中。过去研究过的许多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。今天，组合数学是数学的一门重要分支，而且它的影响还在继续扩大。组合数学自60年代以来急速发展的部分原因就在于计算机在我们的社会中所发挥的重要影响，而且这种影响还在继续发挥。由于运算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的。然而计算机不能独立运行，它需要编程来控制。这些程序的基础往往是求解问题的组合学算法，对于这些算法，运行时间效率和存储需求分析需要更多的组合学思想。 组合数学近期发展的另一个原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领城，而且也用于社会科学、生物科学、信息论等领域。此外，组合数学和组合学思想在许多数学分支中已经变得越来越重要。 组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。如下两类一般性问题反复出现： 排列的存在性如果有人想要排列—个集合的成员使得某些条件得以满 足，那么这样一种排列是否可行根本就不是显而易见的。这是最根本的问题。如果这种排列不总是可能的，那么我们要问，这种排列在什么样的(必要和充分)条件下能够实现？ 排列的计数和分类如果一个指定的排列是可能的，那么就会存在多种 方法去实现它。此时，人们就可以计数并将它们分类。 虽然对任何组合问题都可以考虑其存在性和计数问题，但在实践中常常发生的却是：如果存在性问题需要广泛地研究，那么计数问题则是非常困难的。然而，如果指定的排列问题的存在性容易解决，那么计算实现该排列的方法的数目则是可能的。在例外的情形下(即当它们的数目较小时)，这些排列可以被列出来，理解列出所有的排列与确定它们的数目之间的区别很重要。一旦这些排列被列出，它们就可通过与整数集{1，2，3，…，n}之间建立一一对应而被数出，其中n 是某个整数。我们计数的方法就是：1，2，3…，n。但是，我们主要关心的是事先不列出指定类型的排列而确定它们的数目的方法。当然，这些排列的总数也许很大以至于不可能把它们部列出来，概括地说，许多组合学问题常呈现下列形式：“能否排列…?” “存在一个……吗?” “能用多少方法—…?” “计算……的数目。”
一、填空题 1.如图,阴影部分的面积是 . 2 1 2 2.大圆的半径比小圆的半径长6厘米,且大圆半径是小圆半径的4倍.大圆的面积比小圆的面积大平方厘米. 3.在一个半径是 4.5厘米的圆中挖去两个直径都是2厘米的圆.剩下的图形的面积是平方厘米.(π取3.14,结果精确到1平方厘米) 4.右图中三角形是等腰直角三角形,阴影部分的面 积是 (平方厘米). 5.如图所求,圆的周长是1 6.4厘米,圆的 面积与长方形的面积正好相等.图中阴影部分 π 的周长是厘米.) 14 .3 (= 6.有八个半径为1厘米的小圆,用它们的圆周的一部分连成一个花瓣图形 π,那么花瓣图形的面积(如图).图中黑点是这些圆的圆心.如果圆周率1416 .3 = 是平方厘米.
7.已知:ABC D 是正方形, ED =DA =AF =2厘米,阴影部分的面积是 . 8.图中,扇形BAC 的面积是半圆ADB 的面积的3 11倍,那么,CAB 是 度. 9. 算出圆内正方形的面积为 . 10.右图是一个直角等腰三角形, 直角边长2厘米,图中阴影部分面积是 平方厘米 11一个扇形圆心角120,以扇形的半径为边长画一个正方形,这个正方形的面积是120平方厘米.这个扇形面积是 . 12.如图所示,以B 、C 为圆心的两个半圆的直径都是2厘米,则阴影部分的周长是 厘米.(保留两位小数)
13.三角形ABC 是直角三角形,阴影部分①的面积比阴影部分②的面积小28 长 厘米 . 积为2平方厘米,等腰直角三角形的面积 15.扇形的面积是31.4平方厘米,它所在圆的面积是157平方厘米,这个扇形的圆心角是 度. 16.图中扇形的半径OA =OB =6厘米.45=∠AOB , AC 垂直OB 于C ,那么图中阴影部分的面积是 平方厘米.)14.3(=π 17.右图中正方形周长是20厘米.图形的总面积是 平方厘米. 45
李凡长版-组合数学课后习题答案-习题3
第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17
1 第一章 排列组合 1、 在小于2000的数中，有多少个正整数含有数字2？ 解：千位数为1或0，百位数为2的正整数个数为：2*1*10*10； 千位数为1或0，百位数不为2，十位数为2的正整数个数为：2*9*1*10； 千位数为1或0，百位数和十位数皆不为2，个位数为2的正整数个数为：2*9*9*1； 故满足题意的整数个数为：2*1*10*10+2*9*1*10+2*9*9*1＝542。 2、 在所有7位01串中，同时含有“101”串和“11”串的有多少个？ 解：（1） 串中有6个1：1个0有5个位置可以插入：5种。 （2） 串中有5个1，除去0111110，个数为()6 2 -1＝14。 （或： ()()41 42 *2+＝14） （3）串中有4个1：分两种情况：①3个0单独插入，出去1010101，共()53 -1 种；②其中两个0一组，另外一个单独，则有 ()()2*)2,2(41 52 -P 种。 （4）串中有3个1：串只能为**1101**或**1011**，故共4*2种。 所以满足条件的串共48个。 3、一学生在搜索2004年1月份某领域的论文时，共找到中文的10篇，英文的12篇，德文的5篇，法文的6篇，且所有的都不相同。如果他只需要2篇，但必须是不同语言的，那么他共有多少种选择？ 解：10*12+10*5+10*6+12*5+12*6+5*6 4、设由1，2，3，4，5，6组成的各位数字互异的4位偶数共有n 个，其和为m 。求n 和m 。 解：由1，2，3，4，5，6组成的各位数字互异，且个位数字为2，4，6的偶数均有P(5,3)=60个，于是：n = 60*3 = 180。 以a 1,a 2,a 3,a 4分别表示这180个偶数的个位、十位、百位、千位数字之和，则 m = a 1+10a 2+100a 3+1000a 4。 因为个位数字为2，4，6的偶数各有60个，故 a 1 = (2+4+6)*60=720。 因为千（百，十）位数字为1，3，5的偶数各有3*P(4,2) = 36个，为2，4，6的偶数各有2*P(4,2) = 24个，故 a 2 = a 3 = a 4 = (1+3+5)*36 + (2+4+6)*24 = 612。 因此， m = 720 + 612*(10 + 100 + 1000) = 680040。 5、 从{1，2，…，7}中选出不同的5个数字组成的5位数中，1与2不相邻的数 字有多少个？ 解：1与2相邻：())4,4(253P ??。故有1和 2 但它们不相邻的方案数： ()())4,4(2)5,5(53 5 3 P P ??-? 只有1或2：())5,5(254P ?? 没有1和2：P(5,5)
组合数学试题 共 5 页 ，第 1 页 电子科技大学研究生试卷 （考试时间： 至 ，共 2 小时） 课程名称 组合数学 教师 学时 40 学分 2 教学方式 讲授 考核日期 2011 年 11 月 日 成绩 考核方式： （学生填写） 一、(共10分) 1、（4分）名词解释：广义Ramsey 数R (H 1，H 2，…，H r )。 2、（6分）证明：R(C 4,C 4) ≥ 6，其中C 4为4个顶点的无向回路图。 解： 1、使得K n 对于(H 1，H 2，…，H r )不能r －着色的最小正整数n 称为广义Ramsey 数R (H 1，H 2，…，H r )。-----------------4分 2、如下图所示的5个顶点的完全图就没有一个纯的C 4，实线和虚线分别代表不同的颜色。 -----------------4分 故R(C 4,C 4)>=6。-----------------2分 二、(16分)未来5届欧盟主席职位只能有法国、德国、意大利、西班牙、葡萄牙五国的人当选，一个国家只能当选一次。假如法国只能当选第一届、第二届或者第三届，德国不能当选第二届和第三届，意大利不能当选第一届，西班牙不能当选第五届，葡萄牙只能能当选第二届、第四届或者第五届。问未来的5届欧盟主席职位有多少种不同的当选方案？ 解：原问题可模型化为一个5元有禁位的排列. 其禁区棋盘C 如下图的阴影部分。 -----------------4分 学 号 姓 名 学 院 ……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………
组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。 任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到 2n之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a1，a2，…，a52被100除的余数分别是r1,r2,…,r52，而任意一个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将r1,r2,…,r52放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj，要么有ri＋rj ＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有 R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤ R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。 从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。 若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats? 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?
组合数学试题 共 4 页 ，第 1 页 电子科技大学研究生试卷 （考试时间： 19：30 至 21：30 ，共 2 小时） 课程名称 组合数学 教师 学时 40 学分 2 教学方式 讲授 考核日期 2007 年 11 月 27 日 成绩 考核方式： （学生填写） 一、填空题（每空3分，共27分） 1．将6本无区别的书放入3个无区别的箱子中的放法数为 7 ，又每个箱子都不为空的放法数为 3 。 2．将8个有区别的球放入6个无区别的盒子中,每个盒子不空的放法数为 266 ；将8个有区别的球放入7个无区别的盒子中, 每个盒子不空的放法数又为28 。（注：将9个有区别的球放入7个无区别的盒子中, 每个盒子不空的放法数为462）。 3．现有4个女士6个男士围圆桌就坐，则其中女士两两不相邻的入座方式数有 5!·6·5·4·3= 43200 种； 所有女士坐在一起的方式数有 6!·4!= 17280 种。 4．将单词〝motorola 〞中的所有字母作排列，其排列方式数有 8!/3!＝6720 种；其中所有〝o 〞均不相邻的排列方式数有 ???? ???36!5＝2400 种。（两问均只要求给出解的表达式，不必算出最终结果）。 5. 方程???≥≥≥=+++0,1,2123214321x x x x x x x 的整数解的个数为 F(4,9)=220 。 学 号 姓 名 学 院 …… … …… …… …密 …… …… … 封 … … … … … 线 … … … … … 以 … … … … … 内 … … … … … 答 … …… … … 题 … …… … … 无 … … … … … 效… … … …… …… …