组合学建立于17世纪60年代，但组合思想却有悠久的历史，因为组合学中的诸多问题与一些奇异的古老问题相联系。1979年，组合学家Biggs N. L.发表文[1]，讨论了组合学的渊源，他引用大量事例来说明这一问题。但是，他对东方古老的组合事例未予足够重视，下面给出进一步讨论。
|
4 9 2 3 5 7 8 1 6
图1
洛书 Fig.1 3-magic
square |
1
幻
方
幻方是一种组态设计。中国先秦的
“洛书”，即纵横图，是世界上最古老的三阶幻方。中国春秋战国时代已经有了三阶纵横图，到西汉则有较多的应用，成为一种普遍的知识，中国是幻方的发源地。
所谓n阶幻方，是指在一个n×n方阵中数字1，2，3 … … n2 的某种配置，使得其中每行、每列及两条对角线上的和均为n(n2+1)/2，即幻方常数，三阶幻方洛书的常数为15。所以，组态洛书满足特定条件，即把一组对象集映入到具有已定结构的抽象有限集中。因此，法国数学家贝尔热（Belral C.）曾说：“懂得构造这种组态的困难，就不能说在中国古代不曾有过组合学”[2]。河图也是一种组态设计。河图、洛书（图1）表明了古代中国人对满足这些特定条件的配置的最早尝试。
大约在8世纪，中国的幻方记述传入阿拉伯地区，该地区的人们对幻方产生了极大兴趣，并做出了重要贡献。塔比伊本•库拉（Thabitibn Qurra）较早研究了幻方。在一批阿拉伯学者约990年编辑的一本百科全书中可找到 3，4，5，6阶幻方，并说明7，8，9阶幻方的存在。此后，又有三部幻方著作发展了从已知阶的幻方构造新幻方的规则，它们是：①阿尔布尼（al-Buni）的《（幻术）道具之书》，其中有构造幻方的一些规则，甚至用一种简单的边缘技术使维数增加；②阿尔卢布迪（al-Lubudi）献给曼苏尔(al-Mansur)的《幻方论》；③莫斯霍普洛斯（Moscho-poulos）在约写于1315年的手稿中给出了改造奇数阶和可被4整除的阶数的幻方的一般方法。幻方在1315年前后传入西方后，最初被赋予一种神秘性或作为护身符，成为神秘哲学的一部分，或是在一些场合中作为有趣的数学游戏，但并未引起人们的深思和研究。
在中国，宋朝杨辉的《续古摘奇算法》（1275）辑录了更高阶的幻方（至10阶），他最早从数学角度研究了洛书的构造法以及其他6种变形幻方，它们同样具有某些组合性质，杨辉还构造出由9个洛书构成的大幻方。
|
7 12 2 13 |
1 14 8 11 |
|
19 9
25 15 |
15 9 25 19 |
|
16 3 9 6 |
10 5 15 4 |
19 25 9 15 |
15 25 9 19 | |
|
图 2
变形幻方 Fig. 2 Transformative square | ||||
杨辉之后，丁易东、程大位、王文素，清朝方中通、张潮、保其寿对幻方及变形幻方有深入的研究，形式也趋于多样和复杂。另外，在印度古城Khaj-uraho的一个不晚于12世纪的Jaina碑文中出现过一个4×4阶幻方，
它包含一些复杂的组合性质：将其1/4纵横求和后相对应放置，得到它的一个变形（图2）。直到中世纪后，欧洲的一些数学著作中才开
始出现讨论幻方及其改造的内容，如卡尔丹诺（G. Cardano, 1501—1576）给出了分别以日、月和五星为名的幻方及构造法[3]，17世纪，日本对幻方也产生很浓的兴趣，主要是关孝和对幻方和幻圆理论的研究。
总之，幻方最早源于中国洛书，阿拉伯、印度和中国对幻方的发展做出了重大贡献；而西方的研究起步较晚。幻方是智慧的结晶，它提供了现代组合学研究中区组设计的古老范例。
2 排列组合
排列组合的思想随着人类计数的需要而产生，编撰于西周后期的《易经》含有最早的排列，它是根据阳爻（—）和阴爻（- -）两种符号而建立的体系，演绎成3线的八卦图和6线的64卦，即从2元多重集中取3个的有重排列23以及从8元多重集中取2个的有重排列(23)2=64。
中国传统的“干支历”在商代已普遍使用，干支计数与五行循环理论包含着丰富的排列思想。把10个“天干”与12个“地支”有序排列为“甲子，乙丑，…，甲戌，乙亥，…，壬戌，癸亥”，周而复始，成一循环，即是从两个有序集中有序选取元素，依次以奇数对奇数，偶数对偶数的约束条件构成一组，如甲子为1—1，乙丑为2—2，它实际上给出一种设计。五行循环说在学术界一般作为哲学理论探讨，若予以数学的分析，木、火、土、金、水正向邻位相生，正向隔一位相克，生克各自循环，在此约束条件下，它所含元素量最少，是惟一的体系 [4]，这样组态元素最小量为5。
中国古代有许多不同的占筮方法，其实质都是以事物的不同排列来对应卜辞，又将律吕相生图、五行、日月干支、二十八宿、五色、五音等等相配合，产生出各种组合来，这些尚需更进一步研究。
印度、阿拉伯在古代也有许多对物体排列组合研究的事例，并且有较深入的认识。公元前300年左右，印度耆那教的文献已提到排列组合问题，他们已经知道了3个排列数和3个组合数（Pn1, Pn2,
Pn3
和Cn1, Cn2, Cn3）。印度教中的哈利神（Hari）4只手中拿着狼牙棒、铁饼、莲和贝壳，4样的排列不同，哈利神就有不同的名字，共有4！种。
约公元前6世纪的苏斯鲁塔（Susruta）的医学论文中给出了从六种不同的味道物品中分别取1，2，3，4，5，6种的组合方法分别为6，15，20，15，6，1，通过枚举得出所有可能的结果为63[5]。排列组合的方法在印度当时似乎已成为一种普通的知识，对于寻求排列组合的一般性规则，似乎在很长一段时间内才逐步形成。约公元850年数学家马哈维拉（Mahavira）给出了n个物体中每次取r个的取法数的一般完整组合公式，即今所谓n元集中所能构成的r元子集数。1150年巴什迦罗（Bhaskara Ⅱ）又给出了Cn r = Cnn-r
，这是构成算术三角形的基本规则。
印度数学家巴什迦罗的《立刺瓦提》一书中有一个著名的排列问题：湿婆神（Siva）的十只手中拿十件东西，绳、钩、蛇、鼓、头盖骨、三叉戟、床架、匕首、弓、箭，若十只手交换拿这十样东西，共有多少种不同方式？答案是有3 628 800种，即10！。他首次给出了这一定理，r个物体中，分别有k、l、…个物体相同，则r个物体的排列数为r!/k!l!…。
随着伊斯兰征服了印度的一部分，印度的数学成就开始通过阿拉伯学者向西方渗透，阿拉伯人似乎已获得了简单的组合原则并予以应用。哈雷特（al-Halit）在著作中考虑了文字在音节构成上可能的排列，体现出求排列数和组合数的基本方法。
古代西方对组合学也有相关研究。古希腊阿基米德“计算太阳神的牛数”一题，是古代西方旁及组态构作的罕见一例：当白公牛与黑公牛数目相混时，它们纹丝不动地排成一个正方形，牛群把向四周延伸的Thrinacia平原充满。此外，当黄公牛与花公牛合成一群时，它们是这样排列的：数目由1开始，慢慢加多，直到排成一个三角形，其中既没有别色的牛也没有空缺。
这一问题涉及到两个机遇性组态，其一为白、黑公牛排成的正方形，另一个为黄、花公牛排成的正三角形。该问题侧重于数论，与算术有关，但它是古代西方的相关于组合学组态的奇例。
西方由于研究形数而产生排列组合数，波菲利（Porphyry）把三角形数与“从n个不同物体中选取2个”相结合，从n个不同物体中选取2个的方法数等于第n–1个三角形数，帕普斯（Pappus）考虑了另一种形式：n条不同的直线，既没有两条平行，也没有三条交于一点，且每任意两条直线有一个交点，那么共有多少个点？
答案即为三角形数n(n－1)/2，博伊修斯（Boethius）讨论了波菲利的结论并予以推广，若考虑物体的顺序，则从n个不同物体中选取2个的方法数为n(n–1)/2，此即n个物体中任取2个的排列数。直到1321年，犹太人本•哲生（Levi ben Gerson）给出了印度已知的3个主要规则：n！为n个物体的排列数n(n–1)…3·2·1；n(n–1)…(n–r+1)为n个物体中取r个的排列数；Cnr=n(n－1)…(n－r+1)/r!为n个物体中取r个组合数。
3
棋术与游戏
历史上有许多棋艺和游戏不仅具有浓郁的趣味性，而且蕴涵着深奥的数学知识，有些亦成为组合学研究的素材，它们既丰富了组合学的内容也促进了组合学的产生。
宋沈括在《梦溪笔谈》卷18中讨论了围棋的所有可能摆出的“棋局都数”，由此可联想到古代印度棋盘上放麦粒的故事，导致用等比数列求和。棋盘上能产生许多与组合计数相关的问题。沈括根据与现今相同的19路361点的围棋盘，举出了从2路4个棋子到6路36个棋子的例子，分别得到34，39，……336，应用3种算法：①先考虑每个格点有黑、白、空3种可能，故361个点位落子的方法数共为3361，即3元素中取361次的可重排列；②先算出最边一路的3种落子19次重复排列数a=319为基数，再随行数的增加使a累乘19次；③依次计算a=319，a2，a4，a6，a12，a18，a19，此法与②相同，但减少了计算次数。这些是11世纪惊人的结果。
在现代组合学中，棋阵问题已成为一个研究专题，如棋盘的覆盖、布局、格点、格径等。“棋局都数”是这类组合问题一个较早的特例。作为数学游戏，随着组合论、对策论的逐渐发展，棋盘上的问题不断得到开发和利用。
Nim游戏，中国称之为“抓三堆”或“拧法”，国外称之为“Chinese game of Nim”，“simple game of Nim”等，Nim是为现代数学研究提供模型的一个古老的游戏，它源于几千年前的东方，其规则为：有k堆物体，两人从中轮流拿取，每次只能在其中一堆中拿取，至少取一个，至多取一堆，谁最后取完谁胜或谁负。Nim游戏包含深刻的组合学道理，对k=3的情况，所建立的Nim三元系与柯克曼三元系有一定联系，柯克曼的方案恰好是Nim中每堆石子数目都不大于15时的制胜方案[6]。
镶符（也称移棋或移珠）问题，是中国古代组合游戏：沿一直线自左至右黑白相间地排列着黑白棋子各n个，在右端留有m个空格，现按“镶变”规则对棋列进行变换：①每一步将依次相邻的m个棋子移入空格，留下m个新空格，被移棋子的相对位置移后不变；②被移动的m个棋子不得与将要移动的空格相邻，即这m个棋子必须是“隔子跳入”（或“镶入”）空格的。问：能否按上述规则经若干次镶变将黑白相间的棋列变易成黑白分别的棋列（且空格仍留在棋列的某一端）？若能，最少变易次数是多少？
镶符问题实际是一个在某种特定的组合规则下，将一种序列重新组合为另一种序列。现代在密码学、计算机问题中有很多与它相同或相似的数学模型[7]。
还有许多其他的古老游戏或竞赛题，如“约瑟夫问题（Josephus problem）”、哈内塔（towers of Hanot）问题，狼、羊、白菜过河问题等，其解法成为组合学或其他分支研究的数学方法，丰富了数学学科的内容。
综上得出的结论是：组合学源于东方文明。中国传统数学不像西方很注重数学的逻辑，而是擅长离散性思维，这些必然引发对数学方法的验证和研究，颇有启发性，古印度多考虑多个物体的组合而产生的组合对象和概念，西方数学在欧几里得逻辑数学思想的支配及其对这种逻辑的崇拜，往往对游戏、竞赛等问题不甚求解，而组合学的起源与这些奇妙的问题有一定联系。这也正是组合学起源于东方的数学背景。