《组合数学》测试题含答案(2)

56. 对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案？旋转或翻转使之重合的视为相同的方案。

58. 生成矩阵

1 0

G

0 0

01000010000111100111

1 1 0 1

试求相应的校验矩阵H。

59.由m个0，n个1组成的n+m位符号串，其中n≤m+1,试求不存在两个1相邻的符号串的数目。

60.n个男人与n个女人沿一圆桌坐下，问两个女人之间坐一个男人的方案数，又m个女人n个男人，且m<n，沿一圆桌坐下求无两个女人并坐的方案数。 61.求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目。 62.求满足下列条件：

x1 x2 x3 40,6 x1 15,5 x2 20,10 x3 25的整数解数目。 63.求不超过120的素数的数目。

64.试说明A4群中各置换的不同格式及其个数。 65.已知生矩阵

1 0

G

0 0

01000010000101111011

1 1 0 1

求下列信息的码字？

（a） 1110 (b) 1000 (c) 0001 (d) 1101

66.有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一组的最大数，有多少种取法？

67.设某组织有26名成员，要选一名主席，一名会计，一名秘书，且规定一人不得担任一个以上职务，问有多少种选法？ 68.从整数1，2， ，100中选取两个数。（1）使得它们的差等于7；（2）使得它们的差小于或等于7，各有多少种选取方式？ 69.有n个相同的红球和m个相同的白球；那么这m+n个球有多少种不同的排列方式？ 70.一个工厂里已装配了30辆汽车，可供选择的设备是收音机、空调和白圈轮胎。这30辆汽车中，15辆有收音机，8辆有空调，6辆是白圈轮胎，而这三种设备都具有的汽车有3辆，试求这三种设备都不具备的汽车至少有多少辆？ 71.数1，2， ，9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。

72.在等于300的自然数中：（1）有多少个不能被3，5和7整除的数？（2）有多少个能被3整除，但不能被5和7整除的数？ 73.求下列数值函数的生成函数：

（1）ar cr(r=0，1，2， )，其中C为实数。 (2) ar 1 r （r=0,1,2, ）,其中a为正整数。 ，74.求下列生成函数的数值函数：其中A x x2 5 6x x2

nn

2 n. 75.用生成函数求下式之和： 1 12 n n

q

r

76.一个人上楼梯，可以一步上一个台阶，也可以一步上两个台阶，令an表示有n 个台阶时的上楼方式数，写出an的递推关系，并求解之。 77.利用特征方程法解递推关系：

an an 1 9an 2 9an 3,n 3

a 0,a 1,a 2012

n

78.求下列递推关系的特解 an 3an 1 2an 2 2

79.1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数。

80．在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？ 81. 计算[1,n]的无重不相邻组合C n,r 的计数问题

82. 某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干

钥匙。须４人到场，所备钥匙才能开锁。问①至少有多少把不同的钥匙？②每人至少持几把钥匙？

83. 凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少

点？又把所有对角线分割成多少段？ 84.在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个? 85. 整数n拆分成1，2，3， ，m的和，并允许重复，求其母函数。

86.某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次， 每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇1次，1人也没有遇见的有5次，问某甲共参加了几次会议？ 87. 给出下列等式的组合意义：

l

n m m m n l 1 n k l k ,n k m

l 0 （a）

m l 1 m l m l m l l m l 1 m 1 m m 1 m 2 m l

(b)

88. 将正整数10写成3个非负整数n1,n2,n3的和，要求n1 3,n2 4,n3 6，有多少种不同的写法？ 89. 计算母函数G x 1 2x1 3x x 的头6项。

2

90. 红、白、黑三色球各8个，现从中取出9个，要求3种颜色的球都有，问有多少种不同取法？ 91. 求序列c n,0 , c n,1 ,c n,2 , , 1 nc n,n 的母函数。 92. 解递归关系an an 2 0,a0 0,a1 2 93. 求下列表达式中求出a50的值

x 3x

2

3x 2

a0 a1x a50x50

94.设ar是掷两个骰子时和为r的方式数，其中第一个骰子的点数为偶数，第二 个骰子的点数为奇数，求序列 a0,a1,a2 的母函数。 95. 有多少棵有n个顶点的二叉数？ 96．求下式之和

1 c n,1 /2 c n,2 /3 1 nc n,n / n 1 97．展开多项式 x1 x2 x3

4

98.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。

99.试求n个完全一样的骰子掷出多少种不同的方案？ 100. 写出全部部分数最小的19-完备分拆

kn

fn 2 101. 已知，求f n

n

102. 求方程x1 2x2 4x3 17的非负整数解的个数。

四、证明题

1.证明：{1,2, ,n}的全排列的最大逆序数是n(n-1)/2。试确定具有n(n-1)/2个逆序的唯一排列。

2.证nc n 1,r r 1 c n,r 1 ．并给出组合意义.

3.n个完全一样的球，放到r个有标志的盒子，n≥r，要求无一空盒，试证其方案数为c n 1,r 1 .

4. 试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数． 5. 试证明：c 0,m c 1,m c n,m c n 1,m 1 6. 证明：(C(n,0))2+(C(n,1))2+ +(C(n,n))2 = C(2n,n) 7. 证明：若F1 F2 1, Fn Fn 1 Fn 2 (n>2)，则

nn

Fn 1 5/2 1 5/2 / n n/

其中α=（1+√5）/2，β=（1-√5）/2

8. N个代表参加会议，试证其中至少有两个人各自的朋友数相等。 9. 证明：12 22 n2 n n 1 2n 1 /6 10. 证明： 2n !/2n是整数。

11. 证明：在边长为1的等边三角形内任取5点，试证至少有两点的距离小于1/2。

112.证明： 1

1 Fn 1 F0 n

n

Fn

Fn 1

其中Fn定义为：F1 F2 1，Fn Fn 1 Fn 2

13.任取11个整数，求证其中至少有两个数它们的差是10的倍数。

14.在边长为1的正方形内任取5点，试证其中至少有两点，

2。 15.若H是群G的子群，试证：|xH|=K, 其中K＝|H|，x∈G。

16.二维空间的点（x,y）的坐标x和y都是整数的点称为格点。任意5个格点的

集合A，试证A中至少存在两个点，它们的中点也是格点。 17.证明：在由字母表{0，1，2}生成的长度为n的字符串中，0出现偶数次的字符串有（3n+1）/2个。 18.试证任意r个相邻的正整数的连乘积（n+1）(n+2) (n+r)必被r!除尽。 19.证明：c m,0 c m,n c m,1 c m 1,n 1 c m,n c m n,0 2nc m,n 20.证明c n,1 2c n,2 nc n,n n2n 1

21. 任取5个整数，试求其中必存在3个数，其和能被3整除。

22. 若H是群G的子群，x和y 是G的元素。试证xH∩yH或为空集，或xH=yH. 23. 令S={1，2， ，n+1},n≥2,T x,y,z S,x z,y z

试证： 12 22 ...... n2 C n 1,2 2C n 1,3 。

24. 证明：任何K个相继的正整数之积，必是r的倍数，其中r=1，2， ，K。

n 22n2n2 …… 此处隐藏：3273字，全部文档内容请下载后查看。喜欢就下载吧 ……