[工学]1章 排列组合.doc

组合数学基础 排列组合的基本计数问题（研、本） 计算多项式系数（研、本） 排列组合算法（研） 绪 论 背景 组合数学起源于数学游戏。例如幻方问题：给定自然数1,2,…,n2，将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和。图1.1.1是一个3阶幻方，其幻和等于15。首先，人们要问： （1）存在性问题：即n阶幻方是否存在？ （2）计数问题：如果存在，对某个确定的n，这样的幻方有多少种？ （3）构造问题：即枚举问题，亦即如何构造n阶幻方。 8 1 6 2 7 6 3 5 7 9 5 1 4 9 2 4 3 8 3阶幻方 奇数阶幻方的生成方法： 一坐上行正中央，依次斜填切莫忘， 上边出格往下填，右边出格往左填， 右上有数往下填，右上出格往下填。 将2，4，6，8，10，12，14，16，18填入下列幻方： 16 2 12 6 10 14 8 18 4 36名军官问题：有1，2，3，4，5，6共六个团队，从每个团队中分别选出具有A、B、C、D、E、F六种军衔的军官各一名，共36名军官。问能否把这些军官排成6×6的方阵，使每行及每列的6名军官均来自不同的团队且具有不同军衔？ 本问题的答案是否定的。 A1 B2 C3 D4 E5 F6 A1 B2 C3 D4 E5 F6 B2 C3 D4 E5 F6 A1 B3 C4 D5 E6 F1 A2 C3 D4 E5 F6 A1 B2 C5 D6 E1 F2 A3 B4 D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1 E5 F6 A1 B2 C3 D4 E4 F5 A6 B1 C2 D3 F6 A1 B2 C3 D4 E5 F6 用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。例如，对图1.1.2的涂染方案(a)，当正方形逆时针旋转时就变为方案(b)，因此，在正方形可旋转的前提下，这两种方案实质上是一种方案。那么，我们要问：不同的染色方案共有多少种？  r y b b （a） y b r b （b） 正方形的顶点染色 染色方案的总数为：＝81种。 问题：要计算不同的染色方案，显然属于计数问题。在旋转条件下，不同的染色方案总数为（见第6章） L＝＝24 不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是由低到高或由高到低排列的（见第5章）。 研究内容 计算机科学中涉及的算法大致可分为两类： 第一类是计算方法，它主要解决数值计算问题，如方程求根、解方程组、求积分等，其数学基础是高等数学与线性代数。 第二类是组合算法，它解决有哪些信誉好的足球投注网站、排序、组合优化等问题，其数学基础就是组合数学。 按所研究问题的类型，组合数学所研究的内容可划分为： 组合计数理论 组合设计 组合矩阵论 组合优化 本书将以组合计数理论为主，部分涉及其它内容。 研究方法 分类： 第一类：从组合学基本概念、基本原理出发解题的所谓常规方法，例如，利用容斥原理、二项式定理、Pólya 定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等。 第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如： 数学归纳法：前提是已知问题的结果。 迭代法。 例如已知数列满足关系，求的解析表达式。 直接迭代即得： ＝ 一一对应技术 这是组合数学理论常用的一个计数技巧。其原理就是建立两个事物之间的一一对应关系，把一个较复杂的组合计数问题A转化成另一个容易计数的问题B，从而利用对B的计数运算达到对A的各种不同方案的计数。它的应用是多方面的，在组合学中最常见的是利用它将问题的模式转化为一种已经解决的问题模式。 殊途同归方法 即从不同角度讨论计数问题，以建立组合等式，尤其是在组合恒等式的证明中，故也称组合意义法。 数论方法 特别是利用整数的奇偶性、整除性等数论性质进行分析推理的方法。 组合数学用的较多的是方法（3）与（4）。 有100名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军共需要进行多少场比赛？ 解 常规思路：50+25+12+6+3+2+1场 采用一一对应方法：因为采用的是单循环淘汰制，所以每两名选手比赛产生一个失败者，且每个失败者只能失败一次。因此，失败的人数与比赛场数之间一一对应，计算比赛场数问题转化为计算失败人数问题。后者的解显然是99人，故应该比赛99场。 设某地