组合数学讲义及课后答案 1章 排列组合

《组合数学讲义及课后答案 1章 排列组合》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《组合数学》第一章组合数学基础第1章组合数学基础1、排列组合的基本计数问题（研、本）2、计算多项式系数（研、本）3、排列组合算法（研）1.1绪论（一）背景起源：数学游戏2幻方问题：给定自然数1,2,…,n，将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和。例：3阶幻方，幻和＝(1＋2＋3＋…＋9)/3＝15。（1）存在性问题：即n阶幻方是否存在？（2）计数问题：如果存在，对某个确定的n，这样的幻方有多少种？（3）构造问题：即枚举问题，亦即如何构造n阶幻方。816276

2、357951492438图1.1.13阶幻方奇数阶幻方的生成方法：奇数阶幻方最经典的填法是罗伯法。填写的方法是：把1(或最小的数)放在第一行正中；按以下规律排列剩下的1/69《组合数学》第一章组合数学基础(n×n－1)个数(1)每一个数放在前一个数的右上一格；(2)如果这个数所要放的格已经超出了顶行那么就把它放在底行，仍然要放在右一列；(3)如果这个数所要放的格已经超出了最右列那么就把它放在最左列，仍然要放在上一行；(4)如果这个数所要放的格已经超出了顶行且超出了最右列，那么就把它放在前一个数的下一行同一列的格内；(5)如果这个数所要放的格已经有数填入，

3、那么就把它放在前一个数的下一行同一列的格内。一坐上行正中央，依次斜填切莫忘，上边出格往下填，右边出格往左填，右上有数往下填，右上出格往下填。例：将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名军官均来自不同的团队且具有不同军衔？本问题的答案是否定的。反例：A1B2C3D4E5F6A1B2C3D4E5F6B2C3D4E5F6A1B3C4D5

4、E6F1A2C3D4E5F6A1B2C5D6E1F2A3B42/69《组合数学》第一章组合数学基础D4E5F6A1B2C3D2E3F4A5B6C1E5F6A1B2C3D4E4F5A6B1C2D3F6A1B2C3D4E5F6例1.1.2（计数——图形染色）用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。例如，对图1.1.2的涂染方案(a)，当正方形逆时针旋转o90时就变为方案(b)，因此，在正方形可旋转的前提下，这两种方案实质上是一种方案。那么，我们要问：不同

5、的染色方案共有多少种？ybryrb（a）bb（b）图1.1.2正方形的顶点染色4染色方案的总数为：3＝81种。问题：计算不同的染色方案，但在图像可旋转条件下重合的方案只能统计一次，不同的染色方案总数为（见第6章）142L＝3323＝244例1.1.3（存在性）不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是由低到高或由高到低排列的（见第5章）。（二）研究内容算法分类：第一类：数值算法。主要解决数值计算问题，如方程求根、3/69《组合数学》第一章组合数学基础解方程组、求积分等，其数学基础是高等数学与线性代数

6、。第二类：组合算法，解决搜索、排序、组合优化等问题，其数学基础就是组合数学。按所研究问题的类型，组合数学所研究的内容可划分为：组合计数理论组合设计组合矩阵论组合优化本课程重点：以组合计数理论为主，部分涉及其它内容。（三）研究方法分类：第一类：从组合学基本概念、基本原理出发解题的所谓常规方法（利用容斥原理、二项式定理、Pólya定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等）。第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如：（1）数学归纳法：前提是已知问题的结果。（2）迭代法hn2hn1

7、1,例.如已知数列hn满足关系，求hn的解析h11表达式。直接迭代即得：h2h1nn12＝22h1＋1＝2h21n2n2232＝22hn3121＝2hn32214/69《组合数学》第一章组合数学基础n1n2n32＝2h222211n＝21（3）一一对应技术原理：建立两类事物之间的一一对应关系，把一个较复杂的组合计数问题A转化成另一个容易计数的问题B，从而利用对B的计数运算达到对A的各种不同方案的计数。思路：将未解决问题的模式转化为一种已经解决的问题模式。（4）殊途同归方法原理：从不

8、同角度讨论计数问题，以建立组合等式。应用：组合恒等式的证明（也称组合意义法）。（