下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 组合数学

组合数学.doc

组合数学

王达达欢乐多
2010-11-22 0人阅读 举报 0 0 暂无简介

简介:本文档为《组合数学doc》,可适用于其他资料领域

组合数学组合数学CombinatorialMathematics内容摘要:一、组合数学概述二、排列组合三、容斥原理四、鸽笼原理五、母函数六、Pólya计数原理的相关数学基础一、组合数学概述广义:有人认为广义的组合数学就是离散数学也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称但这只是不同学者在叫法上的区别。总之组合数学是一门研究离散对象的科学。随着计算机科学的日益发展组合数学的重要性也日渐凸显因为计算机科学的核心内容是使用算法处理离散数据。狭义:狭义的组合数学主要研究满足一定条件的组态(也称组合模型)的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。二、排列组合加法原理:若事件能以种方式发生另一个不同的事件能以种不同的方式发生则事件或事件能以种方式发生。乘法原理:若事件能以种方式发生另一个不同的事件能以种不同的方式发生则事件和事件能以种方式发生。排列:从个不同的元素中有次序地选取个元素称为从中取出个的排列其排列数记为。当时称此排列为全排列。定理:证明:在个不同的元素中有次序地选取个元素可以采取以下方式:首先取一个元素有种选择然后选第二个元素有种选择……最后取第个元素有种选择。由乘法原理得:例:(圆排列问题)从个不同的元素中选取出个元素围成一个圆求选取的方案总数。解:从个不同的元素中选取出个元素的排列数为。设为一个排列。将其加以变换……一共有个排列。但是这个排列对应同一个圆排列也就是说每一个圆排列对应着个线排列所以从个不同的元素中选取出个元素组成的圆排列总数为组合:从个不同的元素中选取个元素而不考虑其次序时称为从中取出个的组合其组合数记为或。对于一个从个不同的元素中选取个元素的每一个组合对这个元素进行全排列便得到了一个从个不同的元素中选取个元素的排列。因此可以得到下面的定理:定理:例:在如图所示的棋盘中若从左下角走到右上角并且规定只能向右走或者向上走问共有多少种方案。图一个的棋盘解:如果从左下角向右走步然后再向上走步就可以达到右上角。并且发现:如果从左下角开始无论怎么走只要向右走步和向上走步都可以达到右上角。所以我们可以用代表向右走一步用代表向上走一步。那么从左下角到右上角的一种可能的走法就唯一地对应了一个由个和个组成的位字符串。反之给定一个由个和个组成的位字符串。如果规定代表向右走代表向上走则这个字符串又唯一地对应着一种可能的走法。这样便建立了方案与字符串之间的一一对应关系。所以我们所求的方案数就是由个和个组成的位字符串的个数即PKUHRBEU三、容斥原理定理(DeMorgan定理):设、为全集的任意两个子集则()()定理(DeMorgan定理的推广形式):设为全集的子集则()()定理(容斥原理的简单形式):设、是分别具有性质和的元素集合则。定理(容斥原理):集合的子集具有性质具有性质…,具有性质则()​ 集合至少具有性质…,之一的元素的个数为()集合不具有性质…,之一的元素的个数为例:(欧拉函数)小于并且与互质的正整数的个数记为(称为欧拉函数)求。解:设的不同素数因子的是用表示能够被整除的所有整数组成的集合。比如、、表示能够被、、整除的正整数的集合。求就是求不属于任何一个的整数的个数。即求于是由容斥原理得又因为…所以例:(错位排列问题)设是的一个全排列。若对于任意的成立则称是的一个错位排列。用表示的错位排列的个数求。解:令是由的所有全排列组成的集合则令是在的所有全排列中由第个位置上的元素恰为的所有排列组成的集合则有。同理可得一般情况下有又因为是中不满足性质…,的元素个数由容斥原理得四、鸽笼原理定理(简单形式):将只或只以上的鸽子放入个鸽笼内则至少有一个鸽笼内有只或只以上的鸽子。定理(加强形式):设都是正整数若将个物品放入个盒中则必有一盒内至少含有个物品或者有一盒内至少含有个物品……或者有一盒内至少含有个物品。推论:若将个物品放入个盒子里则至少有一个盒子里含有个或者更多的物品。推论:设个正整数满足不等式则中至少有一个不小于。例:在边长为的正三角形中任意放个点证明:至少有两个点之间的距离不大于。证明:如右图在三角形的三边中点之间连线整个三角形划分成四个边长均为的小三角形由鸽笼原理个点至少有两个点落在同一个小三角形里而这两个点之间的距离一定小于等于。例:在某一个宴会里所参加的人当中一定会有两人所认识的朋友个数一样多。证明:将人数为的一群人分为。其中表示有个朋友的那些人。视为鸽为笼。在此鸽笼鸽笼原理得不出结论!但稍加注意就可看出与中必有一笼是空的。若不空表示有一人跟其它所有人都不是朋友因此没有一个人认识所有其它人此即表示是空的若不空表示有一人认识所有其它个人因此不可能有一人跟其它所有人都不是朋友此即表示是空的。故要么为空要么为空!因此所有人共可分为类。由鸽笼原理知至少有一类有二个人。换言之有二个人有一样多的朋友。五、母函数母函数与标志函数:给定数列构造一函数称为数列的母函数其中序列只作为标志用,所以称之为标志函数标志函数的最有用和最重要的形式是在这种情况下,对于数列的母函数为这是我们研究的重点定理(普通型母函数):设从元集合中取元素的组合是若限定元素出现的次数集合为则该组合数序列的母函数为例:有重量为、、(克)的砝码各两个问:()可以称出多少种不同重量的物品()若要称出重量为(克)的物品所使用的砝码有多少种本质不同的情况解:根据定理构造母函数如下其中第一个括号中的表示可以不用重量为的砝码表示可以使用个重量为的砝码表示可以使用个重量为的砝码。同理第二个括号中的表示可以不用重量为的砝码表示可以使用个重量为的砝码表示可以使用个重量为的砝码以此类推。将上面的多项式展开后比如多项式它表示我们可以用个重量为的砝码和个重量为的砝码来称出重量为的物体代表了一种称重量的方法。显然当把展开并将指数相同的项进行合并后有多少个系数非的项就代表了可以称量出多少种不同重量的物品而相应的前面的系数则表明了称量出重量为的物品可选砝码的方案数。所以项前面的系数就是本题第二问的解而的展开式中系数不为的项的个数就是本题第一问的解。定理(指数型母函数):从多重集合中选取个元素的排列中若限定元素出现的次数集合为则该排列数序列的母函数为在应用指数型母函数解题时我们经常需要应用的Taylor展开式,即对此稍加变换便可得到比较普通型母函数和指数型母函数可以看到普通型母函数的标志函数为而指数型母函数的标志函数为关于指数型母函数的标志函数的物理意义可以这样来理解。对于表示在一个方案中某个元素出现了次而在不同位置中的次出现是相同的所以在计算排列总数时只应算作一次。由排列组合的知识可以知道最后的结果应该除以。在应用指数型母函数时还应该特别注意对于一个指数型母函数的展开式我们应将化为这样的形式在指数型母函数中只有才是我们所需要的结果。例:设有个数字其中三个数字两个数字一个数字问能组成多少个四位数解:这实际上是求中取四个的多重集排列数问题。其指数型母函数为所以可以组成个四位数。PKU六、Pólya计数原理的相关数学基础群:给定集合和集合上的二元运算如果满足下列条件()​ 运算是封闭的:对于任意的成立。()​ 运算是可结合的:对于任意的成立。()​ 存在单位元:中存在一个元素使得对于任意的成立。()​ 存在逆元:对于任意的存在一个元素使得。这时称为的逆元记为。则称集合在运算下是一个群记为。若是一个有限集则称为有限群若是一个无限集则称为无限群。当群中的二元运算满足交换律时称该群为可交换群又称为Abel群。注意:在群的定义中“”只是代表一个二元运算而不是通常意义上的乘号。置换:集合的一个一一映射称为一个元置换记为对换群与置换群:令是的置换全体是的两个元素定义它们的乘积为对于置换乘法“”构成群称为次对称群。的任意子群称为置换群。注意:在上述定义中将自变量放到了置换符号前面。这是因为置换的复合运算顺序与函数的复合运算顺序是相反的。循环:置换叫做阶循环简记为。对换:二阶循环叫做与的对换。不相交的:如果两个循环没有公共元素则称这两个循环是不相交的。定理:任何一个置换都可以表示成若干个互不相交的循环的乘积且表示法是唯一的。Note:任何一个置换都可以表示成若干个对换的乘积。因为任何一个循环都可以表示成若干个对换的乘积。稳定核:设是的子群若是中的某个整数中使数固定不变的置换全体所构成的集合称为数在下的稳定核或称中使数固定不变的置换群记为。此时为一个不变元。中不变元的个数记为。例:已知将中的元素依次记为则且======。引理:若设为置换中不变元的个数则群的等价类个数为其中“等价类个数”就是在染色问题中所求的本质不同的方案数。例:用红、蓝两种颜色对正方形的四个顶点进行着色问共有多少中方案经过旋转后重合的着色方案算一种。解:用红蓝两种颜色对正方形的四个顶点着色的所有情况如图所示。从图中可以看出有种着色方案在这些着色方案中有许多方案本质上是相同的。比如方案、和都可以通过方案旋转来得到因此这四个方案是本质相同的。方案、、都可以通过方案旋转来得到因此这四个方案也是本质相同的。那么总共有多少种本质不同的方案呢下面用引理来解决这个问题。根据题意我们可以对这个正方形进行四种变换即依次旋转、、和。当旋转时这所有的个图形没有发生任何变化因此可以写为所以=当旋转时图形和没有发生变化而其他的个图形都发生了变化所以=同理可得:==。所以由引理得本质不同的着色方案数为这六种本质不同的着色方案如图所示。Pólya定理:设是个对像的置换群用种颜色给这个对像着色则不同的着色方案数为因为=所以在上面的定理中不同的着色方案数也可以写为例:考虑上一节中的例题用红、蓝两种颜色对正方形的四个顶点进行着色。问共有多少种方案?经过旋转后重合的着色方案算一种。解:我们对一个正方形的四个顶点标号如图所示。将这个正方形顺时针旋转、、和后的各正方形顶点标号如图所示。设则可得所以有====。由Pólya定理得不同的着色方案数为与用引理所求得的结果是相同的。练习题:HRBEU校赛题PKU

用户评价(1)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/12

组合数学

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利