围棋比赛中的组合数学

摘"要：本文首先介绍了第一届中日围棋擂台赛的比赛情况，其次讨论了表格与非降路径这两类经典组合结构在围棋比赛中的应用。通过构造两个等势集合之间的一一映射，建立相关集合之间的联系，刻画了组合物体的性质。这样将趣味性融入数学的教学过程，激发了学生的学习兴趣，提高了学生的数学素养。

关键词：组合数学；表格；非降路径；兴趣教学

一、概述

数学是自然科学的根本，华罗庚先生曾经说过：“宇宙之大，粒子之微，火箭之速，化工之巧，地球之变，生物之谜，日用之繁，无处不用数学。”［1］数学的应用非常广泛，上至对宇宙空间的探索，下到生活中的柴米油盐，都离不开数学的身影。但人们谈到数学却常常抱有抽象难懂且脱离实际的印象，这是一种误解。这一现象也对一线数学教师有所启发，我们在平时的课堂中需注重数学理论与现实生活的连接，选取实际生活中合适的片段穿插在数学课程的讲授当中。本文围绕一场传为佳话的围棋比赛，聚焦组合数学中两类经典的组合结构——表格与非降路径的知识应用，开展了富有趣味性的讨论。

二、围棋比赛与表格

首先，我们考虑一个古典概型问题。1984年举办的第一届中日围棋擂台赛的赛制为中日双方各自派出八名棋手，一对一地进行单败淘汰赛。第一局出场的日方棋手执白子赢得一盘，第二局出场的中方棋手扳回一城，随后又胜四盘。然而，第七局出场的日方棋手连胜六局，兵锋直指中方主将。面对如此局面，中方主将从容应对，三战三捷，为中国队赢得了首届中日围棋擂台赛的胜利。

其次，借由这样传奇的围棋比赛，我们引入一个组合学问题：假设甲乙两队起初各有8名队员，两队队员按序出场，每队各取一人对弈，进行类似中日围棋擂台赛这种一对一单败淘汰赛，总共可能出现的比赛结果有多少种？进一步说，若甲队第8名选手面临对方两人及以上的局面并且甲队获得最终的胜利有多少种可能？基于组合证明的思想，我们借助以红白两色着色的1行16列表格构造双射来解决上述问题。我们断言每一个包含8个红格的以红白两色着色的1行16列表格对应一种比赛结果，并用第i个红格代表甲队第i名棋手，而将第i个白格指代乙队第i名棋手。

在该表格中第i-1个红格与第i个红格之间的白格表示甲队第i名棋手所战胜的乙队棋手，若i=1则第1个红格左侧所有的白格即为甲队第1名棋手所战胜的乙队棋手。类似地，第i-1个白格与第i个白格之间的红格则表示第i名乙队棋手所击败的甲队棋手，若i=1则第1个白格左侧所有的红格即为乙队第1名棋手所战胜的甲队棋手。若甲乙两队比赛情况与第一届中日围棋擂台赛一致，不难看出，第一届中日围棋擂台赛的比赛结果可以用图1所显示的着色表格来表示。事实上，任意一种比赛结果都可以通过这样的表格来表示，因此我们建立了从比赛结果到这类着色表格之间的一一映射，从而解决了第一个问题，其答案应为168。对于第二个问题，甲队第8名选手面临对方两人及以上的局面并且甲队获得最后的胜利意味着在表格最右侧三格的着色分别为白色、白色、红色。再由剩余的13格中有6格着白色，故得出该问题的结果为136。

三、围棋比赛与非降路径

不同于着色表格，我们还可以运用二维平面坐标系中的非降路径来表示两队围棋擂台赛的一系列比赛情况。考虑坐标平面上具有整数坐标的两个点（x1，y1）和（x2，y2），其中x2≥x1且y2≥y1，则将从（x1，y1）到（x2，y2）由水平步（1，0）和垂直步（0，1）组成的一条格路定义为从（x1，y1）到（x2，y2）的一条非降路径。例如，在图2中，我们给出了一条从（0，0）到（5，6）的非降路径，它由5个水平步和6个垂直步构成。

那么从（0，0）到（5，6）的非降路径一共有多少条呢？考虑到在每一个整数坐标点处均存在水平向右移动一步或垂直向上移动一步这两种选择，因此当我们在从（0，0）到（5，6）的非降路径总体11步中确定好向右移动的水平步出现的位置，剩下的自然就是向上移动的垂直步。所以从（0，0）到（5，6）的非降路径共有5+65条。一般地，从（0，0）到整数坐标点（x，y）的非降路径的数目为x+yx，而从（x1，y1）到（x2，y2）的非降路径的数目则可表示为x2-x1+y2-y1x2-x1［2］。

