组合数学复习题解答

1 组合数学练习题 一 1 有20根完全相同的木棍从左至右竖立成一行 占据20个位置 要从中选出6根 1 有多少种选择 2 如果选出的木棍中没有两根是位置相邻的 又有多少种选择 3 如果选出的每一对木棍之间必须至少有两根木棍 又有多少种选择 解 1 有种 2 2 所选出的6根木棍实际上可将这20根排成一行的木棍分割成7段 加上首和尾 设所选左边第1根木棍的左侧有x1根未被选中的木棍 在第1与第2根所选木棍之间有x2根未被选中的木棍 在第5与第6根所选木棍之间有x6根未被选中的木棍 在第6根所选木棍的右侧有x7根未被选中的木棍 则由于没有两根选出的木棍是相邻的 所以 3 作变量代换 则原方程变成 这个方程的非负整数解的个数即为所求的选择数 4 3 同 2 中的分析 此时有不定方程 仿照 2 这个方程的非负整数解的个数即为所求的选择数 5 2 1 在2n个物体中有n个是相同的 则从这2n个物体中选取n个的方法有几种 2 在3n 1个物体中有n个是相同的 则从这3n 1个物体中选取n个的方法有几种 解 1 若选出的物体有个不 相同 则其余n k个是相同的 所以选取的方法数为 2 类似于 1 的分析可知 所以选取的方法数为 6 3 用种颜色去涂棋盘 每格涂一种颜色 求使得相邻格子异色 首末两格也异色的涂色方法数 解用hn表示所求方法数 易知 用m种颜色去涂棋盘 每格涂一种颜 色 使得相邻格子异色的涂色方法数有 种 其中使得首末两格同色的涂色方法有种 所以 从而 7 8 4 用种颜色去涂棱锥的n 1个顶点 每个顶点涂一种颜色 求使得棱锥的每条棱的两个端点异色的涂色方法数 解设V是一个n棱锥 则可依如下两个步骤去完成V的n 1个顶点的涂色工作 先涂顶点v0 有m种涂色方法 然后用异于v0颜色的m 1种颜色去涂顶点序列v1 v2 vn 使得相邻顶点异色且首末两个顶点也异色 9 由上题可知 完成此步骤的方法有 种 由乘法原理 得所求涂色方法数为 10 5 将充分多的苹果 香蕉 橘子和梨这4种水果装袋 要求各袋有偶数个苹果 最多2个橘子 3的倍数个香蕉 最多1个梨 如果每袋装n个水果 求装袋的种类数 11 12 6 把n个相异的球放到4个相异盒子中 求使得含有奇数个球 含有偶数个球的不同的放球方法数 则数列对应的指母函数为 解设满足条件的放球方法数为 13 所以 14 7 由数字1至9组成的每种数字至少出现1次的位数有多少个 解设所求的数为an 则 an 的指母函数为 所以 15 8 由字母a b c d e组成的总字母数为n的单词中 要求a与b的个数之和为偶数 求这样的单词的个数 解这样的单词有两类 一类包括偶数个a与偶数个b 另一类包括奇数个a与奇数个b 设所求的数为an 则 an 的指母函数为 16 故 17 9 有多少个长度为n的0与1串 在这些串中 既不包含子串010 也不包含子串101 解设这种数串的个数为 将满足条件的数串分为两类 1 最后两位数字相同 这种长度为n的数串可由长度为n 1的串最后一位数字重复一次而得 故这类数串的个数 2 最后两位数字不同 这种长度为n的数串可由长度为n 2的串最后一位 设为a 重复一次 再加上与a不同的数字而得 故这类数串的个数为 18 于是得递推关系 由Fibonacci数列 得通解 代入初值 得 19 10 由0 1 2 3组成的长度为n的序列中 求含偶数个0的序列个数和含奇数个0的序列个数 解设an为含偶数个0的序列个数 bn为含奇数个0的序列个数 则有 解得 20 11 十个数字 0到9 和四个运算符 组成14个元素 求由其中的n个元素的排列构成一形式算术表达式的个数 解令an表示n个元素排列成算术表达式的数目 则 解得 21 12 在一圆周上均匀地取2n个点 用n条两两不相交的弦把这些点配成对 求所有这种配对的方式数 解设所求配对的方式数为hn 则h1 1 则h0 1 设2n个点依次为 连接 配对方式数为hk 1 则将圆周一分为二 一边有2 k 1 个点 另一边有 2 n k 个点 配对方式数为hn k 22 于是 解得 23 13 一个计算机系统把一个十进制数字串作为一个编码字 如果它包含偶数个0 就是有效的 求有效的n位编码字的个数an 解显然 若末位数是1到9中某个数 则前面n 1位组成的有效数有an 1个 因此 末位数不是0的n位有效数字有9an 1个 若末位数是0 则这样的n位十进制数有10n 1个 而不是有效数的有an 1个 因n 1位的有效数后面添一个0就不是有效数了 所以末位数是0的有效数有 24 个 于是得递推关系 即 解得通解 代入初始条件得 故所求有效数字有 个 25 14 把件彼此相异的物品分给甲 乙 丙三人 使得甲至少分得两件物品 乙和丙至少分得一件物品 有多少种不同的分法 解设有N种不同的分法 因为把n件彼此相异的物品分给3个人 使得每人至少分得一件物品的方法共有 种 其中使得甲恰分得一件物品的分法有 种 故 27 15 令m和n是非负整数且 有m n个人站成一排进入剧院 入场费为每人50元 这m n个人中有n个人有50元面额的钞票 而另外m个人只有100元面额的钞票 售票处开门时使用一个空的现金收银机 求能够使得需要的时候总有零钱可找的队列方式数 证将有50元的人用1标识 有100元的人用 1标识 则该问题为 包括m个 1和n个1的m n个数 构成的序列 使 28 这m n个数的排列是集合的排列 排列数为 设A是满足以上要求的序列全体 称为可接受排列 设U为不可接受排列的全体 则 29 由于U是不可接受排列的集合 对U中任一个排列 必有最小的k 使 从而有 即k 1是偶数 且中有相等个数的1 和 1 将 中前k个变号后 可得一个由n 1个1和m 1个 1的序列 30 反之n 1个1和m 1个 1的序列 由于 故必存在k 使中1的个数恰比 1的个数多1 只要将这n 1个1和m 1个 1的序列前k项变号 就可得一个有n个1和m个 1的U中一个排列 所以U是集合的排列全体 于是 所以 31 组合数学练习题 二 32 33 34 2 将4个黑球 3个白球 2个红球排成一列 但不能让任何一种同颜色的球全部排在一起 问有多少种排法 假定同色球不加区别 解设所求数为N 以S表示由4个黑球 3个白球 2个红球作成的全排列之集 A B C分别表示S中4个黑球 3个白球 2个红球排在一起的全排列之集 则 35 所以 36 3 n个单位各派2名代表出席一个会议 2n名代表围一圆桌坐下 试问 1 同一单位代表相邻而坐的方案有多少种 3 同一单位的代表不相邻的方案有多少种 解 1 这是2n个元的圆排列 故各单位代表入座方式有 2 将同一单位代表看作一个整体参与排列 有 而同一单位的两位代表坐法有2种 左或右 故同一单位代表相邻而坐的方案有 37 3 设这2n个人入座方式的全体为S 则 S中第i个单位的两个人相邻的入座方式 则 38 由容斥原理 所求方案数为 同类问题 n对夫妻围圆桌而坐 求夫妻不相邻的入坐方案数 39 4 用10个球垒成一个三角阵 使得1个球在2个球之上 2个球在3个球之上 3个球在4个球之上 这个三角阵可自由旋转 用红色与蓝色对该阵各球着色 求不等价着色数 如果再允许翻转该阵 不等价着色数又有多少种 解将三角阵上的球标以1 10表示 它分别绕其中心逆时针旋转 得置换群 40 其中 恒等置换 逆时转 逆时转 由定理知 所求方案数为 41 如果球阵可以翻转 则置换群为 其中同前 由定理知 所求方案数为 42 5 将一个3行3列棋盘的9个正方形着红色和蓝色 棋盘可以绕对称中心旋转 但不能绕对称轴翻转 求不等价的着色方案数 从而得置换群Q所含的置换为 解棋盘可以分别绕对称中心逆时针旋转 43 故由定理知不等价的着色方案数为 44 6 把1到10这10个数随机地写成一个圆圈 证明 必存在某3个相邻数之和大于或等于17 45 这表明圆圈的10个数中 必存在三个连续的数 其和大于或等于17 46 7 证明 如果从S 1 3 5 7 599 中任选101个数 在所选出的数中总存在2个数 它们之间最多差4 证把S中的数分成100组 则每组中的数之间的差均不超过4 从S中任取101个数 由抽屉原理 至少有2个数在同一组 它们之差不超过4 47 如果集合与集合没有相同元素 则它们对应的两组人即为所求 如果这两个集合有相同元素 则在等式 两端同时减去这些相同元素的值 等式仍成立 等式中两端余下的各项对应的人就是所求两组年龄和相同的人