组合数学习题解答

第一章 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 2 8 9 9 2 1 14 求 1 到 10000 中 有多少正数 它的数字之和等于 5 又有多少数字之和小于 5 的整 数 解 1 在 1 到 9999 中考虑 不是 4 位数的整数前面补足 0 例如 235 写成 0235 则问题就变为求 x1 x2 x3 x4 5 的非负整数解的个数 故有 F 4 5 56 5 154 2 分为求 x1 x2 x3 x4 4 的非负整数解 其个数为 F 4 4 35 x1 x2 x3 x4 3 的非负整数解 其个数为 F 4 3 20 x1 x2 x3 x4 2 的非负整数解 其个数为 F 4 2 10 x1 x2 x3 x4 1 的非负整数解 其个数为 F 4 1 4 x1 x2 x3 x4 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 2 5 在图中 每个方格着红色或蓝色 证明至少存在两列有相同的着色 解 每列着色的方式只可能有种 现有列 由鸽笼原理知 至少有二列着色方2 24 5 式相同 2 7 一个学生打算用 37 天总共 60 学时自学一本书 他计划每天至少自学 1 学时 证明 无论他怎样按排自学时间表 必然存在相继的若干天 在这些天内其自学总时数恰好为 13 学时 解 设是第一天自学的时数 是第一 二天自学的时数的和 是第一 二 1 a 2 a j a 第天自学时数的和 j1 2 37j 于是 序列是严格递增序列 每天至少一学时 而且 1237 a aa 137 1 60aa 于是序列也是严格递增的序列 故 137 13 13aa 37 1373a 因此 74 个数都在 1 和 73 两个整数之间 由鸽笼原 137137 13 1373aaaa 理知 这 74 个数中必有两个是相等的 由于中任何两数都不相等 故 1237 a aa 中任何两个数也是不相等的 因此 一定存在两个数使得 137 13 13aa i j 1313 ijij aaaa 因此 在这些天中 这个学生自学总时数恰好为 13 1 2 jji 2 10 证明 在任意 52 个整数中 必存在两个数 其和或差能被 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 或 ri rj 100 这就是说 ai aj 可 100 整除 或 ai aj 可被 100 整除 第三章 3 2 求 1 到 1000 中既非完全平方又非完全立方的整数个数 解 设 1 2 1000 表示 1 到 1000 中完全平方数的集合 则表示 1 到 1000S 1 A 1 A 中不是完全平方数的集合 表示 1 到 1000 中完全立方数的集合 则表示 1 到 1000 2 A 2 A 中不是完全立方数的集合 故表示 1 到 1000 中既非完全平方又非完全立方的整数的集合 由容斥原理 2 1 AA 3 5 式 知 3 5 212121 AAAASAA 其中 1000 S 1 100031A 3 2 100010A 表示 1 到 1000 中既是完全平方又是完全立方的数的集合 故 21 AA 3 21 AA 6 1000 将以上数值代入 3 5 式得 1000 31 10 3 962 21 AA 故 1 到 1000 中既非完全平方又非完全立方的整数个数为 962 3 8 在所有的 n 位数中 包含数字 3 8 9 但不包含数字 0 4 的数有多少 解 除去 0 4 则在 1 2 3 5 6 7 8 9 这 8 个数字组成的 n 位数中 令 S 表示由这 8 个数字组成的所有 n 位数的集合 则 S 8n P1表示这样的性质 一个 n 位数不包含 3 P2表示这样的性质 一个 n 位数不包含 8 P3表示这样的性质 一个 n 位数不包含 9 并令 Ai表示 S 中具有性质 Pi的元素构成的集合 i 1 2 3 则表示 S 中包含 3 又包含 8 又包含 9 的所有 n 位数的集合 AAA321 由容斥原理 3 5 式 得 3 5 321 AAA 321 3 1 AAAAAAS ji ji i i 而 777321 nnn AAA 666323121 nnn AAAAAA 5321 n AAA 代入 3 5 式得 123 83 73 65 nnnn AAA 故所求的 n 位数有个 nnnn 563738 3 10 求重集的 10 组合数 3 4 5Babc 解 构造集合 B 令集合 B 的所有 10 组合构成的集合为 S 由 cba 第一章的重复组合公式 1 11 有 F 3 10 66 S 10 1103 令 p1表示 S 中的元素至少含有 4 个 a 这一性质 令 p2表示 S 中的元素至少含有 5 个 b 这一性质 令 p3表示 S 中的元素至少含有 6 个 c 这一性质 并令 Ai i 1 2 3 表示 S 中具 有性质 pi i 1 2 3 的元素所构成的集合 于是 B 的 10 组合数就是 S 中不具有性质 p1 p2 p3 的元素个数 由容斥原理 3 5 式 有 3 5 321 AAA 321 3 1 AAAAAAS ji ji i i 由于已经求得 66 下面分别计算 3 9 式右端其他的项 S 由于 A1中的每一个 10 组合至少含有 4 个 a 故将每一个这样的组合去掉 4 个 a 就得 到集合 B 的一个 6 组合 反之 如果取 B 的一个 6 组合并加 4 个 a 进去 就得到了 A1 的一个 10 组合 于是 A1的 10 组合数就等于 B 的 6 组合数 故有 F 3 6 28 1 A 6 163 同样的分析可得 F 3 5 21 2 A 5 153 F 3 4 15 3 A 4 143 用类似的分析方法可分别求得 F 3 1 3 21 AA 1 113 F 3 0 1 31 AA 0 103 0 因为 5 6 11 10 32 AA 0 同上 321 AAA 将以上数值代人 3 9 式得到 66 28 21 15 3 1 0 0 321 AAA 6 故所求的 10 组合数为 6 3 14 求由数字 1 2 8 所组成的全排列中 恰有 4 个数字在其自然位置上的全排列 个数 解 4 个数在其自然位置共有种方式 对某一种方式 均有 4 个数字不在其自然位 4 8 置 这正好是一个错排 其方式数为 见定理 3 2 由乘法规则有 恰有 4 个数字在其 4 D 自然位置上的全排列数为 630 4 8 4 D 第四章 4 6 求重集的 10 组合数 7 5 3 dcbaB 解 设重集 B 的 n 组合数为 则序列 的普通母函数为 n a n a 2232345 1 1 1 f xxxxxxxxxxx 234567 1 xxxxxxx x x x x x x x 1 1 1 1 1 1 1 1 864 1 x4 x6 x8 x10 x12 x14 x18 0 3 3 k k x k 所以 a10 3 03 3 23 3 43 3 63 3 103 286 84 35 10 1 158 故重集 B 的 10 组合数为 158 4 9 设重集 并设是满足以下条件的 r 组合数 123456 Bbbbbbb AAAAAA r aB 求序列的普通母函数 01 r a aa a 每个 出现 3 的倍数次 I b 1 2 3 4 5 6I b 至多出现 1 次 至少出现 2 次 最多出现 4 次 1 b 2 b 34 b b 56 b b c 出现偶数次 出现奇数次 出现 3 的倍数次 出现 5 的倍数次 1 b 6 b 3 b 4 b d 每个至多出现 8 次 I b 1 2 3 4 5 6I 解 a 3696 1 f xxxx 3 0 6 k k Fkx b 223422342 1 1 f xxxxxxxxx c 2435369510 1 1 1 f xxxxxxxxxxx 1 x xx 232 d 238 6 1 f xxxx 4 10 有两颗骰子 每个骰子六个面上刻有 1 2 3 4 5 6 个点 问掷骰子后 点数之 和为 两颗骰子的点数有多少种搭配方式 r 解 每个骰子是不同的 但讨论点数之和的时候不考虑顺序 故该问题是组合问题 设有满足条件的搭配方式有种 则其普通母函数为 r a 262 f xxxx 其中的系数即为所求的搭配方式数 r x r a 4 14 求由数字 2 3 4 5 6 7 组成的位数中 3 和 5 都出现偶数次 2 和 4 至少出r 现一次的位数的个数 r 解 这是一个排列问题 设满足条件的位数的个数为 则序列r r a 对应的指数母函数为 12 r a aa 24223 222 1 1 2 4 2 2 3 e xxxxx xxx f 222 2 1 1 2 xxxx eeee 1 1 62 53 44 33 22 4 r rrrrr r x r 所以 0 2233443526 4 1 0 0 r r a rrrrr r 5 2 如果用 an表示没有两个 0 相邻的 n 位三元序列 即由 0 1 2 组成的序列 的个数 求 an所满足的递归关系并解之 解 对 n 位三元序列的第一位数有三种选择方式 1 第一位选 1 则在剩下的 n 1 位数中无两个 0 相邻的个数为 an 1 2 第一位选 2 则在剩下的 n 1 位数中无两个 0 相邻的个数为 an 1 3 第一位选 0 则在第二位又有两种选择方式 1 第二位选 1 则在剩下的 n 2 位数中无两个 0 相邻的个数为 an 2 2 第二位选 2 则在剩下的 n 2 位数中无两个 0 相邻的个数为 an 2 显然有 a1 3 a2 8 由加法规则得an所满足的递归关系为 8 3 3 22 21 21 aa naaa nnn 其特征方程为 x2 2x 2 0 特征根为 x1 1 x2 1 33 由定理 5 3 知其通解为 an c1 1 n c2 1 n33 由初始条件有 8 31 31 3 31 31 2 2 2 1 21 cc cc 解以上 方程组得 6 323 1 c 6 323 2 c nn n a3132331323 6 1 5 4 某人有 n 元钱 她每天要去菜市场买一次菜 每次买菜的品种很单调 或者买一元钱 的蔬菜 或者买两元钱的猪肉 或者买两元钱的鱼 问 她有多少种不同的方式花完这 n 元钱 解 设花完这 n 元钱的方式有 an种 则第一次花钱可分为下面几种情况 1 若第一次买一元钱的菜 则花完剩下的n 1 元钱就有 an 1种方式 2 若第一次买二元钱的肉 则花完剩下的n 2 元钱就有 an 2种方式 3 若第一次买二元钱的鱼 则花完剩下的n 2 元钱就有 an 2种方式 显然有 a1 1 a2 3 由加法规则 得递归关系如下 3 1 3 2 21 21 aa naaa nnn 其特征方程为 0 2 2 xx 特征根 2 1 21 xx 通解 nn n cca2 1 21 由初始条件得 32 1 12 1 2 2 2 1 21 cc cc 解得 3 2 3 1 21 cc 故该递归关系的解为 3 2 2 1 3 1 nn n a 故她有种不同的方式花完这 n 元钱 3 2 2 1 3 1 nn 5 6 求解下列递归关系 a 1 0 2 396 10 21 aa naaa nnn 解 这是一个常系数线性非齐次递归关系式 其导出的齐次递归关系为 2 1 96 nnn aaa 其特征方程为 096 2 xx 解得 3 21 qq 由定理 5 3 知 所导出的齐次线性递归关系的通解为 n n ncca3 21 由于 f n 3 且 1 不是式递归关系式的特征根 故设特解为 Aan 将代入递归关系得Aan 396 AAA 16 3 A 由定理 5 6 知 递归关系式的通解为 n 21 3 16 3 nccaaan 将初值条件代入上式并解得 12 1 16 3 2 1 c c 故 n 3 12 1 16 3 16 3 nan b 1 0 2 365 10 2 21 aa nnaaa nnn 解 这也是一个常系数线性非齐次递归关系式 其导出的齐次递归关系的特征方程 为 065 2 xx 特征根为 3 2 21 xx 由定理 5 3 知 所导出的齐次线性递归关系的通解为 nn n cca 3 2 21 由于 f n 3n 且 1 不是递归关系式的特征根 故设特解为 2 21 2 0 AnAnAan 将上式代入 递归关系式解得 288 115 24 17 4 1 210 AAA 通解 288 115 24 17 4 1 3 2 2 21 nnccaaa nn nnn 由初始条件有 1 288 115 24 17 4 1 32 0 288 115 21 21 cc cc 解得 32 37 9 14 21 cc 故递归关系的解为 288 115 24 17 4 1 3 32 37 2 9 14 2 nnaaa nn nnn c 12 01 7103 2 0 1 n nnn aaan aa 解 对应齐次递归关系的特征方程为 x2 7x 10 0 其特征根 x1 5 x2 2 12 52 nn n acc 又 f n 3n 且 3 不是递归关系式的特征根 故设特解为 将 3n n aA 代入原递归关系得3n n aA