组合数学试题.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 学期 组合数学期末试题答案 一， (15) 解： 由于正负号不能相连，故先将正号排好，产生 n+1个空档。 -5分 则负号只能排在两个正号之间， 这相当于从 n+1个数中取 m个数 的组合，故有-10分 1 n 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 10 4 2 88 ABA BA =+ = += 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 ii = += 10 91 455 2 = 条 - 5分 五， （6 分） 解：原式= 1 1 1 11 1 1 1 1 1 1 = = + + + = + + n k n k n n k n n k n k k+1 （） k+1 （） 1 1 0 1 1 (1 1 1 11 ) 10 1 1 (1 1 1 (0 ) 11 = + = ) + = + + + + + =+ + =+ = + n k n k k n k n nn n n k n n n nn k+1 （） （） - 6 分 六， （15分） 解：对应齐次递推关系的特征方程为 x 2 +6x+9=0 特征根x 1 =x 2 =-3,所以齐次递推关系的通解为 a n =(k 1 +k 2 n)(-3) n - 5分 设特解为 C，则C+6C+9C=3 - 7分 所以 C=3/16, 所以通解为a n =3/16 +(k 1 +k 2 n)(-3) n -10 分 由初始条件可得： 3/16 +k 1 =0， k 1 =-3/16 3/16 +(k 1 +k 2 )(-3)=1 k 2 =-1/12 所以 n n 31 3 a() ( 3 ) 16 12 16 =+ -15分 七， （8分） 解：设a n 表示涂色的方案数，定义a 0 =1，则a n 的指数型 母函数为 24 2 12 2 23 000 ( ) (1 . .) 2! 4! 2 ! (1 . .) 1! 2! ! 11 ()() 22 11 (3 ) ( 31 ) 2!2 n e n xxx xx nn nn nnn xx x fx n xx x n eee ee ! n xxx nn = =+ + =+=+ =+=+ n -4分 所以 1 (3 1) 2 n n a = + -8分 另外，直接由组合方法求得结果为 2 0 31 2 ( 1) 2 2 = + = n n nk k n n k 亦可。 八， （7分） 解：设a n 表示涂色的方案数，考察第一个方格的染色方 案，若染红色，则下一个必须染蓝色，于是剩下的方格 染色方案数恰为a n-2 ,若第一个方格染蓝色，则剩下的方格染色方案数恰为a n-1 ,由加法原理，我们建立如下递推 关系： a n =a n-1 +a n-2 - 3分 确定初始条件:显然，对一个方格有两种方案，对两个方 格有 3 种方案：第一个红第二个蓝色，第一个蓝第二个 红色，二个都是蓝色，即 a 1 =2, a 2 =3 -4分 求解此递推关系，实际上它是斐波那契数列F n+1 ， 特征方程为 ,解得特征根为 0 1 2 = x x 2 5 1 , 2 5 1 = + = 得通解为 ,于是有 n n n k k a 2 1 + = + = + = 2 2 2 1 2 1 3 2 k k k k 则 10 5 3 5 , 10 5 3 5 2 1 = + = k k 从而 n n n a 10 5 3 5 10 5 3 5 + + = -7 分 另外，若直接由组合方法求得 1 2 0 1 n n k nk a k + = + = 亦对。 注：由于组合问题求解方法众多，不一一列出。 北京邮电大学 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 种颜色对 1 n 的方格 涂色，每个方格只能涂一种 颜色， 如果要求偶数个方格涂成白色， 问有多少种方法？ （8 分） 七 ， 用红、蓝二种颜色对 1 n 的 方格涂色，每个方格只能涂一 种颜色， 如果要求涂成红色的两个方格不能相邻， 问有多少 种方法？（7 分）北京邮电大学 2005 2006 学年第 1 学期 组合数学期末试题答案(计算机院) 一， （20分） 解: (1)由于颜色不同,这相当于1,2,3,4上的一个全排列,从而有 4!=24种不同的信号.6分 (2)由于可以使用的灯盏数可以不同,从而由(1)我们有 种不同信号.8分 64 4 4 3 4 2 4 1 4 = + + + P P P P (3),这里,信号与灯的次序无关,从而是一个组合问题,与(2)类似 不同的信号种类有 种不同的信号. 15 4 4 3 4 2 4 1 4 = + + + C C C C -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分 1 n m + 种方式。-15 备注：若写出 mn+1时为 0，m=n+1时为 1，给 5分 四， （15分） 解: 对应齐次递推关系的特征方程为 x 2 -3x+2=0 -3分 特征根x 1 =2,x 2 =1,所以齐次递推关系的通解为 a n =k 1 +k 2 2 n - 5分 由于 1 是特征根,所以设特解为 Cn，则 C n-3C(n-1)+2C(n-2)=1 . 7分 所以 C = -1, 所以通解为 a n =- n +k 1 +k 2 2 n -10 分 由初始条件可得： k 1 +k 2 =4，k 1 +2k 2 -1=6 解得k 1 =1, k 2 =3. 所以a n =- n +1+32 n -15分 五， （15分） 解： 用 A,B,C分别表示 1-10000之间被 4， 5和 6整除的数的集合。 于是由容斥原理问题是求|A B C| 。-2分 10000 10000 10000 | A | 2500,| B | 2000,| C | 1666, 456 10000 10000 |A B| 500,|A C| 833 , 45 43 10000 10000 | C B | 333,| A B C | 166, 65 453 = = = = -10分 | A B C | 10000 (| A | | B | | C |) (| A B | | A C | | B C |) | A B C | 1000 2500 2000 1666 500 833 333 166 5334 =+ +=+ += -15 分 六， （8分） 解：设a n 表示涂色的方案数，定义a 0 =1，则a n 的指数型 母函数为 24 2 12 2 0 ( ) (1 . .) 2! 4! 2 ! (1 . .) 1! 2! ! 11 ()(1 ) 22 1 (2 1 ) 2! = =+ + + =+=+ =+ n e n xxx x n n n xx x fx n xx x n eee e 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分） 解：设a n 表示涂色的方案数，考察第一个方格的染色方 案，若染红色，则下一个必须染蓝色，于是剩下的方格 染色方案数恰为a n-2 ,若第一个方格染蓝色，则剩下的方 格染色方案数恰为a n-1 ,由加法原理，我们建立如下递推 关系：a n =a n-1 +a n-2 - 3分 确定初始条件:显然，对一个方格有两种方案，对两个方 格有 3 种方案：第一个红第二个蓝色，第一个蓝第二个 红色，二个都是蓝色，即 a 1 =2, a 2 =3 -4分 求解此递推关系，实际上它是斐波那契数列F n+1 ， 特征方程为 ,解得特征根为 0 1 2 = x x 2 5 1 , 2 5 1 = + = 得通解为 ,于是有 n n n k k a 2 1 + = + = + = 2 2 2 1 2 1 3 2 k k k k 则 10 5 3 5 , 10 5 3 5 2 1 = + = k k 从而 n n n a 10 5 3 5 10 5 3 5 + + = -7 分 另外，若直接由组合方法求得 1 2 0 1 + = + = n n k nk a k 亦对。