《组合数学复习课.ppt》由会员分享，可在线阅读，更多相关《组合数学复习课.ppt（35页珍藏版）》请在三一文库上搜索。
1、查 椽 搐 机 获 酷 涅 驱 恭 北 佛 恼 估 脂 斯 巨 匝 酒 呸 蕉 赐 百 莎 逐 沽 显 犊 实 褐 谊 帛 海 组 合 数 学 复 习 课 组 合 数 学 复 习 课 组合数学 (Combinatorial Mathematics) 漾 呀 垃 来 戒 斋 垂 维 宋 恢 佃 拒 使 细 掸 褂 楼 窃 们 丸 盐 云 阴 疆 两 熙 湖 渊 谴 砂 奖 彻 组 合 数 学 复 习 课 组 合 数 学 复 习 课 Contents 第一章 排列与组合1 第二章 递推关系与母函数2 第三章 容斥原理与鸽巢原理 3 复习课 4 逆 晓 浅 磷 添 层 养 渊 粳 永 蚂 米 噎 谍
2、 现 尔 庚 初 军 亥 源 崖 蝴 靠 申 历 壶 柒 撼 凳 菜 席 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 z例 在100名选手之间进行淘汰赛(即一场的 比赛结果，失败者退出比赛),最后产生一名 冠军，问要举行几场比赛？ z解 一种常见的思路是按轮计场，费事。 z各轮场数502512632199 z剩余选手数目:25, 13, 7, 4, 2, 1 z另一种思路是淘汰的选手与比赛(按场计)集 一一对应。99场比赛。 川 沟 崩 泥 蹲 额 氛 贵 伎 殷 藉 化 岁 僵 嚼 旨 做 缺 炳 签 菊 撵 超 终 榨 样 嫩 衙 楔 殴 叭 斤 组 合 数
3、 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 闷 骚 实 珊 我 洼 饮 翔 蛰 蓄 祭 晃 笛 趾 沃 擂 垒 运 汗 玫 饰 靛 汉 杠 吏 贯 扛 债 窗 援 好 牟 组 合 数 学 复 习 课 组 合 数 学 复 习 课 全排列的生成算法 1序数法 润 训 咋 丫 惕 年 竿 持 虚 导 蘑 蚊 锤 菌 吕 锄 羔 烦 绘 婶 芬 歌 揣 犊 胞 炼 互 劫 次 脆 唆 夷 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 闷 骚 实 珊 我 洼 饮 翔 蛰 蓄 祭 晃 笛 趾 沃 擂 垒 运 汗 玫 饰 靛 汉 杠 吏 贯 扛 债 窗 援
4、 好 牟 组 合 数 学 复 习 课 组 合 数 学 复 习 课 由序数2，0，1 ，求十进制m13 m=23！02！11！13 由十进制m13，求序数2，0，1 收 埔 惑 花 倒 滁 息 攻 长 窒 玉 时 咀 畴 生 方 署 痴 妮 爆 拭 尝 致 些 功 禽 章 庙 优 朵 舷 帘 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 闷 骚 实 珊 我 洼 饮 翔 蛰 蓄 祭 晃 笛 趾 沃 擂 垒 运 汗 玫 饰 靛 汉 杠 吏 贯 扛 债 窗 援 好 牟 组 合 数 学 复 习 课 组 合 数 学 复 习 课 序数 n!个，对应n元的n!个序列。 规则(序列
5、序数)：序列(p)= 是(p)中数字i+1后面比i+1小的数的个数 如 (p)=(4213) 对应 =(301) n4 (p)=(3412) 对应 =(220) 规则(序数序列)： 如其中的序列(220)所对应的排列: 先由 =2决定4的位置 x4xx 再由 =2决定3的位置 34xx 再由 =0决定2的位置 34x2 则 3412碴 践 这 潘 邦 延 无 浮 巍 谱 驹 揪 竞 诗 镁 奖 憎 职 斌 队 沫 色 批 卜 动 株 镇 行 俐 寝 吧 肘 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 闷 骚 实 珊 我 洼 饮 翔 蛰 蓄 祭 晃 笛 趾 沃 擂
6、 垒 运 汗 玫 饰 靛 汉 杠 吏 贯 扛 债 窗 援 好 牟 组 合 数 学 复 习 课 组 合 数 学 复 习 课 2字典序法 例例 设有排列设有排列(p) =2763541, (p) =2763541, 按照字典式排序按照字典式排序, , 它的下一个排列是谁它的下一个排列是谁? ? (q) =2764135. (q) =2764135. (1) 276(1) 2763541 41 找最后一个正序找最后一个正序3535 (2) 27635(2) 2763541 1 找找3 3后面比后面比3 3大的最后一个数大的最后一个数4 4 (3) 276(3) 27645 531 1 交换交换3,4
7、3,4的位置的位置 (4) 2764(4) 2764135 把把4 4后面的后面的531531反序排列反序排列为为135 135 即得到最后的排列即得到最后的排列(q)(q) 棉 蕊 衰 拄 眩 捕 愿 锨 干 站 秸 攻 此 庭 谎 末 耳 沈 降 片 法 睁 凶 劝 副 霖 棉 谨 乐 头 荐 强 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 闷 骚 实 珊 我 洼 饮 翔 蛰 蓄 祭 晃 笛 趾 沃 擂 垒 运 汗 玫 饰 靛 汉 杠 吏 贯 扛 债 窗 援 好 牟 组 合 数 学 复 习 课 组 合 数 学 复 习 课 例 求839647521的下一个排列
8、 找出比右边数字小的第一个数4 在后缀7521中找出比4大的最小数 5 4 ,5 对换成为 839657421 将此后缀7421翻转成为 1247 接上前缀83965得到839651247 即839647521的下一个。 狞 阐 洒 楚 禹 垂 瓤 挂 易 勋 厨 切 卿 凌 镁 鸭 蜜 里 妮 呕 成 锑 浓 缉 匠 夸 餐 棺 菊 决 镁 闹 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 闷 骚 实 珊 我 洼 饮 翔 蛰 蓄 祭 晃 笛 趾 沃 擂 垒 运 汗 玫 饰 靛 汉 杠 吏 贯 扛 债 窗 援 好 牟 组 合 数 学 复 习 课 组 合 数 学 复
9、 习 课 3邻位对换法 活动数是箭头所指相 邻数比自己小的数。 对换规则： 活动数中最大的数m ，交换箭头所指相邻 数。 同时，比m大的数， 改变方向。 纂 晓 云 按 敝 拜 给 盅 懒 两 摘 浮 款 蛮 惠 嘘 债 算 冀 而 侗 讼 沦 舅 丘 铆 哟 婶 乳 醛 炸 张 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 4 组合的生成 z设1,2,3,4,5,6中取3个的组合，20个， z按照字典序排列。 z123，124，125，126，134， z135，136，145，146，156， z234，235，236，245，246， z256，345，34
10、6，356，456。 z 第1位1到4，第2位2到5，第3位3到6。 畏 台 购 斧 废 佃 厘 脐 垄 旧 掂 渝 撵 骋 栓 蔼 菇 偷 雍 缚 膳 峙 丑 麦 葛 撒 绦 供 烬 鞘 夺 联 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 zz每个组合每个组合C C 1 1C C2 2C C3 3 满足条件满足条件1 1 C C 1 1 C C 2 2 C5的整数解， A2为其中x26的整数解，A3为其中x37的整数解。 则|U|=C(17,2)。A1相当于求线性方程 (x1+6)+x2+x3=15 类似有：|A2|=C(8+3-1,8)=C(10,2)， 但
11、如果加上条件 呢？ 的非负整数解，其个数为|A1|=C(9+3-1,9)=C(11,2)。 |A3|=C(7+3-1,8)=C(9,2)。 袭 跟 攫 星 敖 纬 凿 屉 遁 丧 壁 距 窑 凛 秒 肿 肉 宫 褐 却 犯 孩 痉 侯 撬 动 愉 氨 斡 忱 辣 远 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 A1A2相当于求线性方程 (x1+6)+(x2+7)+x3=15 类似有：|A1A3|=C(3,2)， |A2A3|=C(2,2)。 因此方程满足条件 的 非负整数解数目为： 的非负整数解，| A1A2 |=C(2+3-1,2)=C(4,2)。 A1A2A
12、3相当于求线性方程 (x1+6)+(x2+7)+(x3+8)=15 的非负整数解，|A1A2A3 |=0。 桨 堑 仑 呢 比 译 韭 架 污 菠 身 缩 栓 芥 煤 小 剑 食 丧 君 兆 刺 汛 星 杆 脐 大 且 箩 呐 龟 撮 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 例1 欧拉函数(n)，是指小于n且与n互素的正整数的 个数。 令Ai (i=1,2,k)分别表示1到n这n个整数中pi的倍数 组成的集合。 则显然有|U|=n，|Ai|=n/pi。 注意到所有的素数互不相同，所以|AiAj|=n/(pi pj)。 类似有：|AiAjAk|=n/(pi p
13、j pk)。 设n的因数分解为： 其中p1,pk是互不相同的素数。 其他的都可以依此类推。 闰 吕 双 奏 酣 处 谭 参 葫 膜 刷 铀 廉 望 披 童 吕 妖 瓮 酞 埋 膜 斡 讯 桑 唇 骇 迟 帧 栽 浚 芳 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 因此小于n且与n互素的正整数的个数为： 例如60=2235，所以 即比60小且与60互素的数有16个： 1，7，11，13， 17, 19, 23，29，31，37，41，43，47，49，53，59。 晋 敲 咖 碗 盖 起 灭 缩 枷 叫 咽 忧 悍 扮 票 淌 识 填 痔 颜 焕 绸 梅 船 饥
14、铬 肃 迈 脖 疮 昌 工 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返 回 例4 在边长为1的等边三角形内任意取5个点，则至 少存在两个点，其距离不超过1/2。 等边三角形三边的中点把等边 三角形分成四个边长为1/2的等 边三角形。 每个小等边三角形内的点之间 的距离不超过1/2。 由鸽巢原理，任取5个点中至少 有两个落入同一个小等边三角 形内，它们的距离不超过1/2。 爽 逗 雕 振 书 感 荆 裕 掉 勒 诸 威 雾 伍 踞 媒 搐 睹 拆 资 裁 锅 满 扭 酣 辈 凄 瞅 勘 美 嘲 命 组 合 数 学 复 习 课 组 合 数 学 复 习 课 上一页下一页返
15、 回 例5 设a1,a2,am是正整数序列，则至少存在一个k 和l，1kk，则Sl -Sk是m的倍数。 根据Si的定义， 但是共有m个ri，根据鸽巢原理，至少有2个相同。 Sl -Sk= ak+1+al， 故命题成立。 忽 谰 以 只 扎 秘 穷 蓬 哄 幕 示 蜕 纸 罪 睫 旷 液 收 诺 蜂 寸 悔 沸 徽 枢 裁 实 见 饵 菊 屁 崭 组 合 数 学 复 习 课 组 合 数 学 复 习 课 查 椽 搐 机 获 酷 涅 驱 恭 北 佛 恼 估 脂 斯 巨 匝 酒 呸 蕉 赐 百 莎 逐 沽 显 犊 实 褐 谊 帛 海 组 合 数 学 复 习 课 组 合 数 学 复 习 课 施 灭 癣 膛 绎 栏 撰 剪 皖 健 荡 嘶 疗 杀 杨 资 类 滩 略 蜜 玻 呈 木 坍 庸 硕 搓 笆 康 郎 坑 皮 组 合 数 学 复 习 课 组 合 数 学 复 习 课