组合数学概念简介.pptx

《组合数学概念简介.pptx》由会员分享，可在线阅读，更多相关《组合数学概念简介.pptx（18页珍藏版）》请在装配图网上搜索。

1、1 C o m b i n a t o r i c s马 昱 春第 一 章排 列 组 合 说 说 数 数 这 件 事 2 3 第 一 章 排 列 组 合1.1 加 法 法 则 与 乘 法 法 则分 类 计 数 和 分 步 计 数从 甲 地 到 乙 地 ， 可 以 乘 火 车 ， 也 可 以 乘 汽 车， 一 天 中 ， 火 车 有 3班 ， 汽 车 有 2班 那 么 一天 中 ， 乘 坐 这 些 交 通 工 具 从 甲 地 到 乙 地 共 有多 少 种 不 同 的 走 法 ？解 答 ： 3 2 5 种 不 同 的 走 法从 甲 地 到 乙 地 ， 要 从 甲 地 选 乘 火 车 到 丙 地 ，

2、 再于 次 日 从 丙 地 乘 汽 车 到 乙 地 一 天 中 ， 火 车 有3班 ， 汽 车 有 2班 那 么 两 天 中 ， 从 甲 地 到 乙 地共 有 多 少 种 不 同 的 走 法 ？解 答 ： 共 有 3 2 6 种 不 同 的 走 法 4 1.1 加 法 法 则 与 乘 法 法 则 加 法 法 则 The Sum Rule设 事 件 A有 m种 产 生 方式 ， 事 件 B有 n种 产 生 方 式 ， 则 事 件 A或 B之 一有 m+n种 产 生 方 式 。集 合 论 语 言 ：若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。 例 某

3、班 选 修 企 业 管 理 的 有 18 人 ， 不 选的 有 10 人 ， 则 该 班 共 有 18 + 10 = 28 人 。 5 1.1 加 法 法 则 与 乘 法 法 则 乘 法 法 则 The Product Rule 设 事 件 A有 m种产 生 方 式 ， 事 件 B有 n种 产 生 方 式 ， 则 事 件 A与B有 m n种 产 生 方 式 。集 合 论 语 言 ：若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。例 某 种 字 符 串 由 两 个 字 符 组 成 ， 第 一 个 字 符可 选 自 a， b，

4、c， d， e， 第 二 个 字 符 可 选 自 1， 2， 3， 则 这 种 字 符 串 共 有 5 3 = 15 个 。 6 1.1 加 法 法 则 与 乘 法 法 则 例 某 种 样 式 的 运 动 服 的 着 色 由 底 色 和 装 饰条 纹 的 颜 色 配 成 。 底 色 可 选 红 、 蓝 、 橙 、 黄 ，条 纹 色 可 选 黑 、 白 ， 则 共 有 42 = 8种 着 色方 案 。 若 此 例 改 成 底 色 和 条 纹 都 用 红 、 蓝 、 橙 、 黄四 种 颜 色 的 话 ， 则 ， 方 案 数 就 不 是 4 4 = 16， 而 只 有 4 3 = 12 种 。 在

5、乘 法 法 则 中 要 注 意 事 件 A 和 事 件 B 的 相互 独 立 性 。 7 1.1 加 法 法 则 与 乘 法 法 则例 1)求 小 于 10000的 含 1的 正 整 数 的 个 数 2)求 小 于 10000的 含 0的 正 整 数 的 个 数1)小 于 10000的 不 含 1的 正 整 数 可 看 做 4位 数 ,但 0000除 外 . 故 有 9 9 9 9 1 6560个 . 含 1的 有 ： 9999 6560=3439个另 : 全 部 4位 数 有 10 4 个 ,不 含 1的 四 位 数 有 94 个 , 含 1的 4位 数 为 两 个 的 差 : 104 94

6、 = 3439个 8 2)求 小 于 10000的 含 0的 正 整 数 的 个 数“ 含 0” 和 “ 含 1” 是 否 可 以 直 接 套 用 ？0019含 1但 不 含 0。 在 组 合 的 习 题 中 有 许 多 类 似 的 隐 含 的规 定 ， 要 特 别 留 神 。 不 含 0的 1位 数 有 9个 ， 2位 数 有 92个 ， 3位数 有 93个 ， 4位 数 有 94个 不 含 0小 于 10000的 正 整 数 有 9 + 92 + 93 + 94 =(95 1)/(9 1)=7380个含 0小 于 10000的 正 整 数 有 9999 7380=2619个 9 1.2排

7、列 与 组 合定 义 排 列 Permutation从 n个 不 同 的 元 素 中 ，取 r个 不 重 复 的 元 素 ， 按 次 序 排 列 ， 称 为 从 n个中 取 r个 的 无 重 排 列 。 排 列 的 个 数 用 P(n,r)表 示 ，或 者 。 当 r=n时 称 为 全 排 列 。 一 般 不 说 可 重即 无 重 。定 义 组 合 Combination从 n个 不 同 元 素 中 取 r个 不 重 复 的 元 素 组 成 一 个 子 集 ， 而 不 考 虑 其 元素 的 顺 序 ， 称 为 从 n个 中 取 r个 的 无 重 组 合 。组 合 的 个 数 用 C(n,r)表

