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

《《组合数学》教案 1章(排列组合基础)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《组合数学》第一章组合数学基础第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阶幻方。81627635795149243

2、8图1.1.13阶幻方奇数阶幻方的生成方法：一坐上行正中央，依次斜填切莫忘，62/62《组合数学》第一章组合数学基础上边出格往下填，右边出格往左填，右上有数往下填，右上出格往下填。例：将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名军官均来自不同的团队且具有不同军衔？本问题的答案是否定的。A1B2C3D4E5F6A1B2C3D4E5F6B2C3D4E5F6A1B3C

3、4D5E6F1A2C3D4E5F6A1B2C5D6E1F2A3B4D4E5F6A1B2C3D2E3F4A5B6C1E5F6A1B2C3D4E4F5A6B1C2D3F6A1B2C3D4E5F6【例1.1.2】（计数——图形染色）用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。求本质上不同的染色方案。举例：ryybbbrb（a）（b）62/62《组合数学》第一章组合数学基础形式总数：＝81种。实际总数（见第6章）：L＝＝24【例1.1.3】（存在性）不同身高的26个人随意排成一行，那么，总能从

4、中挑出6个人，让其出列后，他们的身高必然是由低到高或由高到低排列的（见第5章）。注意：不改变原来的相对顺序。（一）研究内容算法分类：l第一类：数值算法。主要解决数值计算问题，如方程求根、解方程组、求积分等，其数学基础是《高等数学》与《线性代数》（解决建模问题，《数值分析》或称《计算方法》解决离散化问题，即在计算机上的求解方法问题）。l第二类：组合算法。解决搜索、排序、组合优化等问题，其数学基础就是《组合数学》。按所研究问题的类型，研究内容：l组合计数理论l组合设计l组合矩阵论l组合优化本课程重点：以组合计数理论为主，部分涉及其它内容。（二）研究方法分类：第一类：从组合学基本概念、基本原

5、理出发解题的所谓常规方法（利用容斥原理、二项式定理、Pólya定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等）。62/62《组合数学》第一章组合数学基础第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如：（1）数学归纳法：前提是已知问题的结果。（2）迭代法【例】如已知数列满足关系，求的解析表达式。（解）直接迭代即得：＝＋1＝＝＝＝＝（3）一一对应技术原理：建立两类事物之间的一一对应关系，把一个较复杂的组合计数问题A转化成另一个容易计数的问题B，从而利用对B的计数运算达到对A的各种不同方案的计数。思路：将未解决问题的模式转化为一种已经解决的

6、问题模式。（4）殊途同归方法原理：从不同角度讨论计数问题，以建立组合等式。应用：组合恒等式的证明（也称组合意义法）。（5）数论方法特别是利用整数的奇偶性、整除性等数论性质进行分析推理的方法。62/62《组合数学》第一章组合数学基础组合数学用的较多的是方法（3）与（4）。【例1.1.4】有100名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军共需要进行多少场比赛？（解）常规思路：50＋25＋12＋6＋3＋2＋1＝99场10000名选手：5000＋2500＋1250＋625＋312＋…＋1采用一一对应方法：每场比赛产生一个失败者，且每个失败者只能失败一次。反之，要淘汰一个选手，必须

7、恰好经过一场比赛。结论：失败者与比赛场次之间一一对应，故应该比赛99场。一般情况：单循环淘汰制的比赛，若有n个选手参考比赛，则须经过n－1场比赛，方可产生冠军。【例1.1.5】设某地的街道将城市分割成矩形方格，某人在其住处A(0，0)的向东7个街道、向北5个街道的大厦B(7，5)处工作（见图1.1.3），按照最短路径（即只能向东或向北走），他每次上班必须经过某12个街段，问共有多少种不同的上班路线？（解）（1）将街道抽象为等长的。B(7,5)A