组合数学漫谈

1、组合数学漫谈组合数学漫谈要点要点组合数学的问题组合数学的问题组合数学的内容组合数学的内容组合数学的应用组合数学的应用中国的组合数学中国的组合数学组合数学的问题组合数学概述组合数学（Combinatorial Mathematics) 也称组合学(Combinatorics) 或离散数学(Discrete Mathematics)现代数学根据所研究的对象可分为两类： 连续数学：以微积分为基础，传统主流 离散数学：伴随计算机科学，方兴未艾1666年Leibniz著Dissertatio de arte combinatoria,首次使用了组合一词。阿基米德宝盒 左上图为一份用希腊文写在羊皮纸上的A

2、rchimedes手稿“Stomachion”的副本, 它考虑的是现在名为“tiling”的组合问题 StomachionArchimedes(287? -212 B.C.)在计算把14条不规则的纸带拼成正方形有多少种不同的拼法。Bill Cutler （2003）：答案是17152=536x32Knigsberg七桥问题七桥问题Pregel河横穿Knigsberg城，河上建有七座桥 ，能否设计散步路线，走过所有七座桥，每座桥恰好经过一次而回到同一地点？Euler环游（一笔画）Euler于1736年给以否定： 图有这样的路线当且仅当 每个点连接偶数条边。图论的起源三十六军官问题 普鲁士腓特烈大

