《组合数学》教案-1章(排列组合基础)

《组合数学》第一章组合数学基础1/61姜建国第1章组合数学基础1.排列组合的基本计数问题2.多项式系数的计算及其组合意义3.排列组合算法1.1绪论（一）背景起源：数学游戏幻方问题：给定自然数1,2,…,n2，将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。例：3阶幻方，幻和＝(1＋2＋3＋…＋9)/3＝15。关心的问题（1）存在性问题：即n阶幻方是否存在？（2）计数问题：如果存在，对某个确定的n，这样的幻方有多少种？（3）构造问题：即枚举问题，亦即如何构造n阶幻方。816276357951492438奇数阶幻方的生成方法：一坐上行正中央，依次斜填切莫忘，上边出格往下填，右边出格往左填，右上有数往下填，右上出格往下填。《组合数学》第一章组合数学基础2/61姜建国例：将2，4，6，8，10，12，14，16，18填入下列幻方：【例1.1.1】（拉丁方）36名军官问题：有1，2，3，4，5，6共六个团队，从每个团队中分别选出具有A、B、C、D、E、F六种军衔的军官各一名，共36名军官。问能否把这些军官排成6×6的方阵，使每行及每列的6名军官均来自不同的团队且具有不同军衔？本问题的答案是否定的。A1B2C3D4E5F6A1B2C3D4E5F6B2C3D4E5F6A1B3C4D5E6F1A2C3D4E5F6A1B2C5D6E1F2A3B4D4E5F6A1B2C3D2E3F4A5B6C1E5F6A1B2C3D4E4F5A6B1C2D3F6A1B2C3D4E5F6【例1.1.2】（计数——图形染色）用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。求本质上不同的染色方案。举例：ryybbbrb（a）（b）《组合数学》第一章组合数学基础3/61姜建国形式总数：43＝81种。实际总数（见第6章）：L＝32334124＝24【例1.1.3】（存在性）不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是由低到高或由高到低排列的（见第5章）。注意：不改变原来的相对顺序。（二）研究内容算法分类：第一类：数值算法。主要解决数值计算问题，如方程求根、解方程组、求积分等，其数学基础是《高等数学》与《线性代数》（解决建模问题，《数值分析》或称《计算方法》解决离散化问题，即在计算机上的求解方法问题）。第二类：组合算法。解决搜索、排序、组合优化等问题，其数学基础为《组合数学》。按所研究问题的类型，研究内容：组合计数理论组合设计组合矩阵论组合优化本课程重点：以组合计数理论为主，部分涉及其它内容。（三）研究方法分类：第一类：从组合学基本概念、基本原理出发解题的所谓常规方法（利用容斥原理、二项式定理、Pólya定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等）。第二类：通常与问题所涉及的组合学概念无关，而对多种问《组合数学》第一章组合数学基础4/61姜建国题均可使用。例如：（1）数学归纳法：前提是已知问题的结果。（2）迭代法【例】已知数列nh满足关系1,1211hhhnn，求nh的解析表达式。（解）直接迭代即得：121nnhh＝1222nh＋1＝12222nh＝1212232nh＝1222233nh＝12222223211nnnh＝12n（3）一一对应技术原理：建立两类事物之间的一一对应关系，把一个较复杂的组合计数问题A转化成另一个容易计数的问题B，从而利用对B的计数运算达到对A的各种不同方案的计数。思路：将未解决问题的模式转化为一种已经解决的问题模式。（4）殊途同归方法原理：从不同角度讨论计数问题，以建立组合等式。应用：组合恒等式的证明（也称组合意义法）。（5）数论方法特别是利用整数的奇偶性、整除性等数论性质进行分析推理《组合数学》第一章组合数学基础5/61姜建国的方法。组合数学用的较多的是方法（3）与（4）。【例1.1.4】有100名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军共需要进行多少场比赛？（解）常规思路：50＋25＋12＋6＋3＋2＋1＝99场10000名选手：5000＋2500＋1250＋625＋312＋…＋1采用一一对应方法：每场比赛产生一个失败者，且每个失败者只能失败一次。反之，要淘汰一个选手，必须恰好经过一场比赛。结论：失败者比赛场次。应该比赛99场。一般情况：单循环淘汰制，n个选手，比赛n－1场。【例1.1.5】设某地的街道将城市分割成矩形方格，某人在其住处A(0，0)的向东7个街道、向北5个街道的大厦B(7，5)处工作（见图1.1.3），按照最短路径（即只能向东或向北走），他每次上班必须经过某12个街段，问共有多少种不同的上班路线？（解）（1）将街道抽象为等长的。B(7,5)A(0,0)图1.1.1最短路径（2）对应为（元素可重复的）排列问题：《组合数学》第一章组合数学基础6/61姜建国路径（蓝色）→排列ｘｙｙｘｘｙｙｘｘｘｘｙ排列ｙｘｘｙｙｙｙｘｘｘｘｘ→路径（红色）结论：最短路径7个x和5个y的排列（3）求解：再对应为（元素不重复的）排列问题N＝!7!5!12＝557C＝512C＝792（4）一般情形：从（0，0）点到达（m，n）点的不同的最短路径数为N＝mnmC＝nnmC1.2两个基本法则1.2.1加法法则（一）加法法则常规描述：如果完成一件事情有两个方案，而第一个方案有m种方法，第二个方案有n种方法可以实现。只要选择任何方案中的某一种方法，就可以完成这件事情，并且这些方法两两互不相同。则完成这件事情共有m＋n种方法。集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，则A与B的并共有m＋n个元素。概率角度描述：设事件A有m种产生方式，事件B有n种产生方式，则事件“A或B”有m＋n种产生方式。当然A与B各自所含的基本事件是互相不同的。（二）应用【例1.2.1】某班又男生18人，女生12人，从中选出一名代表参加会议，问共有多少种选法？（解）（1）两个选择方案：选男生（18种选法）或女生（12《组合数学》第一章组合数学基础7/61姜建国种选法）。由加法法则，全班共有18＋12＝30选法。（2）设集合：A——男生，B——女生。该班中的学生要么属于A，要么属于B，且AB＝，故BA＝18＋12＝30。（3）事件A——选男生（18种可能），事件B——选女生（12种可能）。事件“A或B”——选男生或女生，由加法法则，有18＋12＝30种可能。【例1.2.2】用一个小写英文字母或一个阿拉伯数字给一批机器编号，问总共可能编出多少种号码？（解）26＋10＝36个。其中英文字母共有26个，数字0～9共10个。1.2.2乘法法则（一）乘法法则常规描述：如果完成一件事情需要两个步骤，而第一步有m种方法、第二步有n种方法去实现。则完成该件事情共有m·n种方法。集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，BbAa,，记ba,为一有序对。所有有序对构成的集合称为A和B的积集（或笛卡儿乘积），记作BA。那么，BA共有nm个元素。BA＝BbAaba,,概率角度描述：设离散型随机变量X有m个取值，Y有n个取值，则离散型随机向量（X，Y）有nm种可能的取值。（二）应用【例1.2.3】仍设某班有男生18人，女生12人，现要求从中分别选出男女生各一名代表全班参加比赛，问共有多少种选法？（解）（1）分两步挑选，先选女生（12种选法），再选男生《组合数学》第一章组合数学基础8/61姜建国（18种选法）。由乘法法则，全班共有12×18＝216种选法。（2）设集合：A——男生，B——女生。由乘法法则，A×B＝18×12＝216。（3）变量X——男生（18种取值），变量Y——女生（12种取值）。由乘法法则，随机向量（X，Y），有18×12＝216种可能的值。【例1.2.4】给程序模块命名，需要用3个字符，其中首字符要求用字母A～G或U～Z，后两个要求用数字1~9，问最多可以给多少种程序命名？（解）首字符选法：7＋6＝13种（加法法则）。总数：13×9×9＝1053种（数字可重复使用）（乘法法则）。【例1.2.5】从A地到B地有1n条不同的道路，从A地到C地有2n条不同的道路，从B地到D地有1m条不同的道路，从C地到D地有2m条不同的道路，那么，从A地经B或C到达目的地D共有多少种不同的走法?（解）路线ABD：1n×1m种走法（乘法法则）路线ACD：2n×2m种走法（乘法法则）总数：1n1m＋2n2m种走法（加法法则）《组合数学》第一章组合数学基础9/61姜建国2×3＋3×4＝181.3排列与组合1.3.1相异元素不允许重复的排列数和组合数（一）计算公式从n个相异元素中不重复地取r个元素的排列数和组合数：（1）排列：!!11,PPrnnrnnnrnrn推导：反复利用加法法则与乘法法则（2）组合：!!!!,rrnnrPrnrnCCrnrn推导：利用组合与排列的异同（3）例：n＝5，r＝3，即元素为1，2，3，4，5排列：134，143，314，341，413，431；254，425，……组合：134，245，……（4）特点：排列考虑顺序，组合不然。（二）数学模型《组合数学》第一章组合数学基础10/61姜建国（1）排列问题：将r个有区别的球放入n个不同的盒子，每盒不超过一个，则总的放法数为P(n，r)。（2）组合问题：将r个无区别的球放入n个不同的盒子，每盒不超过一个，则总的放法数为C(n，r)。对应关系元素盒子位置球元素和位置编号12345ABC排列1ABC134排列2CBA431排列3ACB143排列4ACB254排列5BAC425组合1●●●134组合2●●●2451.3.2相异元素允许重复的排列（一）问题从n个不同元素中允许重复地选r个元素的排列，简称r元重复排列，排列数记为RP(∞，r)。（二）模型将r个不相同的球放入n个有区别的盒子，每个盒子中的球数不加限制而且同盒的球不分次序。对应关系元素盒子位置球元素和位置编号12345ABC排列1ABC114排列2CBA433排列3ACB343排列4ABC222排列5BAC425（三）计算公式《组合数学》第一章组合数学基础11/61姜建国RP(∞，r)＝rn（四）集合描述方式设无穷集合neeeS,,,21，从S中取r个元素的排列数即为RP(∞，r)。不重复排列：S＝neee1,,1,121＝neee,,,21。1.3.3不尽相异元素的全排列（一）问题有限重复排列（或部分排列）：设ttenenenS,,,2211（nnnnt21），从S中任取r个元素，求其排列数RP(n，r)。（二）模型将r个有区别的球放入t个不同的盒子，每个盒子的容量有限的，其中第i个盒子最多只能放入in个球，求分配方案数。例：S＝{2·1，4·2，1·3，3·4，2·5}＝{1，1，2，2，2，2，3，4，4，4，5，5}对应关系元素盒子位置球元素和位置编号12345ABC排列1ABC114排列2BCA433排列3ACB343排列4ABC222排列5BAC425《组合数学》第一章组合数学基础12/61姜建国说明：（1）极端情形：相异元素不重复的排列强调的是不重复，即盒子的容量为1；（2）极端情形：相异元素允许重复的排列强调的是无限重复，即盒子的容量无限；（3）一般情形：不尽相异元素的排列强调的是有限重复，即盒子的容量有限，介于两者之间。（三）特例（1）r＝1：RP(n,1)＝t（2）r＝n（全排列）!!!!,RP21tnnnnnn即n个不同元素的全排列