高中數學：格子點上只能走↓↑→，共有幾種走法？

題目：

如上圖，從A沿著格子線到B，只能向右(→)、向上(↑)或向下(↓)，且路徑不得重複，請問

(1)有幾種走法？
(2)不經過P有幾走法？
(3)經過P有幾走法？
(4)不經過P且不經過Q有幾走法？
(5)經過P且經過Q幾走法？
解：
(1)

無論如何走，從A到B一共有四次向右(→)

如上圖，第一次向右有3種選擇、第二次向右有4種選擇、第三次向右有4種選擇，最後一次向右有5種選種，所以共有3x4x4x5 = 240種走法。

(2) 由於不經過P，將一定會經過P的路徑標註起來(如圖b)，再將其刪除(圖c)。

圖(b)

圖(c)

圖(d)

在圖(d)中，第一次向右有3種走法，最後一次向右仍有5種走法。由於P點已刪除，第二次向右與第三次向右被拆成上下兩部份。在上半部，第二次向右與第三次向合併成一種；在下半部，第二次向右有2種走法、第3次向右有3種走法，因此下半部有2x3=6種走法。全部共有3 x (1+2x3) x 5 = 3x7x5 = 105種走法。

(3)經過P有的走法 = 全部減去不經過P的走法 = 240-105 = 135。

(4)將經過P, 或經過Q的路徑標示出來(圖e)，並將其刪除(圖f)

圖(e)

圖(f)

圖(g)

第一次向右有三種走法，接著可區分成上半部與下半部，上半部有兩種走法；下半部有2x4=8種走法。由於不能向左走，所以上半部不能走到下半部，但下半部可往上走上半部。因此共有3x(2+2x4) = 3x10 = 30種走法。

(5)先計算不經過Q的走法，作法如題(2)，先將必經Q的路徑刪除，如下圖(h)

圖(h)

第一次向右有三種走法、第二次向右有四種走法，接著分上半部有2x2=4種走法、下半部有2種走法，因此共有 3x4x(2x2+2) = 3x4x6 = 72 走法。

小結: 不經過Q有72種走法、經過Q有240-72=168種走法。

以上圖來解釋，最大的圈圈代表全部的走法，共有240種、黃圈圈代表經過P的走法、藍圈圈代表經過Q的走法。

黃圈圈與藍圈圈的聯集=全部-(不過P)且(不過Q) = 240-30 = 210

經過P且經過Q幾走法就是黃藍圈圈的交集=(過P)+(過Q)-聯集 = 135+168-210 = 93。

-- END --