运筹学——组合数学

组合问题的出现可以说同数学一样古老。近代许多数学家及业余爱好者都提出过、研究过一些问题，但是至今还很难说组合数学有什么统一的理论及方法，虽然比起过去，它的问题比较系统及集中了。过去组合问题（包括图论问题）散在数论、代数、拓扑、几何、分析、概率、统计乃至趣味数学之中，现在已公认为一门科学。不过它究竟在何时建立，仍然是有争议的。

最古老的组合问题是二项系数C_n^k的性质，到17世纪已知它与组合问题有关。1634年埃瑞冈已知道

这公式首先出现在帕斯卡的著作《论算术三角形》（1665年出版）中，随着概率论的出现，二项系数出现在概率公式中，帕斯卡发现了第一个计算概率的递归公式。1666年莱布尼茨首先引进组合术（arte combinatoria）一词并进行系统研究，1730年德·莫伏瓦首先引进生成函数或母函数方法，这方法通过欧拉等人的工作形成强有力组合方法，至今仍在广泛运用。欧拉等人引进组合方法和一系列著名的“数”，如伯努利数、欧拉数、斯特灵数等在数学及物理—系列问题中有重要应用。1798年勒让德首先提出包括—排除方法，1867年约当把它推广成一个普遍原理，它可以用来解决一系列组合及数论问题，特别是1891年鲁卡所提出的n对夫妻围圆桌而坐的问题。

18到19世纪一系列组合问题到20世纪才正式形成一门学科。1901年德国数学家内托出版第一本组合学教科书《组合学教程》，英国数学家麦克马洪两大卷《组合分析》于1915～1916年出版。

当前组合数学的几个主要领域大都是由18或19世纪一些特殊问题演化而来的。

（1） 古典组合问题。组合学中最基本的问题是排列组合问题。这些问题在概率论、统计数学及统计物理等领域有许多应用。其中二项系数起着关键的作用。推导这些公式的方法是生成函数方法，即把C_n^k 与（1＋x）n＝∑C_n^kx^k 联系起来。用这种方法可得出伯努利多项式。20世纪20年代，贝尔引进贝尔数及贝尔多项式，对有限集合的分拆数有重要作用。

组合计数理论最重要的成就之一是波伊亚计数定理。这定理最早的特例是凯雷列举烷烃的同分异构体的数目定理。波伊亚在1937年发表论文，把一切有限集合在置换群作用下的等价类数目用明显公式表出，其简单情形已由伯恩赛德得出。波伊亚给出等价函数类的计数定理，它在许多领域有重要应用。波伊亚定理中主要思想已发表在10年前瑞德菲尔德的一篇论文中。波伊亚定理还有各种推广。1964年荷兰数学家德布卢因把这定理推广到包含两个置换群的清形。它用于列举不同构的抽象自动机的数目。另一项重要成就是数论中莫比乌斯函数及反演公式的推广。维斯纳在1935年，浩尔在1936年各自独立发现反演公式的推广，它包含排斥原理、斯特灵反演公式等许多组合定理作为特例。1964年美国数学家罗塔系统地研究莫比乌斯函数，提出一般的影演算 （umbral calculus），为组合数学奠定一个可用的基础。其后，美国数学家斯坦利等人把组合数学与代数拓扑、交换代数结合起来，得出一系列深刻定理。例如1974年证明组合几何学的上界猜想。

（2）组合设计理论。区组设计，即t—（b，v，r，k，λ）设计，是指如下的组合设计：

设S＝｛x₁，x₂，…，x_v｝心 是有限集，｛S_i｝是S的一个子集系，S称为区组，|S_i|＝k，l≤i≤b满足b个子集可以分成r组，且S的每一个t元子集都恰为λ个S_i的子集，其中包含许多特例，如：

平衡不完全区组设计（BIBD） t＝2；

对称完全区组设计 t＝2，b＝v；

史坦纳三元系 t＝2，k＝3，λ＝1；

