组合数学

[拼音]：zuhe shuxue

[外文]：combinatorial mathematics

又称组合学，是数学的一个分支。它是研究“安排”的一门学科。当把已给的有限个或可数无限个物体按一定规则来安排时，自然会产生以下四个问题：

（1）符合要求的安排是否存在？②这些安排有多少种？③怎样作出这些安排？④当有衡量这些安排优劣的标准时，怎样求出最优安排？这四个问题依次称之为存在性问题、计数问题、构造问题和优化问题。

据传，早在公元前2200年左右，大禹治水时就发现一个“神龟”，背上有花纹，如

所示。用阿拉伯数字写出是一个由1～9的九个数组成的方形阵列，具有三行三列，其中每行、每列以及每条对角线上的三个数之和都等于15。这表明早在中国古代就能构造出这种组合结构。宋代杨辉造出过表明二项式系数间的基本而重要的关系，即的杨辉三角形。朱世杰得出了组合恒等式 1≤p≤6。清代李善兰则证明此恒等式对一切正整数 p成立。德国数学家和哲学家G.W.莱布尼茨于1666年首次在近代数学的意义下使用“组合”一词，这是在他的著作《论组合的艺术》中出现的。

自17世纪至20世纪30年代，组合数学受到娱乐、数论、概率论和化学等的推动而迅速发展，得到了一般的存在性定理和计数原理，诸如抽屉原理及其推广──拉姆齐定理、母函数、递归关系的解法、容斥原理、波利亚计数定理等，还解决了一系列著名的组合学课题，诸如更列问题、家政问题、36军官问题等。

自20世纪以来，许多理论学科和应用学科，诸如物理学、化学、信息论、计算机科学、运筹学、管理科学、概率统计、编码理论等，向组合数学提出了大量的具有理论和实际意义的课题，促使它产生许多新理论，如区组设计、组合优化、组合算法等，解决了一系列理论上的以及与经济发展密切相关的课题。

建立组合模型的实例

用组合学方法去解决实际问题，首先是建立适当的组合模型。

设有n位人员 A₁，A₂，…，A_n和n项工作 B₁，B₂，…，B_n。若欲合理分派这 n位人员以工作，而一项工作最多由一人承担，且一人最多承担一项工作。何谓“合理”，则视具体情况而定。

（1）设人员A_i（1≤i≤n）有能力承担的工作是若能使尽可能多的人员分派到他们能承担的工作，则认为是合理的，且称为妥善分派。

（2）设人员A_i担任工作B_j的效益（例如经济效益）为α_ij(1≤i，j≤n)，则能使全部效益的总和达到最大的分派被认为是合理的，且称为最佳分派。

（3）若人员 A_i(1≤i≤n)对诸工作的选择次序为则说人员A_i对工作B的评级为k。注意，评级的数值愈小的工作，被选择的次序愈前。工作 B_j(1≤j≤n)对诸人员的选择次序为，则说工作B_j对人员A的评级为k。对诸人员的一个工作分派叫做不稳定的，如果根据这一分派有二位人员A_p、A_q分别承担工作B_t、B_u，但是人员A_q对B_t的评级小于对B_u的评级，且工作B_t对人员A_q的评级小于对A_p的评级。一个不稳定的分派，不能认为是合理的；不是不稳定的分派才认为是合理的，叫做稳定分派。

（4）如果一个分派使得每位人员承担的工作的评级，都不大于任一稳定分派中该人员承担的工作评级，那么这样的分派称为对人员的最优分派。类似的有对工作的最优分派。最优分派被认为是合理的。对应于上述的①、②、③、④情形，有以下四类组合模型：

Ⅰ型分派模型　作n 阶矩阵A＝（α_ij），这里α_ij＝1，当A_i 能胜任工作B_j时；α_ij＝0，对于其他情形。于是一个合理分派对应于矩阵 A的、积和式不为零的一个最大阶子方阵。一个n阶矩阵B＝(b)_ij)的积和式定义为这里和式遍及｛1，2，…，n｝的全部排列。全部妥善分派的个数，就是A的、积和式非零且阶数最大的子方阵的积和式之和。

Ⅱ型分派模型　 作 n 阶矩阵 C ＝（с_ij），с_ij是一个实数，表征人员A_i工作 B_j的效益。最佳分派是使当过{1，2，…，n}的一切排列达最大值的排列所对应的分派：人员A_i承担工作。

