资源描述：
《1数字集合论基础(资料)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第一章数字电路理论基础--数字集合论数字集合论基础知识:排列与组合[1-1]一．排列Def0.1函数与二部图（偶图）设U,V为有限集合，函数为则得二部图（偶图），称为表现函数的二部图。表示序偶，在第一节中将详细介绍。二部图得名的由来：当集合时，函数能这样考虑，把m个不同的球放入附有标记的n个箱内的一种放法；函数也能这样考虑，把n类球（每类球不止一个）放入m个箱内，每个箱内只有一个球的一种放法(集合V中的球不一定全部选择)。前者是从偶图的左侧端点集合U看问题的，后者是从二部图的右侧端点集合V看问题的。所以二部图及表示分为集合U和集合V两个部分，也表示可以从U，或者从V两个方向解释整
2、体，是可逆的过程。注：从有限集合U到V的函数有。排列，是一一映射，表示从V中选取m个元素，放入附有1,…,m编号的箱子而每个箱子内恰好一个的一种方法，与从n个不同的元素中选取m个使其按序排列是等价的.Def0.2排列：一对一映射从n个相异的元素中选取m个使其按序排列的方法就作排列，，即一一映射的全体和从从n个不同的元素中选取m个使其按序排列的全体是一一对应的。一一映射的个数是,:Fom0.1称为从n个（相异的）元素中选取m个使其按序排列的排列数。Def0.2.1圆排列从n个元素中选取r个排成一个圆圈的排列称为n个元素的r元圆排列，排列总数：Fom1.2?Def0.2.2全排列从n个元素中选
3、取n个的排列称为全排列.这样的排列总数:Fom0.3规定的对应多项式可看作n的多项式,把n用变量x代换,得到x的m次多项式的展开式.Fom0.4Def称系数S(m,k)为第一种斯特林(stirling)数.Th0.1对于第一种stirling数下式成立:Fom0.5.1S(m+1,k)=S(m+1,k-1)-m*S(m,k)()Fom0.5.2S(m,0)=0;S(m,m)=1()这个公式的意义.证明重复排列:限制重复度的函数Def0.3重复度函数和,把的象源的个数叫做f在V中对于的重复度,Th0.2设,且Fom0.6.1Fom0.6.2.其中表示的重复度,则这样限制重复度的函数的个数:F
4、om0.7证明:考虑对于各个的个新元素，则从U到的一一映射的个数为,而对于各个具有重复度的一个函数则和个一一映射对应（？？？）。当把值域中的看作同一个就得到.因而，限制重复度的函数的个数有Fom1.7。若有m个物，设第一类物有d1,第二类物有d2,…，第n类物有dn,同类物之间没有区别。这样的m个物的排列叫做重复排列，即限制重复度的函数可看作是把不同的m个物在第一个箱内放d1个，…，在第n个箱内放个dn个的一种分配方法。？？?若有m个相异的物和与这m个不同的r个相同的物，这m+r个物的排列数根据定理Th1.2与把m个不同的物放入r+1个附有序号的箱内是等价的。怎样区别？为什么等价。公式为：
5、Fom0.8例1路径遍历排列的生成递推排列的算法:从{1,2,…,n-1}的排列生成{1,2,…,n}的排列.二.组合Def0.4(组合)从m个元素集合U中选取r个元素构成的子集称为U的r组合.组合是不考虑元素之间的选取次序的。组合可以看成重复度限制的某个二值函数，设，，则有重复度的函数和从U中取r个元素构成的子集（从m个物中选取r的组合）一一对应，因而，根据Th1.2,下面的定理成立。Th0.3设，则U的r个元素的子集个数等于，或.Fom排列和组合的关系：重复组合：单调非递减函数Def重复组合是从n类物中允许重复m个物的组合。重复组合可以看成是多重集的组合。若U是多重集，则U的r组合是不
6、计次序地从U中选取r个元素，于是U的r组合本身也是一个多重集，是U的子多重集。Def设，对于各,把满足的函数称为单调非递减函数；把满足的函数称为单调递增函数。三．集合的分割：满射把不同的n个物放入不同的m个箱中，每个箱都不少于一个物，这样的饭配方法和从到的满射函数一一对应。这样n个物的分配恰恰是n元集合到m个非空子集的分割。Def把n个不同的元素分成m个子集，每个子集至少一个元素的分割方法数称为第二种stirling数，。Th0.4从n元集合到m元集合的满射函数个数等于三.加法原理和乘法原理§1二值集合论[1-2]一．输入序偶集Def1.1设A为一个集合，则集合A的幂集被定义如下，并简记为
7、，即：幂集是集合A的伴随集之一，它的元素是A的所有子集，亦即A中元素的所有组合。Th1.1设集合A={a0,a1,a2,…,an-1}，则有2n个元素。。证明：def1.2序偶序偶是两个元素的排列，与次序相关的二元组。实际上最常用在函数里，表示原象和象；用在有向图中表示一条弧。def1.2.1三元组说明:.没有赋予x3不同的语义:若x3值重复,第2,3集合相同,与二元组的定义相同.def1.2.2多元组n元关系的使用很广
