1、浅谈组合数学浅谈组合数学南开大学南开大学 组合数学中心组合数学中心 陈永川陈永川组合数学概述组合数学概述n 现代数学可以分为两大类：一类是研究连现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等；另一类就是续对象的，如分析、方程等；另一类就是研究离散对象的组合数学。研究离散对象的组合数学。 n 计算机出现以后，由于离散对象的处理是计算机出现以后，由于离散对象的处理是计算机科学的核心，研究离散对象的组合计算机科学的核心，研究离散对象的组合数学得到迅猛发展数学得到迅猛发展 。组合数学概述组合数学概述n 吴文俊吴文俊 院士指出，每个时代都有它特殊的要求，院士指出，每个时代都有它特殊的要求，
2、使得数学出现一个新的面貌，产生一些新的数学使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求分支，组合数学这个新的分支也是在时代的要求下产生的。下产生的。n 最近，最近， 吴文俊吴文俊 院士又指出，信息技术很可能会给院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。将显示出它的重要作用。 n Gian-Carlo Rota教授曾提出要向中国领导人呼吁教授曾提出要向中国领导人呼吁，组合数学是计算机软件产业的基础，中国最终，组合数学是计算机软件产业的基础，中国最终一定能成为一个软
3、件大国，但是要实现这个目标一定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。的一个突破点就是发展组合数学。 组合数学的历史组合数学的历史n 传说在公元前传说在公元前 23世纪大禹世纪大禹治水的时候，在黄河支流治水的时候，在黄河支流洛水中，浮现出一个洛水中，浮现出一个 大乌大乌龟，甲上背有龟，甲上背有 9种花点的图种花点的图案，人们将图案中的花点案，人们将图案中的花点数了一下，竞惊奇地发现数了一下，竞惊奇地发现 9种花点数正巧是种花点数正巧是 1 9这这 9个个数，各数位置的排列也相数，各数位置的排列也相当奇妙，横的当奇妙，横的 3行、纵的行、纵的 3列以及两对角线上各自的
4、列以及两对角线上各自的数字之和都为数字之和都为 15。上图为三阶洛书幻方问题幻方问题n 组合数学中有许多象幻方这样精巧的结组合数学中有许多象幻方这样精巧的结构。构。n 1977年美国旅行者年美国旅行者 1号、号、 2号宇宙飞船就号宇宙飞船就带上了幻方以作为人类智慧的信号。带上了幻方以作为人类智慧的信号。神农幻方2200BC1 15 14 412 6 7 98 10 11 513 3 2 16 15世纪阶幻方阿基米德手稿阿基米德手稿n 上图为一份用希腊文写在羊皮纸上的上图为一份用希腊文写在羊皮纸上的 阿基米阿基米德德 手稿副本手稿副本 , 最近科学家借助现代科技手段初最近科学家借助现代科技手段初
5、步破译了古希腊数学家阿基米德的这篇论文步破译了古希腊数学家阿基米德的这篇论文 , 结论是这篇被称作结论是这篇被称作 Stomachion的论文解决的是的论文解决的是组合数学问题。组合数学问题。 阿基米德手稿阿基米德手稿n 在论文中阿基米德是在计算把在论文中阿基米德是在计算把 14条不规则的条不规则的纸带拼成正方形一共能有多少种不同的拼纸带拼成正方形一共能有多少种不同的拼法。这在现在被称为法。这在现在被称为 tiling问题。问题。n 当今数学家借助计算机得出的答案是当今数学家借助计算机得出的答案是 17152种拼法，这在当时是相当困难的。种拼法，这在当时是相当困难的。 Periodic Til
6、ings Non-Periodic Tilings Penrose Tilings Symmetric Tilings Symmetric Tilings 贾宪三角贾宪三角n 中国最早的组合数学中国最早的组合数学理论可追溯到宋朝时理论可追溯到宋朝时期的期的 ”贾宪三角贾宪三角 ”, 后来后来被杨辉引用被杨辉引用 , 所以普遍所以普遍称之为称之为 ”杨辉三角杨辉三角 ”, 这这在西方是在西方是 1654年由帕斯年由帕斯卡提出，但比中国晚卡提出，但比中国晚了了 400多年。多年。11， 11， 2， 11， 3， 3， 11， 4， 6， 4， 11， 5， 10， 10， 5， 11， 6， 15， 20， 15， 6， 1七桥问题七桥问题n 近代图论的历史可追溯到近代图论的历史可追溯到 18世纪的世纪的 七桥问题七桥问题 穿过穿过 Knigsberg城的七座桥，要求每座桥通城的七座桥，要求每座桥通过一次且仅通过一次。过一次且仅通过一次。n Euler1736年证明了不可能存在这样的路线。年证明了不可能存在这样的路线。
