组合数学(Richard A. Brualdi)重要知识考点.docx

什么是组合§1排列组合组合数学主要研究有限集合的计数，结构的存在性，以及性质。几个计数原理设是有限多个元素的集合，用表示的元素个数分类与加法原理设，，，则称为的一个分类，显然（加法原理）分步骤乘法原理设是有限集令（笛卡尔乘积），称为的积，显然的每个元素是有序数对，是按步骤确定的且（乘法原理）【例1】则【例2】求120的因数的个数解：，，其中令，记120的因数的集合为故.【例3】有限集的一个有序列称为的一个r排列，其中，，所有r排列的个数记为，令，则，规定：0！=1.双射原理设、是两个集合，对应，对中的每个元素，有唯一的元素，，与之对应，则称为一个映射.映射： 不是映射.如果有，则称是单射.显然，这时有.如果有使则称为满射.如果既是单射又是满射，则称为双射.这时.【例4】设，计算的所有子集的个数（组合证明）解：设表示的所有子集所成的子集（或者用幂集表示）设：令，，，时表示，如果则令易知是双射.由双射原理和乘法原理得：补充：例如，在上述映射下，有，，，【例5】的个元素所成的集合成为的一个组合所有这样的组合的个数记为，称之为二项式系数.一般来讲，特别的当时，，今后，令，且为任意实数.注意是没有意义的.【例6】循环排列（圆排列）：从中取出个元素作圆排列的个数为，当时，如：1,2,3三个元素作圆排列，一共有种不同的排列方法.§3重集设是个不同的元素，我们用表示有的集合称为一个重集，这里注：表示不出现，表示取之不尽这个集合的元子集称为一个组合，元有序集合称为一个排列.【例1】的5组合有：、、3个；6排列共有个.§4重集的排列的排列的个数等同于的排列的个数的全排列（这里）的个数为，其中注：称为多项式系数，这里只有当时才有意义.证明：要得到一个排列，我们只需从个有序位置中选取个位置来放，共有种方法，再在余下的个位置中选个位置来放，共有种方法，继续下去，由乘法原理，排列的个数等于多重集合的组合组合数学（Richard A. Brualdi）重要知识考点整理4