运用组合证明的思想方法，结合非降路径这一组合结构，我们希望构建从（0，0）到（8，7）或（7，8）的非降路径与擂台赛比赛结果之间的一一映射，从而将一个实际问题转化为数学问题。我们定义与比赛结果相对应的非降路径从（0，0）出发，在每一局比赛中，若是中方获胜则格路向右移动一步，反之则格路向上移动一步。若中方取得最终的胜利，则规定该条非降路径走到（8，7），反之则规定该条非降路径走到（7，8）。这样我们就将每一种赛况对应于一条从（0，0）到（8，7）或（7，8）的非降路径，例如，首届中日围棋擂台赛的战况可以表示为图3所示的一条非降路径。

接下来，我们从非降路径的角度来回顾一下之前提出的两个问题。甲乙两队在类似中日围棋擂台赛这类一对一单败淘汰赛制下比赛，一共可能出现多少种比赛结果？若规定在每一局比赛中，甲队获胜则格路向右移动一步，反之则格路向上移动一步，那么这个问题就对应于从

（0，0）到（8，7）或（7，8）的非降路径的数目。由前面的讨论可知，从（0，0）到（8，7）或（7，8）的非降路径的数目均为158，所以在这种一对一单败淘汰赛制下一共可能出现2×158=168种比赛结果，与前文中运用表格方法计算的结果一致。对于第二问，甲队第8名选手面临对方两人及以上的局面并且甲队获得最终的胜利，这意味着该条非降路径最后是经两个水平步达到（8，7）的。因此，该条从（0，0）出发的非降路径一定经过（6，7），所以这样的非降路径一共有136条，分别对应了136种赛况。这样看来，前文中用表格组合解释的两个问题均可以用非降路径来理解，那么非降路径作为一种重要的组合结构，其自身特点还可以如何运用呢？下面我们来研究第三个问题：若在围棋擂台赛过程中完成10次比赛后，甲乙双方各取胜5次，且甲队获得擂台赛的最终胜利，这样的比赛结果有多少种可能？我们先把完成10次比赛后甲乙双方各取胜5次转化为非降路径上的表达，即该条路径经过（5，5），因此解决该问题的关键在于考察从（0，0）出发，途经（5，5）并且最终落点于（8，7）的非降路径的数目。那么，这类的路径每一条都可以分为两段，前一段为从（0，0）到（5，5）的部分，共有105种可能；另一段则为从（5，5）到终点（8，7）的部分，共有5

2种方式。再由乘法原则可知，满足这样要求的比赛结果有105·52种。

四、问题的推广

我们还可以利用非降路径考察更复杂的情形。例如，假设甲乙两队起初各有n名队员，两队队员按序出场，两队各取一人对弈，进行一对一单败淘汰赛，那么比赛开始后甲队一直领先且取得最终的胜利有多少种可能？我们定义与比赛结果相对应的非降路径是从（0，0）出发，每一局的比赛若甲方获胜则格路向右移动一步，若乙方获胜则格路向上移动一步。若甲方取得最终的胜利则规定该条非降路径的终点达到（n，n-1），若乙方取得最终的胜利则规定该条非降路径终点达到（n-1，n）。在这些定义的基础上，我们尝试将“比赛开始后甲队一直领先”转化为对应的非降路径上的体现，即该条路径一直位于直线y=x下方，而甲队取得最终胜利则对应于该条非降路径的终点为（n，n-1）。因此，这样一个附加了条件的一对一单败淘汰赛问题就转化为考察在平面坐标系中从（0，0）出发，始终位于直线y=x下方且终点为（n，n-1）的非降路径的数目。下面，我们尝试计算这类非降路径的数目。若第一局比赛甲队获得胜利，则对应的非降路径从（0，0）出发向右移动一步走到了（1，0），接着再从（1，0）到达（n，n-1），这意味着甲队获得最终的胜利，这样的非降路径一共有2n-2n-1条。在这么多非降路径中，我们只想保留始终位于直线y=x下方的路径，因此需要在总数中将不符合条件的路径数目减去。那么如何计算不符合条件的路径数目呢？我们转而考察第一局为乙队胜出但甲队获得最终的胜利这一情形所对应非降路径的数目，即从（0，0）出发向上移动一步后走到（0，1），再走到点（n，n-1）的非降路径数目为2n-2n-2。由于这类非降路径经过（0，1）和（n，n-1）点，因此它们与直线y=x之间必定存在除去（0，0）以外的交点。对于任一条这类非降路径，我们选取它与直线y=x的交点中横坐标最小且非零的交点A，并以直线y=x为对称轴，将从（0，0）出发，经过（0，1）并到达交点A的这段非降路径做镜面对称，变换到直线y=x的另一侧。于是，我们得到了一条从（0，0）出发，经过（1，0）与交点A并最终到达（n，n-1）的非降路径，如图4所示。这一类型的非降路径的数目为2n-2n-2，正是从（0，0）出发，途经（1，0）终到（n，n-1）且不完全位于直线y=x之下的非降路径的数目。因此，从（0，0）出发始终位于直线y=x下方且终点为（n，n-1）的非降路径的数目为2n-2n-1-2n-2n-2=1n2n-2n-1，即著名的组合数——卡特兰数［3］。

