组合数学第一章

1、2021-10-24计算机科学与技术学院1组合数学组合数学Combinatorics吉林大学吉林大学计算机科学与技术学院计算机科学与技术学院计算机图形学与数字媒体计算机图形学与数字媒体郭晓新郭晓新 副教授副教授2021-10-24计算机科学与技术学院2第一章第一章 引言引言 n组合数学的发展历史组合数学的发展历史n组合数学的概念组合数学的概念n组合数学研究的主要内容组合数学研究的主要内容n教材的主要内容教材的主要内容2021-10-24计算机科学与技术学院3组合数学的发展组合数学的发展 n1666年，莱布尼茨发表年，莱布尼茨发表组合的艺术组合的艺术(De Art Combinatoria)，这

2、是组合数学的第一部专著。书中首次使用了组合论这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。标志组合数学的诞生。）一词。标志组合数学的诞生。 n17世纪的学者帕斯卡和费马研究了与博弈相关的组合问题，还提世纪的学者帕斯卡和费马研究了与博弈相关的组合问题，还提出了概率的概念。帕斯卡和费马的工作奠定了概率论的基础。出了概率的概念。帕斯卡和费马的工作奠定了概率论的基础。n18世纪，拉普拉斯使用有利情形定义了概率。世纪，拉普拉斯使用有利情形定义了概率。n同在同在18世纪，结合著名的哥尼斯堡桥问题，欧拉发明了图论，而世纪，结合著名的哥尼斯堡桥问题，欧拉发明了图论，而伯努利

3、出版了第一本展示组合方法的书伯努利出版了第一本展示组合方法的书猜度术猜度术。n在在18世纪和世纪和19世纪，哈密尔顿和其他人把组合数学应用于拼图和世纪，哈密尔顿和其他人把组合数学应用于拼图和游戏的研究中。游戏的研究中。n在在19世纪，基尔霍夫发展了电网的图论方法，而凯莱发展了有机世纪，基尔霍夫发展了电网的图论方法，而凯莱发展了有机化学研究中的枚举技术。化学研究中的枚举技术。2021-10-24计算机科学与技术学院4n组合数学，也称组合学或组合分析，是数学的一个分组合数学，也称组合学或组合分析，是数学的一个分支。它研究事物在给定模式下的配置，研究这种配置支。它研究事物在给定模式下的配置，研究这种

4、配置的存在性，所有可能配置的计数和分类，以及配置的的存在性，所有可能配置的计数和分类，以及配置的各种性质。各种性质。n简单地说，简单地说，组合数学是组合数学是“按照一定的规则（模式）来按照一定的规则（模式）来安排一些离散个体安排一些离散个体”。组合数学组合数学2021-10-24计算机科学与技术学院5研究的内容研究的内容n安排的存在性（存在性问题）安排的存在性（存在性问题）如果想把离散对象按照它们所应满足的条件来进行安排，当符合如果想把离散对象按照它们所应满足的条件来进行安排，当符合要求的安排并非显然存在或显然不存在时，首要的问题就是要证要求的安排并非显然存在或显然不存在时，首要的问题就是要证

5、明或否定它的存在。明或否定它的存在。n安排的枚举、分类和计数（计数问题）安排的枚举、分类和计数（计数问题）如果所要求的安排存在，则可能有多种不同的安排。此时，就可如果所要求的安排存在，则可能有多种不同的安排。此时，就可以计数不同的方案数，并将它们进行枚举和分类。以计数不同的方案数，并将它们进行枚举和分类。 n构造性问题构造性问题研究怎样构造出所需要的安排方法。研究怎样构造出所需要的安排方法。n优化问题优化问题此类问题是在一定条件下找出一个（或几个）最优或近乎最优的此类问题是在一定条件下找出一个（或几个）最优或近乎最优的安排方案。安排方案。如果安排的原则带有技巧性或比较复杂，那么存在性问题就成为