3、帝在一次检阅中要求： 从不同的6个军团各选6种不同军衔的6名军官共36人，排成一个6行6列的方队，使得各行各列的6名军官恰好来自不同的军团而且军衔各不相同。 Euler（1779）：办不到! 但末能给出严格的证明 。 拉丁方阵与拉丁方阵与正交拉丁方阵正交拉丁方阵 每名军官对应一个有序对（军团，军衔） 以9名军官为例： 军团阵列 军衔阵列 并置阵列 （拉丁方阵）（拉丁方阵） （拉丁方阵）（拉丁方阵） （正交拉丁方阵）正交拉丁方阵）)2 , 1 () 1 , 3()3 , 2() 1 , 2()3 , 1 ()2 , 3()3 , 3()2 , 2() 1 , 1 (213132321132213

4、321Euler猜想Euler(1779)：不存在4t+2阶正交拉丁方？Tarry(1900)：不存在6阶正交拉丁方！ 存在10阶正交拉丁方！Bose, Shrikhande和Parker(1960)： 当t2时，存在4t+2阶正交拉丁方！ 首次数学上了The New York Times的头版！四色猜想英国大学生Guthrie（1852）：一张地图，只需要四种颜色就能保证每两个相邻的地区颜色不同？四色定理Kemple（1879）： 给出“证明”。Heawood（1890）： 指出漏洞。五色定理。Appel-Haken(1976)： 给出计算机证明（1200小时100亿个判断）。 （右图为Ap

5、pel ）Kirkman女生问题Kirkman （18061895）1850年：有15个女生，她们每天要做三人行的散步，要使每个女生在一周内的每天做三人行散步时，与其她同学在组成三人小组同行时，彼此只有一次相遇在同一小组，应怎样安排？组合设计的起源Kirkman女生问题的一个解SunABCDEFGHIJKLMNOMonADHBEKCIOFLNGJMTueAEMBHNCGKDILFJOWedAFIBLOCHJDKMEGNThuAGLBDJCFMEHOIKNFriAJNBIMCELDOGFHKSatAKOBFGCDNEIJHLMKirkman三元系Kirkman三元系：把v个女学生分成v/3组，使

6、得在每(v1)/2天内任意两个女生在同一组内只相遇一次。Ray-Chaudhuri 和Wilson （1971）：Kirkman三元系存在的充要条件是v=6k+3相识问题任何六人中必有三人彼此相识或互不相识。以点表人，连红线表相识，蓝线表不相识。那么六个点的 完全图里或有红三角形或有蓝三角形。五个点的则不然。Ramsey定理Ramsey(1903-1930)：给定任意正整数p和q，总存在一个最小正整数R(p,q)，使得R(p,q)个人中或者有 p 个人互相认识，或者有 q 个人互不相识。R(p,q) 称为Ramsey数。只要人数足够多，则互相认识的人会越来越多，或互不相识的人会越来越多。Ram

7、sey数R(p,q)p,q34567893 691418232836418 25354149615684691155 4349588780143101216121316610216511129812749516978072055402161031232171382821870317358395656588Ramsey数的计算Ramsey数的计算是对人类智力的挑战！例如R(4,5)=25 (1993年计算机11年的计算量)Erds用如下比喻说明其困难程度：一伙外星人入侵地球，要求一年内求得R(5,5)，否则将灭绝人类！那么也许人类能集中所有计算机和专家来求出它以自保；但如果外星人问的是R(6,6

8、) ，那么人类将别无选择，只能拼死一战了。最精美的组合定理Rota：如果要求在组合学中仅举出一个精美的定理，那么大多数组合学家会提名Ramsey定理。1984年Wolf奖得主Erds1997年Fulkerson奖得主Kim1998年Fields奖得主Gowers1999年Wolf奖得主Lovasz2003年Steele奖得主Graham2005年Gdel奖得主Alon2006年Fields奖得主Tao 均对Ramsey理论有杰出贡献Ramsey理论的哲理意义完全的无序是不可能的(Complete disorder is impossible)。任一足够大的结构中必定包含一个给定大小的规则子结构

9、。无序无意的行为产生了有规律的后果，发人深思耐人寻味。古人在满天的星斗中发现野兽和众神群集于天空的图形，以为是造物主的杰作。但根据Ramsey 定理，只要随机分布的星星数目足够多，就可以描绘出各种图形的轮廓。1994年Statistical Science的一篇论文利用统计方法证明：圣经隐藏了许多讯息，而这些讯息是有意安排的，绝非文字排列偶然造成的。 1997 年Michael Drosnin的The Bible Code 通过计算机扫读圣经中的304805个字母，发现圣经密码当中传达的讯息除了拉宾被刺杀外，还包括美国肯尼迪和林肯两位总统，以及印度总理甘地遇刺的事件，日本神户、美国旧金山的大地

10、震、世界末日与广岛原子弹轰炸等，种种过去与未来发生的大事件。组合数学的内容组合数学的研究内容组合数学研究的中心问题是按照一定的规划来安排一些与物件有关的问题。1.存在问题当符合要求的安排并非显然存在或不存在时，首要的问题是证明或否定它的存在. 2.计算问题或分类问题当符合要求的安排显然存在，或者已证明它存在时，求出这类安排的各抒己见，或者把它分类. 3.构造问题（组合设计）把满足某种条件的安排构造出来. 4.优化问题给出最优标准，找出满足给定条件的最优安排.组合数学的分支组合分析代数组合极值集论图 论组合设计组合优化组合算法组合数学的应用组合数学的应用应用促进理论发展36个军官问题这个纯粹来自

11、智力游戏的题目孕育着艰深的数学问题 。Euler猜想直到二十世纪中叶才获得解决，有两个原因：一是理论上的准备。这类问题用初等方法很难解决，二十世纪代数和几何的发展为解决问题提供了必要工具（如Galois域上的射影几何即有限几何等）；二是生产实际的推动。数理统计学家Fisher将正交拉丁方用于试验设计，例如，用二种原料合成某染料，每种原料有3个水平，怎样安排试验能使每种原料的各种水平各碰一次？这正好是3阶的正交拉丁方阵问题。 Fisher的试验设计是一股巨大的推动力量，把一种数学游戏变成了节约人力物力的具有重大价值的科学方法。源出于游戏受惠于数学落脚于应用源出于游戏受惠于数学落脚于应用“Kirk

12、man女生问题”引出组合数学的一个重要分支组合设计。对这些数学游戏，一旦当人们认识到它们在数学和其他科学上的深刻含义后，便又促使人们对它进行更深入的研究，从而丰富了数学学科的内容和知识。该问题就是最典型的组合设计问题。其本质就是如何将一个集合中的元素组合成一定的子集系以满足一定的要求。表面上看来，Kirkman女生问题是纯粹的数学游戏，然而它的解却在医药试验设计上有很广泛的运用。德国组合数学家利用组合设计的方法研究药物结构，为制药公司节省了大量的费用。在美国也有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。中国的组合数学河图洛书九宫图易曰：河出图，洛出书，圣人则之。河图洛书

13、是最早的幻方。“二、九、四；七、五、三；六、一、八” -大戴礼记明堂 黄帝内经灵枢的九宫八风篇。 “九宫者，即二四为肩，六八为足，左三右七，戴九履一，五居中央 ” -(汉)徐岳撰 (北周)甄鸾注 杨辉续古摘奇算法(1275)进一步给出了四阶幻方构造方法。此外，他还构造出了五阶、六阶、七阶、八阶、九阶和十阶幻方(百子图 )。四 九 二三 五 七八 一 六幻方的转播12世纪的阿拉伯文献里有六阶幻方的记载印度12-13世纪时的Jaina幻方（右下）15世纪幻方传往欧洲西方最早的幻方出现在德国Drer 1514年的名画”忧郁者”中。1977年美国旅行者1号和2号宇宙飞船带去Jaina幻方。杨辉三角杨辉

14、（南宋）著详解九章算法(1261年)中曾引贾宪（北宋）的“开方作法本源”图。杨辉在承上启下、数学教育方面有突出贡献。 Pascal三角(1654年)可上溯至1537年朱世杰恒等式（元）朱世杰是中国传统数学中水平最高者之一。 他在四元玉鉴（1303）得到：Zeilberger: Chus 1303 Identity Implies Bombieris 1990 Norm-Inequality,1994.1121 nmnnmnnnnnnn李善兰恒等式（清）李善兰（1811-1882）是开展现代数学研究的第一位中国数学家。他从研究中国传统的垛积问题入手，获得了一些相当于现代组合数学中的成果。如在垛积

15、比类中提出 .0 llnkknlkjlknjljkjErds-Ko-Rado定理Frankl-Graham：Erds-柯召-Rado定理是组合数学中的一个主要结果，开辟了极值集合论迅速发展的道路。柯召(1910-2002)：1935-1938在英国Manchester大学期间与Erds相识，该结果在1938年得到，于1961年发表。Erds（1913-1996）是数学史上著作数仅次于Euler的传奇人物（约1500篇），他曾说在他所有著作中，含有上述结果的论文是被同行们引用次数最多的。Gould-Hsu反演公式1973年Duke Math. J.上发表了Gould与徐利治的论文“Some ne

16、w inverse series relations”，这是中美关系正常化开始后两国学者合作发表的第一篇论文。Gould-Hsu反演公式可用于证明和发现恒等式，也可以应用于算法分析和插值方法中。中国邮递员问题管梅谷（1960）： 邮递员从邮局出发送信，要求对辖区内每条街都至少通过一次再回邮局，怎样选择一条最短路线? 现实生活中很多问题可以转化为中国邮递员问题。有好算法！论不相交斯坦纳三元系大集陆家羲(19351983)，包头九中物理教师1961年完成论文“冠克满系列和斯坦纳系列的制作方法” ，三次投稿国内杂志未中。前者1971年为国外学者解决发表，惜哉！1983年和1984年在J. Combin. Theory Ser. A 上发表题为 “On large sets of disjoint Steiner triple systems ”的六篇论文。以“论不相交斯坦纳三元系大集”系列论文获1987年国家自然科学一等奖。 Gilbert-Pollak猜想1990年，堵丁柱和黄光明合作证明了 Gilbert-Pollak猜想(1968)。被列为1989年-1990年度美国离散数学界和