进一步地，我们考虑甲乙两队在进行一对一单败淘汰赛的前提下，甲队一直未被超越且取得最终的胜利有多少种可能？甲队取得最终的胜利则意味着对应的非降路径的终点仍为（n，n-1）。而这里的“甲队一直未被超越”转化为对应的非降路径的表现形式则应为该条路径从未越过直线y=x，即除去（0，0）以外，该条非降路径仍可以与直线y=x有接触但未穿过。对于这一类的非降路径，我们先换一个角度来考虑，就是将“可以与直线y=x有接触但未穿过”转变为“完全位于直线y=x+1下方”。因此，我们的目标转化为计算从（0，0）出发走到（1，0），且完全位于直线y=x+1下方，并最终达到（n，n-1）的非降路径的数目。所以，我们只需要找到从（1，0）到（n，n-1）但不完全位于直线y=x+1下方的非降路径数目并将其从（1，0）出发最终达到（n，n-1）的非降路径数目中减去即可。因此，我们以直线y=x+1为对称轴，找到（1，0）的对称点（-1，2），考察从（-1，2）到（n，n-1）的非降路径，事实上这类非降路径与直线y=x+1必有交点。接着，对于每一条这样的非降路径，我们找到其与直线y=x+1交点中横坐标最小的点B，将从（-1，2）到B的这部分的路径以直线y=x+1为轴，做镜面对称变换到直线y=x+1下方，如图5所示。这样就形成一条从（0，0）出发走到（1，0），经过点B，最后达到（n，n-1）的非降路径，而这条路径是不完全位于直线y=x+1下方的，也是穿过直线y=x的。由此可见，我们想要计算的不符合条件的非降路径数目与从（-1，2）到（n，n-1）的非降路径数目是相同的，即2n-2n-3。所以，从（0，0）出发，最终达到（n，n-1）且未穿过直线y=x的非降路径数目为2n-2n-1-2n-2n-3=2n+12n-1n-1。

结语

通过这样的教学案例的运用，首先，我们将趣味性融入教学，不仅加深了学生们对组合数学知识的掌握，还让他们了解了一场传奇的围棋擂台赛，增强了文化自信。其次，本文针对同一问题利用不同的方法进行求解，并逐步加大问题难度进行分析研究，激发了学生们的学习兴趣。最后，数学与生活之间连接的建立让学生们真实地体会到数学的思想方法，提高了数学素养。相信这种寓教于思、融学于趣、化教于心的教学理念会为我们的数学教育增添更多的光彩。

参考文献：

［1］华罗庚.大哉数学之为用：华罗庚科普著作选集［M］.武汉：长江文艺出版社，2023：261272.

［2］BRUALDI"R"A.组合数学［M］.5版.冯速，等译.北京：机械工业出版社，2012：187188.

［3］杨雅琴，李秋月，马腾宇.组合数学［M］.北京：国防工业出版社，2013：5762.

基金项目：河海大学新工科、新农科、新文科研究与改革实践项目（B2301914）；江苏本科高校“理工类公共基础课程教学改革研究”专项重点课题（2024LGJK011）；江苏高校“青蓝工程”资助

作者简介：沈一颖（1987—"），女，汉族，江苏南京人，理学博士，副教授，研究方向：组合数学；郝小健（1987—"），男，汉族，河北石家庄人，理学博士，副教授，研究方向：组合数学。