Ⅲ型分派模型　作n阶评级矩阵 其中e_ij是人员A_i对工作B_j的评级，ƒ_ij是工作B_j对人员A_i的评级。于是，一个分派是稳定分派的充要条件是，假定按此分派人员A_i承担工作，那么，绝不存在一对整数i、j(1≤i≠j≤n)合于和

Ⅳ型分派模型　称工作B_j对人员A_i是可行的，如果存在一个稳定分派，按此分派人员A_i承担工作B_j。最优分派是具有下述性质的分派：按此分派每一人员承担的工作的评级都不大于该人员的诸可行工作的评级。

存在性定理

有关存在性的一个重要结果是抽屉原理及其推广──拉姆齐定理：设S是一个N元集，T_r(S)是S的全部r元子集所组成的集，而，是T_r(S)的任一分解且p、q≥r≥1，那么存在最小正整数n(p，q，r)，只与p，q，r有关，与S及分解法T_r(S)=α∪β无关。具有以下性质:当N≥n(p，q，r)时或有S的p元子集S₁合，或有S 的 q元子集 S₂合。应用该定理及其略为普遍的变形可得：

（1）对已给正整数p₁，p₂，…，p_t≥2，存在最小正整数 n(p₁，p₂，…，p_t，2)使得时，任一t色完全图K_n都有单色完全子图K_pj，这里i为1与m之间某一整数；

（2）对任给的正整数m≥3，存在正整数n=n(m)， 使得在平面上无三点共线的n个点中，有m个点为凸m边形的顶点。

一些不存在定理与区组设计有关。区组设计的理论源于农业试验和其他科学试验。设，是S的一个子集系，S_i叫做区组。如果｜S_i｜=k，1≤i≤b;S的每一个二元子集都恰为λ个S_i的子集；S的每一元 x_i都恰在 r个区组里，则称 是一个(b，v，r，k，λ)平衡不完全区组设计，简称为(b，v，r，k，λ)设计。合于条件v＝b)，r＝k的(v，b，r，k，λ)设计，又叫做(v，k，λ)对称设计，简称为（v，k，λ）设计。易知，存在(b，v，r，k，λ)设计的必要条件有r(k-1)=λ(v-1)，bk=vr；存在(v，k，λ)设计的必要条件有:若2|v，则k-λ是个平方数，如果2凲v，那么不定方程

有不完全为零的整数解。如果这些条件不满足，那么具有相应参数的设计不存在。

组合计数理论

最简单的计数原则有三个。

（1）积则：若某物θ₁有m种方法选出，用其中任一方法选出θ₁后都有n种方法选出另一物θ₂，则依次选出物θ₁、θ₂的方法数是m·n。

（2）和则：把一些东西分成若干类，任二类都没有公共元，那么全部东西的个数等于各类东西的个数之和。

（3）补则：一堆东西中满足某性质的东西的件数等于这堆东西的总数减去不满足该性质的东西的件数。

利用这些简单的原则可得：

（1）n个不同物件的 r无重排列数是(n)_r＝n(n－1)…(n－r＋1)；

（2）n个不同的物件的r可重排列数是 n_r；

（3）n个不同物件的 r无重组合数是；

（4）n个不同物件的r可重组合数是。

母函数

由数列u₀，u₁，u₂，…产生的形式幂级数u₀＋u₁x＋u₂x²+…叫做该数列的母函数。若定义1， 则数列的母函数是 (1+x)ⁿ，代x=1，得；代x=-1，得。由此两式可得 。还可推得一系列恒等式，如

；

，

等等。母函数是解决许多组合问题诸如分配、分拆、限位排列等的有力工具。

递归关系

若一个数列u₀，u₁，u₂，…自某项后的任一项均能由它前面的诸项按某一关系式来确定，则该关系式叫做递归关系。最简单的是常系数线性递归关系： 这里诸 α_i是常数。不失一般性，可设α_r≠0，且称这种线性递归关系是 r阶的， 称 为该线性递归关系的特征多项式。在复数域上分解 。以g(x)表数列u₀，u₁，u₂，…的母函数，而=，这里，诸с_i(0≤i≤r-1)只依赖于u₀，u₁，…，u_r-1。展 g(x)为部分分式 ，于是可以解得。由此立得满足线性递归关系 ，和初始值 u₀=u₁=1的斐波那契数

。