一般史坦纳系 λ＝1；

有限射影平面t＝2，v＝ n²＋n＋1，k＝n＋1，λ＝1，n称为平面的阶。

组合设计理论讨论哪种t—（b，v，r，k，λ）设计存在；如存在，有多少种？在应用中总是希望具体构造出来。在计算机的帮助下，已经有了相当的进步，但结果仍是零散的。另一方面，组合设计与统计正交表，正交拉丁方，阿达马矩阵，循环差集等有密切关系。另外上述区组设计也有一系列推广，并有广泛的实用价值，如编码理论。特殊的组合设计问题首先来自英国数学家柯克曼在1847年提出的柯克曼15女生问题：15个女生每天散步，排成5排，每排3人，问应该如何排队使得每一星期中每一对女生恰巧只有一天排在一排中？这是一个2—（15，35，7，3，1）设计。柯克曼给出一组解，其后进步不大。20世纪30年代开始的巨大进展有三个源泉：

①有限几何学；

②抽象代数，如有限置换群论；

③统计的实验设计。

对于t≥3，至今仍所知甚少，t＞5只知道较为简单的情形。对于t＝4及t＝5，1938年德国数学家维特给出t—（v，k，λ）的史坦纳系。4—（11，5，1），5—（12，6，1），4—（23，7，1）及5—（24，8，1）。1976年丁尼斯通又给出两个新设计5—（28，7，1），5—（48，6，1）。另外的5—设计λ≠1，与编码理论有关。对于t＝3，已知无穷多组合设计，例如莫比乌斯平面3—（q²＋1，q＋1，1），其中q为素数幂。

对t＝2的情形已有系统的研究，特别是BIBD以及特殊情形有限射影平面及其有关的拉丁方问题。1938年，印度数学家玻色首先引进BIBD，并得出BIBD存在的必要条件：vr＝bk，λ（v－1）＝r（k－1），以及费舍尔不等式b≥r。1961年汉纳尼证明，对于k＝3，4，上述条件也是充分的，但k≥5条件并不充分。对于对称的BIBD，即v＝b，r＝k时，存在2—（v，k，λ）的必要条件在1949年由周拉及赖瑟给出：

①若v为偶数，则k—λ是一平方数；

②若v为奇数，则不定方程

有不全为零的整数解。

有限射影几何是美国数学家凡勃仑在1904年提出的，其后几年他和同事构造出小阶射影平面，由瑞瑟定理，如果 n≡1，2（mod4），n阶有限射影平面存在的必要条件是n＝x²＋y²，由此可知6阶射影平面不存在。但是10阶射影平面的存在问题，长期令组合学家困扰。经过几年的计算机搜索，1989年终于证明10阶射影平面不存在。

有限射影平面的重要性在于它与拉丁方密切相关。正交拉丁方问题来源于欧拉的36军官问题。它是问，有36位来自6个军团具有6种军衔的军官，能否使他们排成6行6列的方阵，使每行和每列都包含各军衔的军官和各军团的军官？他猜想这个问题无解，并进一步推断n＝4a＋2（a是正整数）也无解。n＝2时显然无解，n＝6时无解由塔里在1900年证明。由于拉丁方对于实验设计密切相关，因此拉丁方的构造至关重要，而且玻色证明当n≥3，如果有t个互相正交n阶拉丁方，则t＜n－l，而且n－l个互相正交n阶拉丁方，存在的充分必要条件是n阶射影平面存在，这就解释了为什么6阶射影平面不存在，下面的问题是对10阶以及4a＋2阶正交拉丁方欧拉猜想是否成立？结果大大出人意料，玻色等人在1959年构造一对10阶正交拉丁方。1960年帕克构造一对10阶拉丁方，接着他们又证明所有4a＋2阶正交拉丁方都存在。对于其他阶的正交拉丁方不断有新结果。1991年，有人构造4个互相正交的28阶与52阶拉丁方。

作者：李佩珊 许良英 主编