6、主如果安排的原则带有技巧性或比较复杂，那么存在性问题就成为主要问题，而在实际应用中更多的是计数问题和优化问题。要问题，而在实际应用中更多的是计数问题和优化问题。 2021-10-24计算机科学与技术学院6重点：组合计数问题重点：组合计数问题n第二章第二章 鸽巢原理和鸽巢原理和Ramsey定理定理组合数学中最主要的存在性定理组合数学中最主要的存在性定理n第三章第三章 基本计数原理基本计数原理加法原则、乘法原则，排列组合，二项式定理，多项式定理加法原则、乘法原则，排列组合，二项式定理，多项式定理n第四章第四章 容斥原理容斥原理容斥原理，错位排列，有限制条件的排列问题，容斥原理，错位排列，有限制条件

7、的排列问题，M Mbiusbius反演反演n第五章第五章 生成函数及其应用生成函数及其应用 组合数的生成函数，排列数的指数型生成函数，组合数的生成函数，排列数的指数型生成函数，CatalanCatalan数列、数列、StirlingStirling数列、分拆数的生成函数数列、分拆数的生成函数 n第六章第六章 递推关系递推关系常系数线性齐次递推关系常系数线性齐次递推关系 ，常系数线性非齐次递推关系常系数线性非齐次递推关系 n第七章第七章 P Plyalya定理定理置换群，置换群，BurnsideBurnside引理，引理，P Plyalya定理定理排列和组合的生成以及带权的排列和组合的生成以及带

8、权的Polya定理为构造问题。定理为构造问题。组合组合计数计数的各的各种方种方法和法和技巧技巧2021-10-24计算机科学与技术学院7安排的存在性（存在性问题）安排的存在性（存在性问题） n例例 1.1 幻方问题，它最早起源于中国古代的洛书河图幻方问题，它最早起源于中国古代的洛书河图（公元前（公元前2100多年）多年） 。4923578162021-10-24计算机科学与技术学院8安排的存在性（存在性问题）安排的存在性（存在性问题） nn阶幻方是由整数阶幻方是由整数1，2，3，n2按下述方式组成的按下述方式组成的方阵：该方阵每行上的整数的和、每列上的整数的和方阵：该方阵每行上的整数的和、每列

9、上的整数的和以及两条对角线中每条对角线上的整数的和都等于同以及两条对角线中每条对角线上的整数的和都等于同一个数一个数s。这个整数。这个整数s就叫做该幻方的幻和。就叫做该幻方的幻和。n下面是下面是3阶和阶和4阶幻方的两个例子：阶幻方的两个例子：这两个幻方的幻和分别是这两个幻方的幻和分别是15和和34。 294753618114154127698111051323162021-10-24计算机科学与技术学院9安排的存在性（存在性问题）安排的存在性（存在性问题）n一个一个n阶幻方中的所有整数的和为阶幻方中的所有整数的和为由于一个由于一个n阶幻方共有阶幻方共有n行，每一行都有一个幻和行，每一行都有一个