下面是非线性关系例子。设已给n个字母α₁，α₂，…，α_n，依此次序把每一α_i（n≥i≥2）放在 α_j-1的右上角，并且在它们之间加括号以形成完全确定的方幂。记这样得到的全部方幂的个数为 。当 n＝3时这样的方幂只有 和，故u₃＝2。易知，因而 u_n为 的泰勒展式中xⁿ的系数，即。

容斥原理

已给元素的集 A和性质的集p。把满足p中k个性质的A中元的个数记为

，

把一切可能的之和记为N_k。那么，恰满足p中r个性质的A中元的个数。这就是容斥原理。在许多情形，N(r)很难直接计算，而N_k则较易直接计算。用此原理可解决更列问题:前n个自然数的无重排列中每一数皆不在其本位上，这样的排列的个数是。著名的家政问题：n对夫妻，围坐圆桌，男女相隔，夫妻不邻，问坐法若干？由容斥原理得坐法数为

。

(0，1)矩阵

这类矩阵是研究很多组合问题的重要工具。设S是一个m 元集，是它的一个子集系。若有元素组合于x_i∈S_i，x_i≠x_j(1≤i≠j≤n)，则称该元素组为子集系｛S_i｝的一个相异代表组。全体相异代表组的个数记为N(S₁，S₂，…，S_n)。当α_j∈S_i时，令α_ij=1；在其他情形，令α_ij＝0；则称矩阵A＝{α_ij}为集S同其子集系｛S_i｝之间的关联矩阵。对任一n×m矩阵B＝(b)_ij)，所有无二在同行或同列的k个元之积之和，称为B的k积和式 ，记为per_kB。易知。虽有公式计算per_kB，但不理想，人们仍在寻求更为满意的结果。

波伊亚定理

这一定理提供一个公式来计算某些元素在置换群下的等价类的个数。设 D和 R是两个有限集，记为从D到R内的全体映射所组成的集。设G是D上的一个置换群。若对ƒ₁，ƒ₂∈存在g∈G使得ƒ₁(gd)=ƒ₂(d)对一切d ∈D 成立，则说ƒ₁与ƒ₂等价， 记为ƒ₁～ƒ₂或ƒ₁g＝ƒ₂。“～”是一个等价关系，据此可把分为若干个等价类之并。诸等价类所组成的集记为F。记 n次对称群中全体置换所组成的集为。波伊亚定理断言｜F｜=p_G(｜R｜，｜R｜，…)，这里　 是G 的轮换示式。设C是一个立方体，G┡是C 的群亦即使C 变为其自身的旋转的全体所成的群。记群 G┡中的旋转所产生的C的六个面之间的置换所成的群为G，则有。C 的六个面所组成的集记为D。令R＝{红，蓝}，那么就是把C 的各面着以红色或蓝色的所有可能的着色法的全体。对C 的诸面的两种着色法叫做本质上不同的，如果经群G┡中的任一旋转，不能使旋转前后的立方体之间的一切对应面有相同的颜色。由波伊亚定理，本质上不同的着色法的个数是。具有i个红面，6-i个蓝面的等价类的个数n_i是 中yⁱ的系数。

构造问题

一些重要的存在性问题往往通过构造而获得解决。此外，在解决实际问题中，往往需要造出特定的组合构形。解决构造问题的主要方法如下：

递归法

通过具有小参数的某种构形来造出具有大参数的这种构形的方法叫做递归法。应用这一方法的最简单的例子是构造2ⁿ阶的H 矩阵。所谓 n阶H矩阵，是指以1，－1为元的n阶矩阵H，满足 HH^T＝nI_n，这里H^T表H 的转置，I_n表n 阶单位阵。易证 n₁阶H 矩阵H₁和n₂阶H 矩阵H₂的克罗内克乘积 H₁×H₂是一个n₁n₂阶H 矩阵。由此和是H 矩阵即可造出2ⁿ阶H 矩阵 。关于H 矩阵有一非常著名的猜想：存在任意4n阶H 矩阵，至今尚未获证。递归法在(b，v，r，k，λ)设计的研究中作用很大。(b，v，r，3，1)设计(又称v阶施泰纳三连系)理论中的大集问题就是要确定存在大集的v值。若把 S上两两无公共区组的v阶施泰纳三连系的个数的最大者记为D(v)，则当 v>1时，D(v)≤v-2。若D(v)=v-2，则把S上任意v-2个两两无公共区组的v阶施泰纳三连系所组成的簇叫做S上施泰纳三连系的大集。陆家羲证明了，对于使v阶施泰纳三连系存在的v(即v>1，v呏1或3(mod 6))，当v>7时，除6个可能的例外，都有D(v)=v-2，从而使大集问题得到解决。

