圍棋比賽中的組合數學

摘"要：本文首先介紹了第一屆中日圍棋擂臺賽的比賽情況，其次討論了表格與非降路徑這兩類經典組合結構在圍棋比賽中的應用。通過構造兩個等勢集合之間的一一映射，建立相關集合之間的聯系，刻畫了組合物體的性質。這樣將趣味性融入數學的教學過程，激發了學生的學習興趣，提高了學生的數學素養。

關鍵詞：組合數學；表格；非降路徑；興趣教學

一、概述

數學是自然科學的根本，華羅庚先生曾經說過：“宇宙之大，粒子之微，火箭之速，化工之巧，地球之變，生物之謎，日用之繁，無處不用數學。”［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—"），男，漢族，河北石家莊人，理學博士，副教授，研究方向：組合數學。