页数：43页文件大小：395.8 KB来源： 离散数学ppt课件
本课件围绕计数问题展开，先给出乘法原理与加法原理两类基本工具，再讲解排列、组合、环形排列与允许重复的组合，最后介绍容斥原理与鸽笼原理在计数与存在性证明中的应用。
计数法初步课件封面
离散数学 Discrete Mathematics，本章为计数法初步。
第2章计数法初步
本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。
计数法初步本章学习内容
基本原理
本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。
如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选，…，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：
Xt均为集合，第i个集合Xi有ni个元素。如{X1, X2, …, Xt}为两两不相交的集合，则可以从X1, X2, …, Xt中选出的元素总数为：n1+ n2+ … + nt即集合X1∪X2∪…∪Xt含有n1+n2+…+nt个元素。
计数法初步本章学习内容
排列与组合
本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。
排列问题
环形排列问题
例：6个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。
解：6个人围坐在圆桌上，有120种不同的坐法。AEFBDC
环形排列问题
定理：含n个不同元素的集合的环形r-排列数Pc(n,r)是
环形排列问题
例：求满足下列条件的排列数。(1)10个男孩和5个女孩站成一排，无两个女孩相邻。(2)10个男孩和5个女孩站成一圆圈，无两个女孩相邻。
组合问题
定理：对满足0< r ≤n的正整数n和r有
组合问题
例：一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；各有13种点数，分别为A, 2-10, J, Q, K。试求满足下列条件的组合数。（1）5张牌称为一手牌，一手牌共有多少种可能的组合？（2）一手牌5张都是同一花色，有多少种可能的组合？（3）一手牌有3张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？
组合问题
例：在1到300中选三个不同的数，并且这三个数之和能被3整除，问有多少种方式？
例：多少个12位二进制串包含a)恰好3个1？b)至多3个1？c)至少3个1？d) 0的个数与1的个数相等？
例：从包含苹果、橙子、和梨的框子里选4个水果。如果不关心选择水果的顺序，且只关心水果的类型，那么当框中每类水果至少有4个时有多少种选法？
【解答】共有15种方式：4个苹果；4个橙子；4个梨；3个苹果，1个橙子；3个苹果，1个梨；3个梨，1个苹果；3个橙子，1个梨；3个梨，1个苹果；3个梨，1个橙子；2个苹果，2个橙子；2个苹果，2个梨；2个橙子，2个梨2个苹果，1个橙子，1个梨；2个橙子，1个苹果，1个梨2个梨，1个苹果，1个橙子。这个解是从3个元素的集合{苹果、梨、橙子}中允许重复的4组合数。
例：从包含1美元、2美元、5美元、10美元、20美元、50美元及100美元的钱袋中选5张纸币，有多少种方式？假定不管纸币被选的次序，同种币值的纸币都是不加区别的，并且至少每张纸币有5张。
解：假设一个零钱盒子有7个隔间，每个保存一种纸币，如下图所示。这些隔间被6块隔板分开，每选择1张纸币就在相应的隔间里放置1个标记。针对选择5张纸币的3种不同方式给出了这种对应，其中的竖线表示6个隔板，星表示5张纸币。
有重复的组合
本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。
选择5张纸币的方法数对应了安排6条竖线和5颗星的方法数。因此，选择5张纸币的方法数就是从11个可能的位置选5颗星位置的方法数。这对应了从含11个物体的集合中无序地选择5个物体的方法数，可以有C(11,5)种方法.因此从7类纸币的袋中选择5张纸币的方式数有：
定理：n个元素的集合中允许重复的r组合有C(n-1+r,r)
分析：用n-1条竖线标记n个不同的单元。每当集合的第i个元素出现在组合中，第i个单元就包含一颗星。例如，4种元素集合的一个6组合用3条竖线和6颗星表示。例如* *| * | | * * *表示2个第一元素、1个第二元素、0个第三元素和3个第四元素的组合。因此，包含n-1条竖线和r颗星的每一个不同的表对应了n元素集合的一个允许重复的r组合。这种表的个数就是C(n-1+r, r),因为每个表对应了从包含r颗星和n-1条竖线的n-1+r个位置来放r颗星的一种选择。
例：方程x1+x2+x3=11有多少个解？其中x1,x2,x3是非负整数。
分析：一个解对应了从3元素集合中选11个元素的方式，以使得x1选自第一类，x2选自第二类，x3选自第三类。因此，解的个数等于3元素集合允许重复的11组合数：
计数法初步本章学习内容
相容排斥原理
本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。
基本容斥原理UABA∩BA-BB-A
定理：设A和B是任意有限集合，有：|A∪B| = |A|＋|B|－|A∩B|
推论：设U为全集，A，B是任意有限集合，有：∩∩
例题
例：在20个大学生中，有10人爱好音乐，有8人爱好美术，有6人既爱好音乐又爱好美术。问：（1）爱好音乐或美术的学生有多少？（2）既不爱好音乐又不爱好美术的学生有多少？
基本容斥原理
定理：设A,B和C是任意有限集合，有：
推论：设U为全集，A，B和C是任意有限集合，有：
例题
例：260个大学生中，64人选修数学，94人选修计算机，58人选修商贸，28人同时选修数学和商贸，26人同时选修数学和计算机，22人同时选修计算机和商贸，14人对三种课程都选修。问（1）三种课程都不选的学生有多少？（2）只选修计算机科学课程的学生有多少？
广义容斥原理
定理：设A1, A2, …, An是任意n个有限集合，则：
推论：设U为全集，A1, A2, …, An是任意n个有限集合，则
例题
例：24名科技人员中，会英、日、德、法语的分别为13、5、10和9人，同时会英语、日语的有2人，同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的均为4人，会日语的人既不会法语也不会德语。试求：(1)同时会英、德、法语的人数为多少？(2)只会一种语言的人数各为多少？
计数法初步本章学习内容
鸽笼原理
本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。
鸽笼原理
本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。
鸽笼原理
本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。
鸽笼原理（Pigeonhole Principle）又称为抽屉原理、鸽舍原理，是指如下定理：
定理：(鸽笼原理)若有n+1只鸽子住进n个鸽笼，则有一个鸽笼至少住进2只鸽子。
例题
例：抽屉里有3双不一样的手套，从中至少取多少只，才能保证配成一双？
例：证明从1到10中任意选出六个数，其中必有有两个数的和是11。
广义鸽笼原理
定理：若有n只鸽子住进m(n>m)个鸽笼，则存在一个鸽笼至少住进只鸽子。这里，表示小于等于x的最大整数。
例题
例：如果一个图书馆里30本离散数学书共有12003页，那么必然有一本离散数学书至少有401页。
例：如果离散数学课有5个可能的成绩ABCDE，那么一个班最少有多少名学生才能保证至少6名学生得到相同的分数。
广义鸽笼原理
例：(拉姆齐理论)假定一组有6个人，任两个人或者是朋友或者是敌人。证明在这组人中要么存在3个人彼此都是朋友，要么存在3个人彼此都是敌人。
广义鸽笼原理
分析：令A是这6人中任意一个，则由广义鸽巢原理知：组里其他5人中至少有3人是A的朋友，或至少有3个人是A的敌人。若是前一种情况，假定B、C、D是A的朋友。如果这3人中有2人也是朋友，那么这2人和A构成彼此是朋友的3人组。否则，B、C、D构成彼此为敌人的3人组。对于后一种情况，即当A存在3个或更多的敌人时，可以用类似方法处理。
计数法初步小结
本节内容到此结束，谢谢大家！
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}