数论法

构造某些类型的差集是说明数论法的最好例子之一。设是互不同余(mod v)的k个整数所组成的集。若每一整数α扝0（mod v）都恰有λ种方式表为D 中二元之差：，则称D是一个（v，k，λ）差集。设p＝4t-1是一个大于3的素数，d₁，d₂，…，d_2t-1为全部非零二次剩余(mod p)，则就是一个(4t-1，2t-1，t-1)差集。

代数法

可以应用有限域的知识来构造正交拉丁方。n元集 A＝{α₁，α₂，…，α_n}上的一个拉丁方是一个 n阶方阵，其中每行每列都是集A 的无重排列。两个 n阶拉丁方（α_ij）和 （b_ij）叫做正交的，如果n阵矩阵((α_ij，b_ij))中无二元相同。对任给的n，至多存在n－1个两两正交的n阶拉丁方。设p 是素数，m是正整数，n＝p^m，记有限域GF(p^m)的n个元为α₀=0，α₁=1，α₂，…，α_n-1，再记。于是可以构造出n-1个两两正交的拉丁方 。大于1的整数 n有标准分解式，记。于是可以构造出两两正交的v（n）个 n阶拉丁方。很长时期以来，直到二十多年前，v(n)一直被设想为两两正交的 n阶拉丁方的个数的最大可能值。由于v(4t＋2)=1，1782年欧拉猜想，当n=4t+2时，无一对n阶正交拉丁方存在。1900年这一猜想仅就t＝1的情形得证。1959年一对10阶拉丁方被构造出来。此后不久，又证明了对任意n=4t+2>6，都存在一对正交拉丁方。这就是说，欧拉猜想仅对n=6成立。n=6时的欧拉猜想就是人所共知的“36军官问题”:有36名军官来自6个不同的团，每个团6名且分属于不同的6种军阶；能否把他们排成一个方形阵列，使得每行每列的6名军官正好来自不同的团，且属于不同的军阶。

几何法

域F上的 n维射影几何pG（n，F）是全体向量的集合。一点p是全体向量（是一个固定的向量，b≠0）的集合，其维数为零。如果y₀，y₁，…，y_k是k+1个无关的向量，则称全体非零向量b)₀y₀+b₁y₁+…+b_ky_k(b_j∈F)是一个 k 维子空间。n－1维子空间又叫做超平面。构造区组设计的下述方法是1938年得到的。以q＝p^m（p是素数）个元的有限域F_q上的n维射影几何pG(n，F_q)的所有超平面作为区组，全体点作为元素组成一个

对称设计。

组合优化和组合算法

Ⅰ型分派可化为积和式问题。对Ⅱ型分派有下述定理:设C＝(C_ij)是一个n阶实矩阵，则　 ；且这个共同值当 时达到。由此可得最佳分派。对Ⅲ和Ⅳ型分派，下面的算法同时提供一个稳定分派和对人员的最优分派。第一步，每一人员选择他最喜爱的工作；第二步，至少被一位人员选中的工作从选择它的全体人员中挑出它最喜爱的人员，让他等待而拒绝其他；第三步，每一位被拒绝的人员在未拒绝他的工作中选择它最喜爱的工作;第四步，每一个被选中的工作从第三步选择它的人员和前一步等待它的人员的全体中挑选它最喜爱的人员，让他等待而拒绝其他。不断重复第三步和第四步直至没有被拒绝的人员存在为止。此时每一工作恰好有一人员等待。于是分配这一工作与该人员。例如当评级矩阵为

时，经上述各步依次得出（“√”表示选中，“×”表示拒绝）：最后一步表明，分派人员1承担工作2，人员2承担工作3，人员3承担工作1，人员4承担工作4，这一分派既是稳定的，又是对人员最优的。

参考书目

1. 柯召、魏万迪同著：《组合论》，上册，科学出版社，北京，1981。
2. 魏万迪著：《组合论-组合设计》，下册，科学出版社，北京，1987。
3. M.Jr.Hall，Combinatorial Theory，Blaisdell Pub. Co.，Waltham，Mass.，1967.
4. C. L. Liu， Introduction to Combinatorial Mathematics，McGraw-Hill，New York，1968.
5. H.J.赖瑟著，李乔译：《组合数学》，科学出版社，北京，1983。 (H.J.Ryser，Combinatoricl MatheMatias，John Wiley & Sons，New York，1963.)