8、 示 或 者rnP rnC 10 1.2排 列 与 组 合从 n个 中 取 r个 的 排 列 的 典 型 例 子 是 从 n个 不同 的 球 中 ,取 出 r个 ,放 入 r个 不 同 的 盒 子 里 ,每盒 1个 。 第 1个 盒 子 有 n种 选 择 ， 第 2个 有 n-1种选 择 ， ， 第 r个 有 n-r+1种 选 择 。故 有 P(n,r)=n(n-1)(n-r+1) = 有 时 也 用 nr记 n(n-1)(n-r+1)全 排 列 ： P(n,n) = n! )!( !rn n 11 1.2排 列 与 组 合若 球 不 同 ， 盒 子 相 同 ， 则 是 从 n个 中 取 r个

9、 的 组合 的 模 型 。若 放 入 盒 子 后 再 将 盒 子 标 号 区 别 ， 则 又 回 到 排列 模 型 。 每 一 个 组 合 可 有 r!个 标 号 方 案 。故 有 C(n,r)r!=P(n,r)=C(n,r)=P(n,r)/r!=nr/r!= = nr )!(! ! rnr n )!( !rn n 12 排 列 组 合 问 题 的 来 源 排 列 组 合 问 题 ， 最 早 见 于 我 国 的 易 经 一 书 所 谓 “ 四 象 ” 就 是 每 次 取 两 个 爻 (yo )的 排 列 ， “ 八 卦 ” 是 每 次 取三 个 爻 的 排 列 在 汉 代 数 学 家 徐 岳

10、的 数 术 记 遗 （ 公 元 2世 纪 ） 中 ， 也 曾记 载 有 与 占 卜 有 关 的 “ 八 卦 算 ” ， 即 把 卦 按 不 同 的 方 法 在八 个 方 位 中 排 列 起 来 它 与 “ 八 个 人 围 一 张 圆 桌 而 坐 ， 问 有 多 少 种 不 同 坐 法 ” 这 一 典 型 的排 列 问 题 类 似 11世 纪 时 ， 邵 雍 还 进 一 步 研 究 了 六 十 四 卦 的 排 列 问题 唐 朝 僧 人 一 行 曾 经 研 究 过 围 棋 布 局 的 总 数 问 题 古 代 的 棋盘 共 有 17路 ， 289个 点 ， 后 来 发 展 到 19路 361个 点

11、一 行 曾计 算 过 一 切 可 能 摆 出 的 棋 局 总 数 17世 纪 ， 北 宋 时 期 沈 括 在 梦 溪 笔 谈 中 ， 进 一 步 讨 论 了围 棋 布 局 总 数 问 题 他 利 用 一 些 排 列 、 组 合 的 办 法 对 一 行的 计 算 作 了 分 析 沈 括 指 出 ， 当 361个 棋 子 全 用 上 时 ， 棋 局 总 数 达 到 1000052 的 数 量 级 13 1.2排 列 与 组 合例 有 5本 不 同 的 日 文 书 ， 7本 不 同 的 英文 书 ， 10本 不 同 的 中 文 书 。1)取 2本 不 同 文 字 的 书 ； 5 7+5 10+7 1

12、0=155;2)取 2本 相 同 文 字 的 书 ；C(5,2)+C(7,2)+C(10,2) =10+21+45=76;3)任 取 两 本 书 155+76=231= C(5+7+10,2) 14 1.2排 列 与 组 合 多 重 全 排 列 ：2个 a, 3个 b， 4个 c， 其 多 重 全 排 列 记 为加 上 下 标 以 区 别 a1a2b1b2b3c1c2c3c4 a下 标 排 列 有 2!， b下 标 排 列 有 3!， c下 标 排列 有 4！ 432 9!9!4!3!2432 9 !4!3!2 !9432 9 15 1.2排 列 与 组 合 求 r1个 1， r2个 2， ，

13、 rt个 t的 排 列 数 ， 设r1+r2+rt=n,设 此 排 列 数 为 P(n;r1,r2,rt) 对 1， 2， ， t分 别 加 下 标 ， 得 到P(n;r1,r2,rt)r1!r2!rt! = n! P(n;r1,r2,rt) = 多 项 式 展 开 nk knknk knkn baknCbaknk nba 00 ),()!(! !)( nraarr naaa irttrtnt .!.!).( 11121 !.! !21 trrr n trrr n.21= 16 1.2排 列 与 组 合 圆 排 列 ： 从 n个 中 取 r个 的 圆 排 列 的 排 列 数 为 P(n,r)/r , 2rn 以 4个 元 素 为 例 12 4 3 1234 12 4 3 2341 12 4 3 3412 12 4 3 4123 思 考 题 ： 手 机 密 码 安 全 吗 ？ 10 10 10 10 =10000 17？ 手 机 密 码 安 全 吗 ？ 18