组合数学初步.ppt

上传人:99****p 文档编号:1589508 上传时间:2019-03-07 格式:PPT 页数:87 大小:466KB
下载 相关 举报
组合数学初步.ppt_第1页
第1页 / 共87页
组合数学初步.ppt_第2页
第2页 / 共87页
组合数学初步.ppt_第3页
第3页 / 共87页
组合数学初步.ppt_第4页
第4页 / 共87页
组合数学初步.ppt_第5页
第5页 / 共87页
点击查看更多>>
资源描述

1、组合数学组合数学简介 组合数学起源于古老的数学娱乐和游戏。而在当今社会中同样发挥着重要的作用。 组合数学研究一个集合的物体进行满足一些规则的排列。具体的说,组合数学研究的是这些排列的存在性、计数和分类。 在 ACM/ICPC中用到的组合数学知识有:一一对应原理、加法乘法原理、多重集排列和组合、排列生成、递推关系、母函数、鸽巢原理、容斥原理、群和置换群、贝恩塞特引理和波利亚定理一一对应原理 “ 一一对应 ” 概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。 如我们说 A集合有 n个元素 |A|=n, 无非是建立了将 A中元与 1,n元一一对应的关系。 在组合计数时往往借助于一一对应实

2、现模型转换。 比如要对 A集合计数,但直接计数有困难,于是可设法构造一易于计数的 B, 使得A与 B一一对应。 例 在 100名选手之间进行淘汰赛 (即一场的比赛结果,失败者退出比赛 ),最后产生一名冠军,问要举行几场比赛?一一对应例 含有 n个元素的集合的所有子集个数为 2n解 一种常见的思路是按轮计场,费事。另一种思路是 淘汰的选手 与 比赛 (按场计 )集 一一对应 。 99场比赛。一一对应例:求集合 1,2,n 的不含相邻整数的k元子集的个数。分析:每个满足条件的 k元子集都和一个 01有序串对应,且这个有序串没有两 1相邻。这样的串含有 k个 1,每个 1前面的 0的个数是不同,又与

3、 0,1, n-k中选 k个不同的元素对应。所以结果 =c(n-k+1,k) 某机要部门安装了电子锁。 M(M8)工作人员每人发一张磁卡,卡上有开锁的密码特征。为了保证安全,规定至少要有 N(N5)个人同时使用各自的磁卡才能将所打开。现在需要计算一下,电子锁至少要有多少种特征,每个人的磁卡上至少有几个特征。一一对应(下午讨论)加法乘法原理 加法原理 把事情分成 N类,每类有 Ci种做法,则该事情共有 C1+C2+CN 种做法 乘法原理 把事情分成 N步,每步有 Ci种做法,则该事情共有 C1*C2*CN 种做法 例 某班选修企业管理的有 18 人,不选的有 10 人,则该班共有 18 + 10

4、 = 28 人。 例 北京每天直达上海的客车有 5 次,客机有 3 次, 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。例 某种字符串由两个字符组成,第一个字符可选自 a, b, c, d, e, 第二个字符可选自 1, 2, 3,则这种字符串共有 5 3 = 15 个。例 从 A到 B有三条道路,从 B到 C有两条道路,则从 A经 B到 C有 32=6 条道路。加法乘法原理的应用 单色三角形(来源于 POI)给定空间里的 n个点,其中没有三个点共线。每两个点用红色或兰色线段连接。如果一个三角形的三条边同色,则称这个三角形是单色三角形。对于给定红色线段的列表,希望能找出单色三角形的个数。

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 课件讲义

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。