数学毕业论文定稿(排列组合及相关算法)

《数学毕业论文定稿(排列组合及相关算法)》由会员分享，可在线阅读，更多相关《数学毕业论文定稿(排列组合及相关算法)（12页珍藏版）》请在金锄头文库上搜索。

1、安 庆 师 范 学 院 数 学 与 计 算 科 学 学 院 2011届 毕 业 论 文共 12页第 1页排 列 组 合 及 相 关 算 法作 者 ： 潘 祥 指 导 老 师 ： 张 胜摘 要 本 论 文 首 先 简 单 的 介 绍 了 排 列 及 组 合 的 定 义 ， 并 且 给 出 一 些 例 子 加 以 说 明 ， 之 后 给 出 了 一 些 关于 排 列 和 组 合 的 相 关 定 理 及 证 明 ， 接 着 给 出 了 大 量 的 例 子 去 说 明 定 理 的 正 确 性 ， 同 时 还 介 绍 了 关 于 排 列 和 组合 问 题 中 的 相 关 算 法 .在 本 论 文 中 给

2、 出 了 排 列 和 组 合 算 法 ， 同 时 用 产 生 的 算 法 将 相 关 的 排 列 组 合 的 例 子 进 行 了二 次 计 算 ， 证 明 了 算 法 的 正 确 性 .关 键 词 排 列 组 合 算 法1 排 列四 个 候 选 人 Zeke,Yung,Xeno 和 Wilma 竞 选 同 一 个 职 务 .为 了 使 选 票 上 人 名 的 位 置 不 影 响选 民 的 选 举 ， 有 必 要 在 印 制 选 票 时 以 各 种 可 能 的 顺 序 排 列 名 字 .那 么 应 该 有 多 少 种 不 同 的 选票 ？可 以 运 用 乘 法 原 理 .一 张 选 票 可 以

3、由 连 续 的 四 步 来 构 造 ： 选 择 第 一 个 名 字 ， 选 择 第 二 个 名字 ， 选 择 第 三 个 名 字 ， 选 择 第 四 个 名 字 .第 一 个 名 字 有 4种 选 择 方 法 .一 旦 第 一 个 名 字 已 选 好 ，第 二 个 名 字 有 3 种 选 择 方 法 .一 旦 第 二 个 名 字 已 选 好 ， 第 三 个 名 字 有 2 种 选 择 方 法 .一 旦 第 三个 名 字 已 选 好 ， 第 四 个 名 字 只 有 1种 选 择 方 法 .根 据 乘 法 原 理 ， 选 票 的 数 目 为 4 3 2 1=24种 . 事 物 （ 如 选 票 上

4、的 名 字 ） 的 有 序 化 ， 叫 做 排 列 .定 义 1.1n个 不 同 元 素 1 2, , , nx x x的 一 个 排 列 就 是 n个 元 素 1 2, , , nx x x的 一 个 次 序 .例 1.1三 个 元 素 有 六 种 排 列 .如 果 元 素 表 示 为 A， B， C， 则 六 种 排 列 为 ：ABC， ACB， BAC， BCA， CAB， CBA.我 们 发 现 在 一 张 选 票 上 有 24 种 方 法 排 列 四 人 候 选 人 的 名 字 ； 于 是 四 个 对 象 有 24 种 排 列 .我 们 用 来 计 算 包 含 四 个 名 字 的 不

5、 同 选 票 的 数 目 所 采 用 的 方 法 可 以 用 来 得 到 一 个 关 于 n 个元 素 排 列 数 的 公 式 .n=4时 的 定 理 证 明 由 图 1.1列 出 .B A D C选 择 第 选 择 第 选 择 第 选 择 第一 元 素 二 元 素 三 元 素 四 元 素图 1.1 定 理 1当 n=4时 的 证 明 .ABCD 的 一 个 排 列 由 连 续 的 选 择 第 一 个 元 素 ，第 二 个 元 素 ， 然 后 第 三 个 元 素 ， 最 后 第 四 个 元 素 来 构 成 的定 理 1n个 元 素 有 n！ 个 排 列 .证 明 ： 运 用 乘 法 原 理 .

