史灵生《离散数学》清华大学-D02Tools.pdfVIP

下载本文档

23
0
约2.16万字
约 44页
2018-05-13 发布于浙江
举报
版权申诉

史灵生《离散数学》清华大学-D02Tools.pdf

1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
4、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
5、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
6、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
7、VIP文档为合作方或网友上传，每下载1次，网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

Discrete Mathematics Lecture 2 Combinatorial Tools 1 Contents • Induction (omitted) • Estimation (Stirling’s formula) • Inclusion-Exclusion (容斥原理) • Pigeonholes (鸽巢原理) • The Twin Paradox 2 2.2 阶乘在离散数学中经常遇到n!计算, 随着n 的增大, 结果增长迅速。那么n!到底有多大？ 2n-1 ≤ n! ≤ nn-1 Stirling公式给出一个求n!的近似公式, 它对从事计算和理论分析都是有意义的. Stirling公式: n! ~ 2n n / e n . n (左边取对数得：∑ln n ≈∫ ln x dx = nlnn-n) 1 3  相对误差： n ! lim 1. n n 2n(n / e)  绝对误差： lim n! 2n n / e n   . n    /doc/5503277.html 4 2.3 容斥原理一．引言二．容斥原理三．应用实例  错排问题  有限制的排列  相对禁位排列 5 引言  容斥原理是组合数学中的一个重要原理,它在计数问题中占有很重要地位.  容斥原理所研究的问题是与若干有限集的交、并或差有关的计数.  在实际工作中, 有时要计算具有某种性质的元素个数. 例1 某单位举办一个外语培训班, 开设英语, 法语两门课. 6 设U为该单位所有人集合, A ,B分别为学英语, 法语人的集合, 如图所示. 学两门外语的人数为|AB |, 学一门外语的人数为|AB |-|AB |, 没参加学习的人数为|U|-|AB |. 7 在一些计数问题中, 经常遇到间接计算一个集合中具有某种性质的元素个数比起直接计算来得简单. 例2 计算1到700之间不能被7整除的整数个数. 直接计算相当麻烦,间接计算非常容易. 先计算