组合数学试题.pdf

组合数学期末试题（A） 姓名姓名班级班级学号学号成绩成绩 一， 把 m 个负号和 n 个正号排在一条直线上，使得没有两个负 号相邻，问有多少种不同的排法。 二， 在 1 和 100 之间既不是某个整数的平方， 也不是某个整数的 立方的数有多少个？ 三， 边长为 1 的等边三角形内任意放 10 个点，证明一定存在两 个点，其距离不大于 1/3。 四， 凸 10 边形的任意三条对角线不共点， 试求(1)这凸 10 边形的 对角线交于多少个点？(2)又把所有对角线分割成多少段？ 五， 求和 k （） k+1 1 1 1 n k n k 六，求解递推关系 12 01 693 0,1 nnn aaa aa 七， 用红白蓝三种颜色对 1n 的方格涂色， 每个方格只能涂一种 颜色，如果要求偶数个方格涂成红色，问有多少种方法？ 八，用红、蓝二种颜色对 1n 的方格涂色，每个方格只能涂一种 颜色， 如果要求涂成红色的两个方格不能相邻， 问有多少种方法？ 注，注，1-4、6 题各题各 15 分，第分，第 5 题题 10 分，第分，第 7 题题 8 分，第八题分，第八题 7 分。分。 北京邮电大学 2005 2006 学年第 1 学期北京邮电大学 2005 2006 学年第 1 学期 组合数学期末试题答案 一， (15) 解： 由于正负号不能相连，故先将正号排好，产生 n+1 个空档。 -5 分 则负号只能排在两个正号之间， 这相当于从 n+1 个数中取 m 个数 的组合，故有-10 分 1n m + 种方式。-15 备注：若写出备注：若写出 mn+1 时为时为 0，m=n+1 时为时为 1，给，给 5 分分 二， （19 分） 解：设 A 表示是 1-100 内某个数的平方的集合，则 |A|=10, -4 分 设 B 表示是 1-100 内某个数的立方的集合，则|B|=4, -8 分 |AB|=2, -12 分 由容斥原理得 100 | 100 104288 ABABA=+ =+= B -19 分 三， （15 分） 证明：将此三角形剖分成 9 个小的边长为 1/3 的等边三角形。 - -5 分 由鸽巢原理，必有两点在某一个小三角形内，-12 分 此时，这两点的距离不超过小三角形边长 1/3。从而得证。 -15 分 四， （15 分） 解： （1）由于没有三条对角线共点，所以这凸多边形任取 4 点， 组成的多边形内唯一的一个四边形，确定唯一一个交点，-5 分 从而总的交点数为 C(10,4)=210-10 分 （2）如图，不妨取顶点 1，考察由 1 出发的对角线被其他对角线 剖分的总数。不妨设顶点标号按顺时针排列，取定对角线 1 i 一个在右侧，则与对角线 1i 相交的 其他对角线 必定一个顶点在左侧， 于是，这种交点总数为 （10-i）(i-2) - 1 分 从而此对角线被剖分成 （10-i）(i-2)+1 段 -2 分 2 i 10 1 从而由顶点 1 出发的所有对角线被分割成的小段总数为 -4 分 从而全体对角线被分割的小段总数为： 9 3 (10)(2)1)91 j i i = += 10 91 455 2 =条 - 5 分 五， （6 分） 解：原式= 1 1 1 11 1 1 1 1 11 = = + + + = + n k n k n n kn n kn k k+1 （） k+1 （） 1 1 0 1 1 (1 11 11 ) 10 1 1 (1 1 1 (0) 11 = + = ) + = + + + + =+ + =+= + n k n k k n kn nn n n kn n n nn k+1 （） （） - 6 分 六， （15 分） 解：对应齐次递推关系的特征方程为 x2+6x+9=0 特征根x1=x2=-3,所以齐次递推关系的通解为 an=(k1+k2n)(-3)n - 5 分 设特解为 C，则 C+6C+9C=3 - 7 分 所以 C=3/16, 所以通解为an=3/16 +(k1+k2n)(-3)n -10 分 由初始条件可得： 3/16 +k1 =0， k1 =-3/16 3/16 +(k1+k2)(-3)=1 k2 =-1/12 所以 n n 313 a()( 3) 161216 = +-15 分 七， （8 分） 解：设an表示涂色的方案数，定义a0=1，则an的指数型 母函数为 242 12 2 23 000 ( )(1) 2!4!2 ! (1) 1!2! 11 ()() 22 11 (3)(31) 2!2 n e n xxxxx nn nn nnn xxx fx n xxx n eeeee ! n xxx nn = =+ + =+=+ =+=+ n -4 分 所以 1 (31) 2 n n a =+-8 分 另外，直接由组合方法求得结果为另外，直接由组合方法求得结果为 2 0 31 2 (1) 22 = + = n n n k k n n k 亦可。 八， （7 分） 解：设an表示涂色的方案数，考察第一个方格的染色方 案，若染红色，则下一个必须染蓝色，于是剩下的方格 染色方案数恰为an-2,若第一个方格染蓝色，则剩下的方 格染色方案数恰为an-1,由加法原理，我们建立如下递推 关系： an=an-1+an-2 - 3 分 确定初始条件:显然，对一个方格有两种方案，对两个方 格有 3 种方案：第一个红第二个蓝色，第一个蓝第二个 红色，二个都是蓝色，即 a1=2, a2=3 -4 分 求解此递推关系，实际上它是斐波那契数列Fn+1， 特征方程为,解得特征根为 01 2 = xx 2 51 , 2 51 = + = 得通解为,于是有 nn n kka 21 += += += 2 2 2 1 21 3 2 kk kk 则 10 535 , 10 535 21 = + =kk 从而 nn n a 10 535 10 535 + + =-7 分 另外，若直接由组合方法求得另外，若直接由组合方法求得 12 0 1 n n k nk a k + = + = 亦对。 注：由于组合问题求解方法众多，不一一列出。 北京邮电大学 2005 2006 学年第 1 学期北京邮电大学 2005 2006 学年第 1 学期 组合数学期末试题(计算机院) 姓名姓名班级班级学号学号成绩成绩 一， 有颜色不同的 4 盏灯。 （20 分） （1） 把它们按不同的顺序全部挂在灯杆上表示信号， 共有多 少种不同的信号？ （2） 每次使用一盏、二盏、三盏或四盏按一定的次序挂在灯 杆上表示信号，共有多少种不同的信号？ （3） 在(2)中如果信号与灯的次序无关， 共有多少种不同的信 号？ 二， （1）在边长为 1 的等边三角形内任意放 5 个点，证明一定 存在两个点，其距离不大于 1/2。而放 4 个点则结论不成立。 （2）由此推广，确定最小的 m(n),使当放 m(n)点在边长为 1 的等边三角形内时其中必有两点的距离不大于 1/n（20 分） 三， 把 m 个负号和 n 个正号排在一条直线上，使得没有两个负 号相邻，问有多少不同的排法。 （15 分） 四， 求解递推关系 12 01 321 4,6 nnn aaa aa （15 分） 五， 在 1 和 10000 之间不能被 4、 5 和 6 整除的数有多少个？ （15 分） 六， 用红白 2 种颜色对 1n 的方格涂色，每个方格只能涂一种 颜色， 如果要求偶数个方格涂成白色， 问有多少种方法？（8 分） 七， 用红、蓝二种颜色对 1n 的方格涂色，每个方格只能涂一 种颜色，如果要求涂成红色的两个方格不能相邻，问有多少 种方法？（7 分） 北京邮电大学 2005 2006 学年第 1 学期北京邮电大学 2005 2006 学年第 1 学期 组合数学期末试题答案(计算机院) 一， （20 分） 解: (1)由于颜色不同,这相当于1,2,3,4上的一个全排列,从而有 4!=24 种不同的信号.6 分 (2)由于可以使用的灯盏数可以不同,从而由(1)我们有 种不同信号.8 分 64 4 4 3 4 2 4 1 4 =+PPPP (3),这里,信号与灯的次序无关,从而是一个组合问题,与(2)类似 不同的信号种类有种不同的信号. 15 4 4 3 4 2 4 1 4 =+CCCC -6 分 二， （ （20 分） 解: (1)将此三角形剖分成 4 个小的边长为 1/2 的边三角形。-4 分 由鸽巢原理，必有两点在某一个小三角形内，此时，这两点的距 离不超过 1/2.-10 分 但若将 4 个点放入则不行,实际上只要在三角形中心放一个点,在 三个顶点附近各放一个点即可,如图.-15 分 (2),由此推广,将此三角形剖分成 n 个小的边长为 1/n 的 等边三角形。将个点放入此三角形中,由鸽巢原理，必有两点在 某一个小三角形内，此时，这两点的距离不超过 1/n-5 分 2 n 三， （15 分） 解： 由于正负号不能相连，故先将正号排好，产生 n+1 个空档。 -5 分 则负号只能排在两个正号之间， 这相当于从 n+1 个数中取 m 个数 的组合，故有-10 分 1n m + 种方式。-15 备注：若写出备注：若写出 mn+1 时为时为 0，m=n+1 时为时为 1，给，给 5 分分 四， （15 分） 解: 对应齐次递推关系的特征方程为 x2-3x+2=0 -3 分 特征根x1=2,x2=1,所以齐次递推关系的通解为 an=k1+k22n - 5 分 由于 1 是特征根,所以设特解为 Cn，则 C n-3C(n-1)+2C(n-2)=1 7 分 所以 C=-1, 所以通解为 an=- n +k1+k22n -10 分 由初始条件可得： k1 +k2 =4，k1+2k2-1=6 解得k1 =1, k2 =3. 所以an=- n +1+32n -15 分 五， （15 分） 解： 用 A,B,C 分别表示 1-10000 之间被 4， 5 和 6 整除的数的集合。 于是由容斥原理问题是求|ABC|。-2 分 100001000010000 |A|2500,|B|2000,|C|1666, 456 1000010000 |AB|500,|AC|833, 4 54 3 1000010000 |CB|333,|ABC|166, 6 54 5 3 = = = -10 分 |ABC| 10000(| A| B|C|)(| AB|AC| | BC|) |ABC| 100025002000 1666500 833333 1665334 =+ +=+ += -15 分 六， （8 分） 解：设an表示涂色的方案数，定义a0=1，则an的指数型 母函数为 242 12 2 0 ( )(1) 2!4!2 ! (1) 1!2! 11 ()(1) 22 1 (21) 2! = =+ + =+=+ =+ n e n xxxx n n n xxx fx n xxx n eeee x n -3 分 所以 1 2 (1) = n n an-8 分 注：若规定偶数不含 0，则 1 2-1 (1) = n n an。另外可直接 由组合方法求，答案为 2 1 0 2 (1) 2 = = n n k n n k 。 七， （7 分） 解：设an表示涂色的方案数，考察第一个方格的染色方 案，若染红色，则下一个必须染蓝色，于是剩下的方格 染色方案数恰为an-2,若第一个方格染蓝色，则剩下的方 格染色方案数恰为an-1,由加法原理，我们建立如下递推 关系：an=an-1+an-2 - 3 分 确定初始条件:显然，对一个方格有两种方案，对两个方 格有 3 种方案：第一个红第二个蓝色，第一个蓝第二个 红色，二个都是蓝色