6、n 个 元 素 的 一 个 排 列 可 以 由 连 续 的 n 步 构 成 ： 选 择 第 一 个 元 素 ， 选 择 第二 个 元 素 ， 选 择 最 后 一 个 元 素 .第 一 个 元 素 由 n 种 选 择 方 法 .一 旦 第 一 个 元 素 已 选 好 ， 第 二安 庆 师 范 学 院 数 学 与 计 算 科 学 学 院 2011届 毕 业 论 文共 12页第 2页个 元 素 有 n-1 种 方 法 .一 旦 第 二 个 元 素 已 选 好 ， 第 三 个 元 素 有 n-2种 选 择 方 法 ， 等 等 .根 据 乘 法 原 理 ， n个 元 素 有 n（ n-1） （ n-2）

7、 2,1=n！ 个 排 列 .例 1.210个 元 素 有 10！ =10 9 8 7 6 5 4 3 2 1=3,628,800个 排 列 .例 1.3字 母 ABCDEF的 排 列 中 有 多 少 个 包 含 子 串 DEF？为 了 保 证 DEF的 出 现 在 子 串 中 ， 这 三 个 字 母 必 须 连 在 一 起 且 保 持 这 个 顺 序 .剩 余 的 字 母 A,B和 C可 以 放 在 任 意 的 位 置 .可 以 把 构 造 包 含 子 串 DEF的 ABCDEF的 排 列 看 作 四 个 标 号 DEF， A,B,C的 排 列 （ 见 图 2） .由 定 理 1， 四 个

8、对 象 有 4！ 个 排 列 .于 是 包 含 子 串 DEF 的 ABCDEF 的 排 列 数 为4！ =24.图 2例 1.4ABCDEF 的 包 含 字 母 DEF任 意 顺 序 的 排 列 有 多 少 个 ？我 们 可 以 通 过 两 步 来 解 决 这 个 问 题 ： 选 择 字 母 DEEF 的 一 个 次 序 ， 构 造 ABCDEF 的 一 个包 含 DEF 给 定 次 序 的 排 列 .有 定 理 1， 第 一 步 有 3！ =6 种 方 法 ， 根 据 例 3， 第 二 步 可 以 有 24种方 法 .根 据 乘 法 原 理 ， ABCDEF的 包 含 字 母 DEF的 任

9、 意 顺 序 的 排 列 数 为 6 24=144例 1.5六 个 人 围 坐 在 圆 桌 前 有 多 少 种 坐 法 ？ 如 果 一 种 坐 法 可 以 由 另 一 种 坐 法 的 每 个 人 都 逆 时 针移 动 n 个 位 置 而 得 到 ， 则 这 两 种 坐 法 被 认 为 是 相 同 的 .F EB AD C我 们 用 A,B,C,D,E,F表 示 六 个 人 .因 为 由 旋 转 而 得 到 的 坐 法 认 为 是 相 同 的 ， 我 们 可 以 让 A任 意 坐 .安 排 剩 余 五 个 人 ， 我 们 可 以 让 他 们 从 A 逆 时 针 排 序 .例 如 ， 排 列 CD

10、BEF 用 相 邻 的 字 母定 义 了 一 种 坐 法 .因 为 五 个 元 素 有 5！ =120种 排 列 ， 则 六 个 人 围 绕 一 张 圆 桌 可 以 有 120种 坐 法 .同 样 可 以 得 到 结 论 ： n 个 人 围 绕 一 张 圆 桌 可 以 有 （ n-1） ！ 种 坐 法 .有 时 我 们 要 考 虑 从 n 个 个 给定 的 元 素 中 选 出 r 个 元 素 的 次 序 .这 种 次 序 叫 做 r-排 列 .定 义 2n 个 不 同 元 素 1 2, , , nx x x的 一 个 r-排 列 就 是 1 2, , , nx x x的 一 个 r-元 子 集

11、 的 排 序 .n个 不 同 元 素 的 r-排 列 数 记 为 P（ n， r） .例 1.6a， b， c的 2-排 列 有 ab， ba， ca.在 定 义 2 中 ， 如 果 r=n， 我 们 得 到 全 部 n 个 元 素 的 一 个 次 序 .这 样 n 个 元 素 的 排 列 就 是 我们 以 前 所 叫 的 排 列 .由 定 理 1知 p（ n， n） =n！ .当 rn时 n 个 元 素 的 r-排 列 数DEF A B C安 庆 师 范 学 院 数 学 与 计 算 科 学 学 院 2011届 毕 业 论 文共 12页第 3页p(n,r)可 以 由 定 理 1 的 证 明 而

