平日在街上走，橫街窄巷之間轉彎，來來去去的時候，當中原來可以有點組合數學的蹤跡。比如圖一之中，各線代表不同的街道，各點代表不同的位置，上方代表北方，那麽由A點走到L點的路線選擇，就有組合數學在其中。
對於以下的問題，將會提出兩個解法，並指出兩方面會對組合數學相關的公式有什麽洞見。
問 題
在圖一中，由A點走到L點，若果每次只能夠向北方走或東方走，那麽共有多少條路線？
答案
解一：先考慮由A到每一點有多少條路線。與A相鄰的兩點，明顯只有一條路線（圖二）。
圖二中由A點到E點，只能由E點的西方和南方來，所以A到E有[1+1=2]條路。普遍來說，每一點都只能由該點的西方與南方來，即到該點的路線數，是左方和下方的數字相加。因此有A點到每一點的路線正如圖三那樣。
由此得知，由A點到L點的路線數是10。
解二：由A到L的各條路線，都用英文字母N和E表示。N代表向北，E代表向東，而NNEEE代表先向北走兩次，再向東走三次，如此類推。那麽這樣五個字母中，必有2個N和3個E，因為由A到L，必須有兩次向北和三次向東。
因此每條路線都會對應一組英文字母。而路線的總數，就是在5個英文字母中，選其中兩個為N的組合數。第一個N有5個選擇，第二個N只有4個選擇，而兩者不分次序，因此有[5×4][2][=10] 個組合，也就是有10條路線。
以上兩個解之中，其中解二用到了5個字母中選2個為N，而且不分次序的概念，這在數學上有固定的符號表示，就是[C52][=][5×4][2] [C52][=][5×4][2] 。普遍來說，[Cnr][=][n(n-1)(n-2)...(n-r+1)][1×2×3...×r] ，即是分子由n開始，倒數r個數相乘，再除以由1到r的乘積。
由這道[Cnr]的公式，再套用在解一的想法上去，就有點新發現。由解二得知，由A到L的路線有[C52]條路，而到L的路都是由左方和下方來的，而左方的就是[C42]，下方的就是[C41]，從而得到算式[C41][=][+][C42][C52]。這裡為了便於理解，也解釋一下為什麽L左方是[C42]，因為到達該點需要由A點向北方走兩次和向東方走兩次，用英文字母表示，就是NNEE之類的4個英文字母中，找2個為N的組合數，即[C42]。[C41]的情況也是類似。
若是考慮向北和向東走的總次數為n，其中有r次向北方走，那麽路線的總數，就是[Cnr]，參考[C41][=][+][C42][C52]的算式，得知由左方來的話，向北方的次數是一樣多，但走的路會少1次，因此是[Cn-1r]，而由下方來的話，走的路會少1次之餘，向北方的次數也會少1次，即[Cn-1r-1]。普遍來說，就是[=][+][Cnr][Cn-1r][Cn-1r-1]
這是一道常用的組合恒等式。
以上的組合恒等式，若果單從代數的角度看，由定義上出發，是不難證明的，但上述由情景中一題兩解之間，發現出恒等式，就不止是證明的方法，亦是發現的方法。事實上組合數學裡，由一題多解之中，能發現的組合恒等式是不少的，這個另文再講。 ■張志基
簡介：香港首間提供奧數培訓之教育機構，每年舉辦奧數比賽，並積極開辦不同類型的奧數培訓課程。學員有機會獲選拔成為香港代表隊，參加海內外重要大賽。詳情可瀏覽：www.hkmos.org。
逢星期三見報