组合数学第二章母函数与递推关系习题解答.pdf

1 证明等式 2 210 22222 n n n nnnn 解 2 求 中 项的系数 10084 1 xx 20 x 解 3 有红 黄 蓝 白球各两个 绿 紫 黑的球各3个 问从中取出10个球 试问 有多少种不同的取法 解 4 求由A B C D组成的允许重复的排列中 AB至少出现一次的排列数目 解 5 求n位四进制数中2和3必须出现偶次的 数目 解 6 试求由a b c三个文字组成的n位符号串 中不出现aa图像的符号串的数目 解 7 证明序列 的母函数为 1 1 1 n x 2 1 nnCnnCnnC 解 8 证明 1 1 1 nmnC nmnCnnCnnC 解 9 利用 改善 4 2 的 估计式 63 1 2 1 1 1 2 222 n p 解 10 8台计算机分给3个单位 第1单位 的分配量不超过3台 第2单位的分配量 不超过4台 第3个单位不超过5台 问 共有几种分配方案 解 11 证明正整数n都可以唯一地表示成不 同的且不相邻的Fibonacci数之和 即 1 0 0 1 2 iii i ii aaaFan 注意 是相同的Fibonacci数 1 21 FF 解 12 设空间的n个平面两两相交 每3个 平面有且仅有一个公共点 任意4个平面 都不共点 这样的n个平面把空间分割成 多少个不重叠的域 解 13 相邻位不同为0的n位2进制数中一共 出现了多少个0 解 14 在Hanoi塔问题中 在柱A上从上到 下套着n个圆盘 其编号依次从1到n 现 要将奇数编号与偶数编号的圆盘分别转 移到柱B和柱C上 转移规则仍然是每次 移动一个 始终保持上面的比下面的小 一共要移动多少次 解 15 一书框中有m格 每格各放n册同类 的书 不同格放的书类型不同 现取出 整理后重新放回 但不打乱相同类 试 问无一本放在原来位置的方案数应多少 解 16 设一矩形 其中 作 使得 是一正方形 试证矩形 和 相似 试证继续这过程可得 一和原矩形相似的矩形序列 51 2 1 ADAB 11B C DCAB 11 CDCB 11 ABCD ABCD 解 AB CD 1 B 1 C 17 平面上有两两相交 无三线共点的n 条直线 试求这n条直线把平面分成多少 个域 解 18 在一圆周上取n个点 过一对顶点可 作一弦 不存在三弦共点的现象 求弦 把圆分割成几部分 解 19 求n位二进制数相邻两位不出现11的 数的个数 解 20 从n个文字中取k个文字作允许重复 的排列 但不允许一个文字连续出现三 次 求这样的排列的数目 解 21 求 的和 4444 321n 解 22 求矩阵 20 13 100 解 23 求 n k n n k n n k n kkkS kkSkkS 0 00 2 1 2 1 解 24 在一个平面上画一个圆 然后一条 一条地画n条与圆相交的直线 当r是大 于1的奇数时 第r条直线只与前r 1条直 线之一在圆内相交 当r是偶数时 第r 条直线与前r 1条直线在圆内部相交 如 果无3条直线在圆内共点 这n条直线把 圆分割成多少个不重叠的部分 解 25 用 记具有整数边长周长为n的三 角形的个数 a 证明 是奇数当 是偶数 当 n n a na a n n n n 4 1 2 2 3 3 b 求序列 的普通形母函数 n a n a 解 26 a 证明边长为整数 最大边长为 l的三角形的个数是 b 设 记边长不超过2n的三角形 的个数 而 记边长不超过2n 1的三角 形的个数 求 和 的表达式 是偶数 当 是奇数 当 ll l ll 2 4 1 4 1 2 n f n f n g n g 解 27 设 a 证明 b 求序列 与 的母函数 c 用Fibonacci数来表示 与 1 00 12 2 0 n k n n k n k kn b k kn an 111nnnnnn babbaa n a n b n a n b 解 28 设 a 证明 b 证明 的充要条件是 21121 1 nn FFFFF 1 11 knFFFFF knkknkn mn FF mn c 证明 2 2 1 1062 nm nF nF FFFFF nm nm nmnmnmnm 是偶数 当 是奇数 当 d 证明 为m n 的最大公约数 nmFFF nmnm 解 29 从1到n的自然数中选取k个不同且不 相邻的数 设此选取的方案为 a 求 的递推关系 b 用归纳法求 c 若设1与n算是相邻的数 并设在此 假定下从1到n的自然数中选取k个不同且 不相邻的k个数的方案数为 利用 求 knf knf knf knf kng kng 解 30 设 是第二类Stirling数 证明 2 knS 1 1 2 1 2 mkS k n mnS n mk 解 3