12、 得 到 .当 n=6， r=3时 定 理 的 证 明 由 图 3 表 示 .C A B选 择 第 选 择 第 选 择 第一 元 素 二 元 素 三 元 素图 3 当 n=6， r=3时 定 理 3的 证 明 .ABCDEF 的 一 个 r-排 列由 连 续 的 选 择 第 一 个 元 素 ， 然 后 第 二 个 元 素 ， 最 后 第 三 个 元 素 构 成定 理 3 具 有 n 个 不 同 元 素 的 集 合 的 r-排 列 数 为P（ n， r） =n（ n-1） （ n-2） （ n-r+1） ， r=n.证 明 : 我 们 想 计 算 从 一 个 n 元 集 合 中 选 出 r个 元

13、 素 的 排 序 方 法 数 .第 一 个 元 素 有 n种 选 择方 法 .一 旦 第 一 个 元 素 已 选 好 ， 第 二 个 元 素 有 n-1中 选 择 方 法 .继 续 选 择 元 素 直 到 已 经 选择 了 第 r-1个 元 素 ， 该 选 第 r 个 元 素 了 .最 后 这 个 元 素 可 以 有 n-r+1 种 选 择 方 法 .根 据 乘法 原 理 ， n 个 不 同 对 象 的 r-排 列 数 为 n（ n-1） （ n-2） （ n-r+1） .例 1.7根 据 定 理 3， X=a,b,c的 2 排 列 数 为 p（ 3， 2） =3 2=6.这 六 个 2 排

14、列 为 ab,ac,ba,bc,ca,cb.例 1.8从 10个 人 中 选 择 一 个 主 席 ， 副 主 席 ， 秘 书 和 会 计 有 多 少 种 方 法 ？我 们 需 要 计 算 从 十 个 人 中 选 择 四 个 人 的 次 序 数 .因 为 是 一 个 有 次 序 的 选 择 ， 主 席 （ 第 选 ） ，副 主 席 （ 第 二 选 ） ， 秘 书 （ 第 三 选 ） ， 会 计 （ 第 四 选 ） .根 据 定 理 3，解 为p（ 10， 4） =10 9 8 7=5040.我 们 也 可 以 直 接 用 乘 法 原 理 来 解 决 例 1.8.我 们 也 可 以 把 p(n,r

15、)写 成 因 子 式 的 形 式 ：P（ n,r） =n(n-1) (n-1) (n-r+1)n(n-1) (n-1) (n-r+1)(n-r) 2.1 n!= =(n-r) 2.1 (n-r)! （ 1）例 1.9用 式 （ 1） 我 们 可 以 将 例 1.8的 结 果 重 写 为 !6!10)!410( !10)4,10( p例 1.10七 个 不 同 的 火 星 人 和 五 个 不 同 的 月 球 人 排 队 等 候 ， 如 果 不 能 有 两 个 月 球 人 站 在 一 起 ， 有安 庆 师 范 学 院 数 学 与 计 算 科 学 学 院 2011届 毕 业 论 文共 12页第 4页

16、多 少 种 方 法 ？我 们 可 以 用 两 步 将 火 星 人 和 月 球 人 排 列 起 来 ： 排 列 火 星 人 ， 排 列 月 球 人 .火 星 人 有 7！ =5040种 排 列 方 法 ， 一 旦 我 们 已 经 排 好 了 火 星 人 ， 因 为 不 能 有 两 个 月 球 人 站 在 一 起 ， 月 球 人 有 八 个可 能 的 位 置 可 以 站 ： -M1-M2-M3-M4-M5-M6-M7-因 此 月 球 人 有 P（ 8， 5） =8 7 6 5 4=6720种 排 列 方 法 .根 据 乘 法 原 理 ， 七 个 不 同 的 火星 人 和 五 个 不 同 的 月 球 人 排 队 等 候 ， 如 果 不 能 有 两 个 月 球 人 站 在 一 起 ， 有 5040 6720=33， 868，800种 方 法 .2 组 合不 考 虑 顺 序 的 对 象 的 选 取 叫 做 组 合 .定 义 1给 定 一 个 包 含 n个 不 同 元