計數組合在古典概型中的應用實例

諶 娜

（天津理工大學理學院 天津 300384）

概率論與數理統計是一門研究隨機現象的數學分支學科。目前，絕大多數高校的理、工、經管等專業均設有該課程。筆者在教授這門課程時發現學生在學習過程中普遍感覺概念抽象難于理解，計算復雜難于掌握。基于這一問題，教師在教授這門課程時有必要探索新的教學方法和手段，從而提高學生的學習積極性與教學質量。

多學科交叉融合是高校學科發展的必然趨勢，同時也是重要的教學方法與手段。本文探究組合數學在概率論與數理統計授課中的應用。一方面，組合數學作為高中便有所接觸的數學分支學科易于被學生理解；另一方面，在概率論課堂中提及組合數學也會給學生帶來新鮮感，激發學生學習興趣。

具體地，我們將會應用組合數學中的計數組合學。它是組合數學的一個最基本的研究方向，主要研究各種組合結構的計數問題。古典概型中許多事件的計數問題均可視為組合計數問題，例如為大家熟知的取球問題，其概率計算便依托于排列組合計數問題。本文則將展示組合數學中的Ballot格路及圈定理在講授古典概型中經典投票問題時的應用，具體教學思路如下。

古典概型是概率論中直觀且簡單的模型，概率的許多運算規則，也是在古典概型中首先發現并加以推廣得到的。具有以下兩個性質的概率模型稱為古典概型：

（1）隨機試驗所包含的基本事件是有限的；

（2）每個基本事件發生的可能性均相等。

古典概型又稱等可能概型，由法國著名數學家拉普拉斯首次提出。若在一次隨機試驗中，可能出現的結果共有n個，且所有結果出現的可能性相同，則每個基本事件發生的概率為1

n.若某事件A包含m個基本事件，那么事件A發生的概率P(A)=m

n。由此可見，計算古典概型事件的概率歸于計數問題。

表1：0≤k≤n≤7時b(n，k)的取值

事實上，這便是組合數學中的經典序列ballot數, 詳情可見組合序列網站OEIS [1]中的A009766.下面我們將用組合方法計算給出b(n，k)的明確表達式

在平面直角坐標系中，橫縱坐標均為整數的點稱為平面格點。平面格路(path)是指在所有格點中，從一點走到另一點，且只走格點的路。我們稱只由步N(0，1)或E(1，0)構成的格路為NE格路。這其中最為著名的NE格路為 Dyck格路(Dyck path)。本文中，我們將要研究Dyck格路的推廣形式，即Ballot格路(Ballot path)。

定義1：Dyck格路為平面上從(0，0)到(n，n)的一條格路（n≥1），每步只能按 N(0，1)或 E(1，0)前進, 且不會穿越到直線的下方。記該Dyck格路的長度為n。

定義2：Ballot格路為平面上從(0，0)到(n，k)的一條格路（n≥k），每步只能按 N(0，1)或 E(1，0)前進，且路徑不會穿越到直線y=x的下方。

圖1：Dyck格路(左)與Ballot格路(右)

圖1給出了Dyck格路與Ballot格路的具體示例。值得指出的是，上述圖例中的格路也可由含有N和E的詞表示，例如上圖Ballot格路可等價表示為NENNENNE。設(0，0)為起始點，在投票過程中，若甲獲勝則向N(0，1)方向前進一步，乙獲勝則向E(1，0)方向前進一步。例如，當n=3且k=2時所有經典投票結果可一一對應到格路，如圖2所示。那么顯然，經典投票問題中甲獲n票乙獲k票且甲票數一直不落后于乙對應(0，0)到(n，k)的所有Ballot格路。故b(n，k)亦為由(0，0)到(n，k)的所有Ballot格路的個數。

組合數學中，計算格路的一個重要方法為 Dvoretzky與Motzkin[2]給出的圈定理(Cycle Lemma)。他們便是利用圈定理討論了經典投票問題。

圖2：n=3，k=2時經典投票結果對應的Ballot格路

定理3： (圈定理)對于任意在整數集合{1，0，-1，-2，…}中取值且滿足a1+a2+…+an=k(k≥0) 的n維整數序列(a1，a2，…，an)，共存在k個下標i使得(ai，…，an，a1，ai-1)部分和ai，ai+ai+1，…，ai+ai+1+…+an，ai+ai+1+…+an+a1，…，ai+ai+1…+an+a1+…ai-1均為正。

利用定理3可知，給定n+k+1維整數序列(a1，a2，…，an+k+1)，其中a1，a2，…，an+k+1中有n+1個1，k個-1，則共存在n+1-k個下標i使得(ai，…，an+k+1，a1，…ai-1)所有部分和均為正。下面，我們將利用圈定理計算b(n，k)，具體步驟如下：

例如 NNENNEE經此步操作可得到格路集合{NNENNEE，NENNEEN，NNEENNE，NEENNEN}；