《《组合数学》教案1章(排列组合基础)》由会员分享，可在线阅读，更多相关《《组合数学》教案1章(排列组合基础)（62页珍藏版）》请在金锄头文库上搜索。
1、第1章 组合数学基础1. 排列组合的基本计数问题2. 多项式系数的计算及其组合意义3. 排列组合算法1.1 绪 论（一） 背景起源：数学游戏幻方问题：给定自然数1, 2, , n2，将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。例：3阶幻方，幻和(1239)/315。关心的问题（1） 存在性问题：即n阶幻方是否存在？（2） 计数问题：如果存在，对某个确定的n，这样的幻方有多少种？（3） 构造问题：即枚举问题，亦即如何构造n阶幻方。816276357951492438图1.1.1 3阶幻方奇数
2、阶幻方的生成方法：一坐上行正中央，依次斜填切莫忘，上边出格往下填，右边出格往左填，右上有数往下填，右上出格往下填。例：将2，4，6，8，10，12，14，16，18填入下列幻方：【例】（拉丁方）36名军官问题：有1，2，3，4，5，6共六个团队，从每个团队中分别选出具有A、B、C、D、E、F六种军衔的军官各一名，共36名军官。问能否把这些军官排成66的方阵，使每行及每列的6名军官均来自不同的团队且具有不同军衔？本问题的答案是否定的。A1 B2 C3 D4 E5 F6 A1 B2 C3 D4 E5 F6B2 C3 D4 E5 F6 A1 B3 C4 D5 E6 F1 A2C3 D4 E5 F6
3、A1 B2 C5 D6 E1 F2 A3 B4D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1E5 F6 A1 B2 C3 D4 E4 F5 A6 B1 C2 D3F6 A1 B2 C3 D4 E5 F6【例】（计数图形染色）用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。求本质上不同的染色方案。举例：ryybbbrb（a）（b）形式总数：81种。实际总数（见第6章）：L24【例】（存在性）不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是
4、由低到高或由高到低排列的（见第5章）。注意：不改变原来的相对顺序。（二） 研究内容算法分类：l 第一类：数值算法。主要解决数值计算问题，如方程求根、解方程组、求积分等，其数学基础是高等数学与线性代数（解决建模问题，数值分析或称计算方法解决离散化问题，即在计算机上的求解方法问题）。l 第二类：组合算法。解决搜索、排序、组合优化等问题，其数学基础就是组合数学。按所研究问题的类型，研究内容：l 组合计数理论l 组合设计l 组合矩阵论l 组合优化本课程重点：以组合计数理论为主，部分涉及其它内容。（三） 研究方法分类：第一类：从组合学基本概念、基本原理出发解题的所谓常规方法（利用容斥原理、二项式定理、P
5、lya 定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等）。第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如：（1） 数学归纳法：前提是已知问题的结果。（2） 迭代法【例】如已知数列满足关系，求的解析表达式。（解）直接迭代即得：1（3） 一一对应技术原理：建立两类事物之间的一一对应关系，把一个较复杂的组合计数问题A转化成另一个容易计数的问题B，从而利用对B的计数运算达到对A的各种不同方案的计数。思路：将未解决问题的模式转化为一种已经解决的问题模式。（4） 殊途同归方法原理：从不同角度讨论计数问题，以建立组合等式。应用：组合恒等式的证明（也称组合意
6、义法）。（5） 数论方法特别是利用整数的奇偶性、整除性等数论性质进行分析推理的方法。组合数学用的较多的是方法（3）与（4）。【例】有100名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军共需要进行多少场比赛？（解）常规思路：502512632199场10000名选手：5000250012506253121采用一一对应方法：每场比赛产生一个失败者，且每个失败者只能失败一次。反之，要淘汰一个选手，必须恰好经过一场比赛。结论：失败者与比赛场次之间一一对应，故应该比赛99场。一般情况：单循环淘汰制的比赛，若有n个选手参考比赛，则须经过n1场比赛，方可产生冠军。【例】设某地的街道将城市分割成矩形
7、方格，某人在其住处A(0，0)的向东7个街道、向北5个街道的大厦B(7，5)处工作（见图1.1.3），按照最短路径（即只能向东或向北走），他每次上班必须经过某12个街段，问共有多少种不同的上班路线？（解）（1）将街道抽象为等长的。 B(7, 5) A(0, 0)图1.1.2 最短路径（2）对应为（元素可重复的）排列问题：路径（蓝色）排列排列路径（红色）结论：最短路径与7个x5个y的排列（3）求解：再对应为（元素不重复的）排列问题N792（4）一般情形：从（0，0）点到达（m，n）点的不同的最短路径数为 N1.2 两个基本法则1.2.1 加法法则（一） 加法法则l 常规描述：如果完成一件事情有两
8、个方案，而第一个方案有m种方法，第二个方案有n种方法可以实现。只要选择任何方案中的某一种方法，就可以完成这件事情，并且这些方法两两互不相同。则完成这件事情共有mn种方法。l 集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，则A与B的并共有mn个元素。l 概率角度描述：设事件A有m种产生方式，事件B有n种产生方式，则事件“A或B”有mn种产生方式。当然A与B各自所含的基本事件是互相不同的。（二） 应用【例】某班又男生18人，女生12人，从中选出一名代表参加会议，问共有多少种选法？（解）（1）两个选择方案：选男生（18种选法）或女生（12种选法）。由加法法则，全班共有181230选
9、法。（2）设集合：A男生，B女生。该班中的学生要么属于A，要么属于B，且AB，故181230。（3）事件A选男生（18种可能），事件B选女生（12种可能）。事件“A或B” 选男生或女生，由加法法则，有181230种可能。【例】用一个小写英文字母或一个阿拉伯数字给一批机器编号，问总共可能编出多少种号码？（解）261036个。其中英文字母共有26个，数字09共10个。1.2.2 乘法法则（一） 乘法法则l 常规描述：如果完成一件事情需要两个步骤，而第一步有m种方法、第二步有n种方法去实现。则完成该件事情共有mn种方法。l 集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，记为一有序对
10、。所有有序对构成的集合称为A和B的积集（或笛卡儿乘积），记作。那么，共有个元素。l 概率角度描述：设离散型随机变量X有m个取值，Y有n个取值，则离散型随机向量（X，Y）有种可能的取值。（二） 应用【例】仍设某班有男生18人，女生12人，现要求从中分别选出男女生各一名代表全班参加比赛，问共有多少种选法？（解）（1）分两步挑选，先选女生（12种选法），再选男生（18种选法）。由乘法法则，全班共有1218216种选法。（2）设集合：A男生，B女生。由乘法法则，AB1812216。（3）变量X男生（18种取值），变量Y女生（12种取值）。由乘法法则，随机向量（X，Y），有1812216种可能的值。【例
11、】给程序模块命名，需要用3个字符，其中首字符要求用字母AG或UZ，后两个要求用数字19，问最多可以给多少种程序命名？（解）先由加法法则，首字符有7613种选法。其次，再由乘法法则，最多可以产生13991053个不同的名称（数字可重复使用）。【例】从A地到B地有条不同的道路，从A地到C地有条不同的道路，从B地到D地有条不同的道路，从C地到D地有条不同的道路，那么，从A地经B或C到达目的地D共有多少种不同的走法? （解）首先，由乘法法则，从A地经B到达D地共有种走法, 由A经C到达D共有种走法,再由加法法则知, 从A地经B或C到达D地共有种不同的走法。例2334181.3 排列与组合1.3.1 相
12、异元素不允许重复的排列数和组合数（一） 计算公式从n个相异元素中不重复地取r个元素的排列数和组合数：排列： 组合： 例：n5，r3，即元素为1，2，3，4，5 排列：134，143，314，341，413，431；254，425，组合：134，245，特点：排列考虑顺序，组合不然。（二） 数学模型（1）排列问题：将r个有区别的球放入n个不同的盒子，每盒不超过一个，则总的放法数为P(n，r)。（2）组合问题：将r个无区别的球放入n个不同的盒子，每盒不超过一个，则总的放法数为C(n，r)。对应关系元素盒子位置球元素和位置编号12345A B C排列1ABC1 3 4排列2CBA4 3 1排列3AC
13、B1 4 3排列4ACB2 5 4排列5BAC4 2 5组合11 3 4组合22 4 51.3.2 相异元素允许重复的排列（一） 问题从n个不同元素中允许重复地选r个元素的排列，简称r元重复排列，排列数记为RP(，r)。（二） 模型将r个不相同的球放入n个有区别的盒子，每个盒子中的球数不加限制而且同盒的球不分次序。对应关系元素盒子位置球元素和位置编号12345A B C排列1ABC1 1 4排列2C BA4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5（三） 计算公式RP(，r) 。（四） 集合描述方式设无穷集合，从S中取r个元素的排列数即为RP(，r)。不重复排列：S。1.3.3 不尽相异元素的全排列（一） 问题有限重复排列（或部分排列）：设（），从S中任取r个元素，求其排列数RP(n，r)。（二） 模