10、幻和s，因，因此我们得到关系。此我们得到关系。于是，任意两个于是，任意两个n阶幻方都有相同的幻和，即阶幻方都有相同的幻和，即不难验证，不可能存在不难验证，不可能存在2阶幻方（其幻和应该是阶幻方（其幻和应该是5）。但）。但是，对于所有其他的是，对于所有其他的n，n阶幻方能够构造出来。存在着阶幻方能够构造出来。存在着许多构造幻方的特殊方法。许多构造幻方的特殊方法。 2) 1(321222nnn2/ ) 1(22nnns2(1) 2sn nabc2021-10-24计算机科学与技术学院10构造性问题构造性问题n例例1.4 构造构造3阶幻方阶幻方解：解： 3阶幻方幻和阶幻方幻和/p>

11、852123456789551928374612314712437()()()()4 153 15315510()()30230()20aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 且又a1a2a3a4a5a6a7a8a9(1)(2)(3)(4)(5)(6)2021-10-24计算机科学与技术学院11构造性问题构造性问题得得所以所以a2，a4有相间的奇偶性从而有相间的奇偶性从而a2，a4，a6，a8的奇偶性也相同，的奇偶性也相同，所以所以a1，a3，a5，a7的奇偶性相同（因为的奇偶性相同（因为19（除去（除去5）有）有4个奇数和个奇数和4个偶数，个偶数

12、，a2，a4，a6，a8的奇偶性相同时，的奇偶性相同时，a1，a3，a5，a7的奇偶性必相同）。的奇偶性必相同）。所以所以a1+a7为偶数但为偶数但a1+a4+a7=15，因，因此此a4必为奇数（否则必为奇数（否则a1，a7奇偶性不同），奇偶性不同），从而三阶幻方的四角全是偶数从而三阶幻方的四角全是偶数 2412(10)aaaa1a2a3a4a5a6a7a8a9(7)12437230()20aaaaa(6)2021-10-24计算机科学与技术学院12构造性问题构造性问题若将若将2放在左上角，即令放在左上角，即令a1=2，则，则a9=8，这时，若，这时，若a3=4 (或或6)，则，则a7=6 (

13、或或4)。这就是说，这就是说，2放在左上角可得两个三阶幻方，而放在左上角可得两个三阶幻方，而2可放可放在四个角中的任在四个角中的任个角上，由此可知，共有个角上，由此可知，共有4 2=8个三个三阶幻方若从同构的意义讲，则三阶幻方只有一个，阶幻方若从同构的意义讲，则三阶幻方只有一个，换句话说，可以从一个幻方经翻转、旋转而得到其余换句话说，可以从一个幻方经翻转、旋转而得到其余七个七个a1a2a3a4a5a6a7a8a92769514382947536182021-10-24计算机科学与技术学院13幻方的构造性问题幻方的构造性问题（1）奇数阶幻方的构造）奇数阶幻方的构造n连续摆放法（连续摆放法（de

14、la Loubre法）。法）。n规则为：假定构造规则为：假定构造n阶（阶（n为奇数）为奇数）幻方。幻方。n首先首先将将1放在放在(n+1)/2列第列第1行的方格行的方格中，中，n然后然后按照副对角线方向（即行号减按照副对角线方向（即行号减1，列号加，列号加1）依次把从小到大的各）依次把从小到大的各个数字放入相应的方格中。个数字放入相应的方格中。n如果行号变成如果行号变成0（第（第1行上面一行），行上面一行），则改成第则改成第n行相应列对应的方格。行相应列对应的方格。n如果列号变成如果列号变成n+1（第（第n列右面一列右面一列），则改成第列），则改成第1列相应行对应的列相应行对应的方格。方格。n

15、如果轮到的方格已经填有数字或者如果轮到的方格已经填有数字或者到了第到了第0行第行第n+1列对应的方格，则列对应的方格，则退到前一个方格正下方的方格。退到前一个方格正下方的方格。 17241815235714164613202210121921311182529n利用连续摆放法构造5阶幻方2021-10-24计算机科学与技术学院14幻方的构造性问题幻方的构造性问题2021-10-24计算机科学与技术学院15幻方的构造性问题幻方的构造性问题214315812592021-10-24计算机科学与技术学院16幻方的构造性问题幻方的构造性问题211714310615138121165942021-10-

16、24计算机科学与技术学院1721171431061513812116594幻方的构造性问题幻方的构造性问题1 12 2 6262 6161 6060 59597 78 85656 1010 1111 5353 5252 1414 1515 49494848 4747 1919 2020 2121 2222 4242 41412525 3939 3838 2828 2929 3535 3434 32323333 3131 3030 3636 3737 2727 2626 40402424 2323 4343 4444 4545 4646 1818 17171616 5050 5151 1313

17、1212 5454 55559 95757 58586 65 54 43 3 6363 64642021-10-24计算机科学与技术学院18幻方的构造性问题幻方的构造性问题ACDB2021-10-24计算机科学与技术学院19幻方的构造性问题幻方的构造性问题 192867233342621221712192327101433036 29 13 18242520151611ACDB2021-10-24计算机科学与技术学院20幻方的构造性问题幻方的构造性问题ACDB192867233342621221712192327101433036 29 13 1824252015161119286723334

18、2621221712192327101433036 29 13 18242520151611ACDB2021-10-24计算机科学与技术学院21幻方的构造性问题幻方的构造性问题1717 2424 1 18 8 1515 6767 7474 5151 5858 65652323 5 57 7 1414 1616 7373 5555 5757 6464 66664 46 6 1313 2020 2222 5454 5656 6363 7070 72721010 1212 1919 2121 3 3 6060 6262 6969 7171 53531111 1818 2525 2 29 9 6161

19、 6868 7575 5252 59599292 9999 7676 8383 9090 4242 4949 2626 3333 40409898 8080 8282 8989 9191 4848 3030 3232 3939 41417979 8181 8888 9595 9797 2929 3131 3838 4545 47478585 8787 9494 9696 7878 3535 3737 4444 4646 28288686 9393 100100 7777 8484 3636 4343 5050 2727 34349292 9999 1 18 8 1515 6767 7474 5

20、151 5858 40409898 8080 7 7 1414 1616 7373 5555 5757 6464 41414 4 8181 8888 2020 2222 5454 5656 6363 7070 47478585 8787 1919 2121 3 3 6060 6262 6969 7171 28288686 9393 2525 2 29 9 6161 6868 7575 5252 34341717 2424 7676 8383 9090 4242 4949 2626 3333 65652323 5 5 8282 8989 9191 4848 3030 3232 3939 6666

21、7979 6 6 1313 9595 9797 2929 3131 3838 4545 72721010 1212 9494 9696 7878 3535 3737 4444 4646 53531111 1818 100100 7777 8484 3636 4343 5050 2727 59592021-10-24计算机科学与技术学院22幻方的计数问题幻方的计数问题 3阶幻方阶幻方 基本形式只有一种基本形式只有一种 经过旋转和翻转可获得经过旋转和翻转可获得8种变形种变形 4阶幻方阶幻方 分类枚举分类枚举 基本形式有基本形式有880个个 变形有变形有7040个个 5 阶幻方阶幻方 基本形式有基本

22、形式有275305224个个6 阶及以上幻方阶及以上幻方 即使通过大型计算机的计算仍然难以获得精确的数字，目前只即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值范围能估计出它的取值范围2021-10-24计算机科学与技术学院23n 拉丁方拉丁方是另一类典型的组合数学问题是另一类典型的组合数学问题n n阶拉丁方阶拉丁方定义为由数字1,2,n构成的nn的方阵，使得在每1行、每1列中每个数字都恰好出现1次。 2阶拉丁方是存在的阶拉丁方是存在的 1221拉丁方问题拉丁方问题1232313121233122312021-10-24计算机科学与技术学院24nn阶拉丁方阶拉丁方是存在的

23、是存在的 n构造方法如下：n第1行为（1,2,3,n）n第2行是(2,3,n,1)，n第k行为(k,k+1,n,1, ,k-1)，n第n行为（n, n-3,n-2,n-1）。 拉丁方构造问题拉丁方构造问题1232313121233122312021-10-24计算机科学与技术学院25拉丁方构造性问题拉丁方构造性问题 2021-10-24计算机科学与技术学院26拉丁方构造性问题拉丁方构造性问题最后满足要求的实验是要形成由1,2,3,4,5构成的55的方阵，其中每行每列中没有相同的数字，即5阶拉丁方的构造问题。n共有共有161280个不同的个不同的5阶拉丁方阶拉丁方2345134512451235

24、123412345ABCDE第一天第二天第三天第四天第五天2021-10-24计算机科学与技术学院27123123(1,1)(2,2)(3,3)312231(3,2)(1,3)(2,1)231312(1,1)(1,1)2,3)(3,1)(1,2)123132(1,3,2)231321(3,2)3(2,3)(2,3)(2,3)12213(3,2)1)正交拉丁方正交拉丁方构造性问题正交拉丁方构造性问题并置矩阵2021-10-24计算机科学与技术学院28正交拉丁方正交拉丁方n容易看出，不存在容易看出，不存在2阶拉丁方，因为阶拉丁方，因为2阶拉丁方共有阶拉丁方共有2个，个，但两者彼此不正交。但两者彼此不正交。1221(1,2)(2,1)2112(2,1)(1,2)2021-10-24计算机科学与技术学院29正交拉丁方正交拉丁方n例例 正交拉丁方源于正交拉丁方源于Euler提出的提出的“36军官问题军官问题”。设。设有分别来自有分别来自6个军团共有个军团共有6种不同军衔的种不同军衔的36名军官，他名军官，他们能否排成们能否排成66（6行行6列）的方阵使得每