1、组合数学合数学吉林大学计算机科学与技术学院年9月1/55关于我关于我姓名：卢奕南姓名：卢奕南 单位：图像处理与虚拟现实研究团体单位：图像处理与虚拟现实研究团体 主要研究方向：图像处理、模式识别主要研究方向：图像处理、模式识别2/55关于教材关于教材内部试用版本内部试用版本时间：下周一下午时间：下周一下午地点：计算机大楼地点：计算机大楼 A413价格：每本价格：每本20元元组织：请各班班长带着本班教材费前来领取组织：请各班班长带着本班教材费前来领取 电话：电话：138431001753/55参考书：l机械工业出版社：组合数学，布鲁迪(Brualdi R.A.)(作者),冯舜玺(译者)l清华大学出
2、版社：组合数学，卢开澄等上网习题 组合数学（姜建国等），西安电子科技大学 4/55本学期包括到内容：本学期包括到内容：鸽巢原理和鸽巢原理和Ramsey定理（存在性问题）定理（存在性问题）基本计数方法基本计数方法容斥原理容斥原理生成函数生成函数递推关系递推关系Plya定理5/55怎样学好组合数学怎样学好组合数学组合数学经常使用方法并不高深复杂。最主要方法是组合数学经常使用方法并不高深复杂。最主要方法是 计数时合理分类计数时合理分类 组合模型转换组合模型转换（一一对应）。（一一对应）。组合分析组合分析 数学归纳法数学归纳法 反证法反证法要学好组合数学并非易事，既需要一定要学好组合数学并非易事，既需
3、要一定数学涵养数学涵养，也要进行，也要进行相当训练。相当训练。可从规模小模型着手，从中找到规律性东西，再推及普通。可从规模小模型着手，从中找到规律性东西，再推及普通。你处理问题越多，那么你能够处理下一个问题可能性也越大你处理问题越多，那么你能够处理下一个问题可能性也越大。6/557第一章第一章引言引言组合数学组合数学(简称组合学）是数学一个分支简称组合学）是数学一个分支,它起它起源于古代娱乐和休闲游戏。以后这些问题逐步源于古代娱乐和休闲游戏。以后这些问题逐步与与数论、概率统计、拓扑学、线性规划数论、概率统计、拓扑学、线性规划等学科等学科问题交织在一起，逐步形成一个理论。问题交织在一起，逐步形成
4、一个理论。广义组合数学就是离散数学，广义组合数学就是离散数学，离散数学是狭义组合数学和图论、代数结构、离散数学是狭义组合数学和图论、代数结构、数理逻辑等总称。数理逻辑等总称。工程认证工程认证7/55组合数学中著名问题组合数学中著名问题计算一些物品在特定条件下分组方法数目。这些是关于计算一些物品在特定条件下分组方法数目。这些是关于排列排列、组组合合和和整数分拆整数分拆。地图着色问题地图着色问题：对世界地图着色，每一个国家使用一个颜色。假：对世界地图着色，每一个国家使用一个颜色。假如要求相邻国家颜色相异，是否总共只需四种颜色？这是如要求相邻国家颜色相异，是否总共只需四种颜色？这是图论图论问问题。题
5、。船夫过河问题船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫船每次只能运要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫船每次只能运输一个东西。怎样把全部东西都运过河？这是输一个东西。怎样把全部东西都运过河？这是线性规划线性规划问题。问题。中国邮差问题中国邮差问题：由中国组合数学家：由中国组合数学家管梅谷管梅谷教授提出。邮递员要穿教授提出。邮递员要穿过城市每一条路最少一次，怎样行走走过旅程最短？过城市每一条路最少一次，怎样行走走过旅程最短？1856年，哈密年，哈密尔顿（尔顿（Kirkman）,旅行商问
6、题。旅行商问题。任务分配问题任务分配问题：有一些员工要完成一些任务。各个员工完成不一：有一些员工要完成一些任务。各个员工完成不一样任务所花费时间都不一样。每个员工只分配一项任务。每项任样任务所花费时间都不一样。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费时间最务只被分配给一个员工。怎样分配员工与任务以使所花费时间最少？這是少？這是线性规划线性规划問題。問題。怎样结构怎样结构幻方幻方。8/55组合数学起源组合数学起源幻方最早记载于我国公元前幻方最早记载于我国公元前500年春秋时期年春秋时期大戴礼中，这说明中，这说明我国人民早在我国人民早在2500年前就已经知道
7、了幻方排列规律。而在国外，年前就已经知道了幻方排列规律。而在国外，公元公元130年，希腊人塞翁才第一次提起幻方年，希腊人塞翁才第一次提起幻方；公园公园1275年（宋代），杨辉著作中出现年（宋代），杨辉著作中出现10阶幻方问题和杨辉三角阶幻方问题和杨辉三角记载；记载；1666年，莱布尼茨发表年，莱布尼茨发表组合艺术组合艺术(De Art Combinatoria)，这，这是组合数学第一部专著。书中首次使用了组合论是组合数学第一部专著。书中首次使用了组合论（Combinatorics）一词。标志组合数学诞生。）一词。标志组合数学诞生。莱布尼茨：莱布尼茨：德国德国最主要最主要自然科学自然科学家、家、
8、数学数学家、家、物理学物理学家、历史学家和家、历史学家和哲学哲学家，一个举世罕见科家，一个举世罕见科学天才，和学天才，和牛顿牛顿（1643年年1月月4日日1727年年3月月31日）同为日）同为微积分微积分创建人。创建人。杨辉，杨辉，中国中国南宋南宋时期出色时期出色数学数学家和数学教育家。家和数学教育家。9/55组合分析和组合算法已经被广泛应用与组合分析和组合算法已经被广泛应用与计算机科学、管理科学、信息科学、电计算机科学、管理科学、信息科学、电子工程、人工智能、生命科学等很多领子工程、人工智能、生命科学等很多领域中。域中。10/55组合数学组合数学蓬勃发展蓬勃发展则是在计算机问世和普则是在计算
9、机问世和普遍应用之后。遍应用之后。首先，当我们研究首先，当我们研究组合问题规模很大组合问题规模很大时候，时候，计算量会很大，计算机为求解这些问题提供了计算量会很大，计算机为求解这些问题提供了有力伎俩。有力伎俩。另首先，在另首先，在计算机科学算法研究中计算机科学算法研究中数据结构数据结构+算法算法+编程语言编程语言时间复杂性和空间复杂性时间复杂性和空间复杂性计算复杂性理论计算复杂性理论、算法设计与分析算法设计与分析基础课。基础课。11/5511什么是组合数学什么是组合数学组合数学就是研究按照一定规则来安排一些离组合数学就是研究按照一定规则来安排一些离散个体问题。它包括面广，内容庞杂（包括到散个体
10、问题。它包括面广，内容庞杂（包括到组合分析、图论、组合算法、近代密码学、编组合分析、图论、组合算法、近代密码学、编码理论等），而且仍在码理论等），而且仍在很快地发展很快地发展着，因而还着，因而还没有一个统一而有效理论体系没有一个统一而有效理论体系。研究对象是离散结构，普通能够用研究对象是离散结构，普通能够用1，2，、，、，、，n表示。表示。本书仅限于讨论本书仅限于讨论n是有限自然数是有限自然数情况。情况。组合数学是研究组合数学是研究离散结构存在、计数、分析和离散结构存在、计数、分析和优化优化等问题一门学科。等问题一门学科。12/55 组合数学主要问题组合数学主要问题（1）存在性问题）存在性问题
11、满足一定条件安排存在性满足一定条件安排存在性.假如某种安假如某种安排不一定总存在，我们就需要研究存排不一定总存在，我们就需要研究存在条件。在条件。存在性是数学研究最主要问题之一存在性是数学研究最主要问题之一.许多问许多问题存在性至今也无法处理？题存在性至今也无法处理？比如数论中很多难题：哥德巴赫猜测比如数论中很多难题：哥德巴赫猜测13/5513（2）安排枚举、分类和计数）安排枚举、分类和计数假如所要求安排存在，则可能有各种假如所要求安排存在，则可能有各种不一样安排。此时，需要计数不一样不一样安排。此时，需要计数不一样方案数，并将它们进行枚举和分类。方案数，并将它们进行枚举和分类。当实际问题比较
12、复杂时候，必须有好数学当实际问题比较复杂时候，必须有好数学方法来处理方法来处理.14/55（3）结构性问题）结构性问题一个组合问题，假如已经判定解是一个组合问题，假如已经判定解是存在，那么将全部可能安排结构出存在，那么将全部可能安排结构出来是一个关键问题。来是一个关键问题。与计算机算法亲密相关与计算机算法亲密相关 经典问题：组合设计经典问题：组合设计15/55（4）优化问题）优化问题在给定优化条件下从全部安排方案在给定优化条件下从全部安排方案中找出最优安排方案。中找出最优安排方案。l旅行商问题(Traveling Salesman Problem，简称TSP)与算法分析亲密相关与算法分析亲密相
13、关传统方法传统方法当代智能方法当代智能方法16/55幻方问题幻方问题有趣数学游戏有趣数学游戏幻方在娱乐数学中地位以及它意义非同幻方在娱乐数学中地位以及它意义非同普通，它是中国人首创。普通，它是中国人首创。公元前公元前22002200年年易经易经提到提到洛书洛书与与河图河图 1.1幻方问题幻方问题17/5517816357412一个n阶幻方是由整数1，2，3，n2按下述方式组成nn方阵：该方阵每行上整数和、每列上整数和以及两条对角线中每条对角线上整数和都等于同一个数s 18/55193阶幻方全部整数和为阶幻方全部整数和为15；每一行（或列或对角线）数字和称为每一行（或列或对角线）数字和称为幻幻方
14、和（幻和）：方和（幻和）：S=n(n2+1)/2。19/55关于幻方问题归结为关于幻方问题归结为（一）存在性问题（一）存在性问题对任意正整数对任意正整数n，n阶幻方存在吗？阶幻方存在吗？（二）组累计数问题（二）组累计数问题假如存在，那么应该有多少个不一样假如存在，那么应该有多少个不一样n阶幻方。阶幻方。（三）结构问题（三）结构问题奇数阶幻方：连续摆数法奇数阶幻方：连续摆数法(deLaLoubre法法)双偶数（双偶数（4k）阶幻方：对称法）阶幻方：对称法单偶数单偶数(4k+2)阶幻方：斯特雷奇法（阶幻方：斯特雷奇法（1918）20/552024年11月30日21（一）幻方存在性问题（一）幻方存在
15、性问题 例1.1 证实了不存在2阶幻方。对其余正整数n，因为n阶幻方都能结构出来，当然就证实了（正整数）阶幻方存在性。21/55例例1.1 证实不存在证实不存在2阶幻方阶幻方证实：证实：反证法。假定存在2阶幻方，如图所表示：a1a2a3a4依据幻方定义，它幻和是5，于是a1+a2=a1+a3=5，可得a2=a3，因为a1，a2，a3，a4必定彼此不一样，所以不可能，矛盾。所以不存在2阶幻方。22/5522（二）（二）幻方结构性问题幻方结构性问题（1）奇数阶幻方结构）奇数阶幻方结构连续摆放法（连续摆放法（delaLoubre法）。法）。规则为：规则为：假定结构假定结构n阶（阶（n为奇数）幻方为奇
16、数）幻方。首先首先将将1放在放在(n+1)/2列第列第1行方格中，行方格中，然后然后按照副对角线方向（即行号减按照副对角线方向（即行号减1，列号加列号加1）依次把从小到大各个数字放入）依次把从小到大各个数字放入对应方格中。对应方格中。23/552024年11月30日23假如行号变成假如行号变成0（第（第1行上面一行），行上面一行），则改成第则改成第n行对应列对应方格。行对应列对应方格。假如列号变成假如列号变成n+1（第（第n列右面一列），列右面一列），则改成第则改成第1列对应行对应方格。列对应行对应方格。假如轮到方格已经填有数字或者到了假如轮到方格已经填有数字或者到了第第0行第行第n+1列对应
17、方格，则退到前一个列对应方格，则退到前一个方格正下方方格。方格正下方方格。24/552024年11月30日24例例1.2 利用连续摆放法结构5阶幻方 17241815235714164613202210121921311182529即行号减即行号减1，列号加，列号加125/5525（2）偶数阶幻方结构）偶数阶幻方结构 当当n=4k时候，即双偶数情况时候，即双偶数情况，对称法。对称法。先把先把nn方阵分成上、下、左、右四方阵分成上、下、左、右四个个2k2k方阵。方阵。然后对于左上然后对于左上2k2k方阵进行处理，方阵进行处理，每行每列任意取二分之一（每行每列任意取二分之一（k个）方个）方格做标识
18、，如我们把这些方格涂成阴格做标识，如我们把这些方格涂成阴影。影。26/5526然后按照对称轴将这种标识方式向下和向然后按照对称轴将这种标识方式向下和向右作对称图形。经过处理后使得右作对称图形。经过处理后使得nn方阵每方阵每一行和每一列都有二分之一（一行和每一列都有二分之一（n/2）方格被涂）方格被涂成阴影。成阴影。接下来，把从接下来，把从1开始数字依次往方格里面开始数字依次往方格里面填。第一遍：从第填。第一遍：从第1行第行第1列方格开始往右，列方格开始往右，不是阴影，则填数字，假如是阴影方格，不不是阴影，则填数字，假如是阴影方格，不填数字，但对应数字加填数字，但对应数字加1。第。第1行填完后，
19、是行填完后，是第第2行第行第1列方格，依次，最终是第列方格，依次，最终是第n行第行第n列列方格。方格。27/5527这么填完之后，有二分之一方格被这么填完之后，有二分之一方格被填上了数字。填上了数字。第二遍，从第第二遍，从第n行第行第n列方格开始依列方格开始依次往左，规则同前，从次往左，规则同前，从1开始数字依次开始数字依次往方格往方格里面填。第填。第n行结束之后，是行结束之后，是第第n-1行第行第n列方格。依次，最终是第列方格。依次，最终是第1行第行第1列方格。列方格。最终就得到了幻方。最终就得到了幻方。28/5528例例1.3利用对称法结构利用对称法结构4阶幻方阶幻方 2143158125
20、92117143106151381211659429/552024年11月30日29当当n=4k+2,所谓单偶数情况所谓单偶数情况。首先把首先把nn方阵分成上、下、左、右方阵分成上、下、左、右四个四个(2k+1)(2k+1)方阵方阵,为了表示方便，为了表示方便，依次把左上、右下、右上、左下方阵编依次把左上、右下、右上、左下方阵编号为号为A,B,C,D。采取连续摆数法，把采取连续摆数法，把1(2k+1)2放在放在A中做成第一个幻方；把中做成第一个幻方；把(2k+1)212(2k+1)2放在放在B中成第二个幻方。中成第二个幻方。30/5530把把2(2k+1)213(2k+1)2放在放在C中成第三
21、个幻方。中成第三个幻方。把把3(2k+1)214(2k+1)2放在放在D中成第四个幻方。中成第四个幻方。然后，在然后，在A各行从第各行从第1列开始向右列开始向右取取m个个(m=(n-2)/4)方格，但中间一方格，但中间一行（行（k+1行）从第行）从第2列开始。列开始。31/5531把这些方格中数字与把这些方格中数字与D中对应位置中对应位置数字对换。数字对换。在在C中各行最终一列右起向左各取中各行最终一列右起向左各取m1个方格，把这些方格中数字与个方格，把这些方格中数字与B中对应位置数字对换。最终，就得到中对应位置数字对换。最终，就得到了幻方。了幻方。3232/55例例1.4结构结构6阶幻方阶幻
22、方 1592832672333426212217121923271014834353036 29 13 1831242520151611ACDBm=133/553313292856723334262122171219232710143533183036 29 13 18424252015161134/5534（三）幻方计数问题（三）幻方计数问题 3阶幻方阶幻方 基本形式只有一个 经过旋转和翻转可取得8种变形 81661835775349229435/5535 4阶幻方阶幻方 分类枚举 基本形式有880个 变形有7040个36/55 5阶幻方阶幻方 基本形式有275305224个 6阶及以上幻方
23、阶及以上幻方 即使经过大型计算机计算依然难以取得准确数字，当前只能预计出它取值范围372024年11月30日37/551.2 拉丁方问题拉丁方问题拉丁方拉丁方是另一类经典组合数学问题是另一类经典组合数学问题 n阶拉丁方阶拉丁方定义为由数字1,2,n组成nn方阵，使得在每1行、每1列中每个数字都恰好出现1次。38/552024年11月30日38拉丁方存在性问题拉丁方存在性问题 2阶拉丁方是存在阶拉丁方是存在122139/552024年11月30日39n阶拉丁方阶拉丁方是存在是存在 结构方法以下：第1行为（1,2,3,n）第2行是(2,3,n,1)，第k行为(k,k+1,n,1,k-1)，第n行为
24、（n,3,2,1）。40/552024年11月30日40例例1.5 设计一个药品临床试验以测试五设计一个药品临床试验以测试五种药品对人体药效。这五种药品编种药品对人体药效。这五种药品编号号1,2,3,4,5。然后选取。然后选取5个人，并给个人，并给每人不一样药。为了消除个体对药每人不一样药。为了消除个体对药品反应偏差，要求在连续品反应偏差，要求在连续5天里进行天里进行测试，每人天天吃一个药品。而为测试，每人天天吃一个药品。而为了消除服药时间造成药效偏差，要了消除服药时间造成药效偏差，要求求2个人不能在同个人不能在同1 天吃相同药。天吃相同药。41/5541最终满足要求试验是要形成由1,2,3,
25、4,5组成55方阵，其中每行每列中没有相同数字，即5阶拉丁方结构问题。42/55422345134512451235123412345行（人）行（人）列（天）列（天）43/5543例例36军官问题军官问题有有36名军官来自六个不一样团，含有六种名军官来自六个不一样团，含有六种不一样军衔，而且每个团每种军衔军官各不一样军衔，而且每个团每种军衔军官各有一名，能否把他们排成一个有一名，能否把他们排成一个6 6方阵，方阵，使得对每一个团与每一个军衔，在每一行使得对每一个团与每一个军衔，在每一行或每一列都有一位军官来自这个团，也都或每一列都有一位军官来自这个团，也都有一位军官有此军衔？有一位军官有此军衔
26、？是由是由Euler首先提出，实际上是组合设计中首先提出，实际上是组合设计中正交拉丁方问题，属于结构问题。正交拉丁方问题，属于结构问题。猜测？猜测？6、10、。、。44/55将这将这36名军官排成名军官排成66方阵方阵,使得使得 1)每行每列都有任一军团军官每行每列都有任一军团军官 2)每行每列都有任一军衔军官每行每列都有任一军衔军官.i:军衔军衔,j:军团军团,军官对应数偶军官对应数偶(i,j),i,j 1,6 问题等价于结构数偶问题等价于结构数偶(i,j)排成排成6阶方阵阶方阵,使得使得 1)数偶第一个数字组成拉丁方数偶第一个数字组成拉丁方;2)数偶第二个数字组成拉丁方数偶第二个数字组成拉
27、丁方;3)每个数偶只出现一次每个数偶只出现一次.45/55 两个拉丁方称为相互正交，即正交拉丁两个拉丁方称为相互正交，即正交拉丁方方.定义定义:设设A=(aij)nn,B=(bij)nn是两个是两个nn拉拉丁方丁方.令令C=(aij,bij)nn,若若Cn2对数偶互不相同对数偶互不相同,则称则称A与与B正交正交.46/55上述是两个上述是两个3阶正交拉丁方。阶正交拉丁方。2阶哪？阶哪？36军官问题即不存在军官问题即不存在6阶正交拉丁方。阶正交拉丁方。6猜测不对。猜测不对。对于只有对于只有9个军官类似问题有解：个军官类似问题有解：47/551.3涂色问题涂色问题 在实际应用中，很多计数问题都可抽
28、象成涂色问题。作为经典组累计数问题，依据涂色问题难度不一样，将反应出各种不一样计数技术。48/5548例例1.6对正三角形三个顶点涂以红、蓝（r和b）两种颜色，求有多少种不一样涂色方案？解解 因为只有两种颜色，我们能够采取枚举方法分类讨论。49/5549涂色方案可分成四类：涂色方案可分成四类：（1）三点全涂红色，只有一个方案 rrr（2）三点全涂蓝色，只有一个方案 bbb（3）两点涂红色，一点涂蓝色，因蓝色可分别涂于三个顶点之一，故有3种方案 brr，rbr，rrb（4）由对称性可知，两点涂蓝色，一点染红方案也有3种：50/5550红色,蓝色51/5551 假如考虑正三角形能够旋转，则(3),
29、(4),(5)显然是同一个涂色方案，(6),(7),(8)也是同一个涂色方案，这么涂色方案数就变成了4种。假如变成了空间四面体了，即加上空间旋转之后，涂色方法计算将愈加复杂。要涂色点和可选颜色数目如再增加话，枚举方法就不奏效了52/5552例例:棋盘完美覆盖棋盘完美覆盖mn棋盘棋盘:m行行n列方格列方格,b-牌牌:1行行b个方格条个方格条mn棋盘被棋盘被b-牌一个牌一个完美覆盖完美覆盖是是b-牌在棋盘上一个排列牌在棋盘上一个排列,满足满足:(1)每个格子恰好只被一张牌覆盖每个格子恰好只被一张牌覆盖;(2)每条每条b-牌覆盖牌覆盖b个方格个方格.定理定理:mn棋盘有棋盘有b-牌完美覆盖牌完美覆盖
30、b|m或或b|n.3 4棋盘棋盘6 6棋盘有棋盘有4-牌完美覆盖吗牌完美覆盖吗?有有2-牌完美覆盖牌完美覆盖.53/55 需要特殊技巧处理问题需要特殊技巧处理问题例例 有有101名选手参加羽毛球比赛，假如采取名选手参加羽毛球比赛，假如采取单循环淘汰制，问产生冠军需要进行多少单循环淘汰制，问产生冠军需要进行多少场比赛？场比赛？方法一：方法一：50+25+13+6+3+2+1=100场比赛 方法二：方法二：因为每场比赛都要产生一个失败者，而每个失败者只能失败一次，所以比赛场数与失败者人数相等，除冠军外其它100人都失败过，所以产生冠军需要100场比赛。例例 有一个边长为有一个边长为3立方体木块，要
31、把它切割成立方体木块，要把它切割成27个边长为个边长为1小立方体，假如在切割过程中能够重新小立方体，假如在切割过程中能够重新排列被切割木块，问最少需要多少次才能完成任排列被切割木块，问最少需要多少次才能完成任务？务？54/55解：解：首先能够看到，经过首先能够看到，经过6 6次是能够完成整个切割，次是能够完成整个切割，上图就是这么一个方案。其次，我们证实少于上图就是这么一个方案。其次，我们证实少于6 6次是次是不能完成切割。因为处于原立方体中心一个小立方体不能完成切割。因为处于原立方体中心一个小立方体每个面都是由切割产生，每次切割只能产生一个面，每个面都是由切割产生，每次切割只能产生一个面，所以切割次数不能少于它面数，所以最少所以切割次数不能少于它面数，所以最少6 6次才能完次才能完成切割。成切割。55/55
