Wikipedia PDF

暖身題

小明的家及上班的地點分別位於下圖中坐標為 (0,0) 及 (10,10) 的位置,圖中的直線與橫線代表著道路。假設小明想由家裡出發,循最短的路徑到達上班地點,也就是說,他隨時不是向東就是向北,請問他總共有幾種走法? Error! Click to view log. 這是一個簡單的問題。不管小明怎麼走,他都須向東及向北各走 10 格,如果我們將向東一格及向北一格分別用一個 $E$ 及一個 $N$ 來表示,那麼小明的任何一種走法都可以用一個包含了 10 個 $E$ 及 10 個 $N$ 的字串來描述;反過來說,任何一個由 10 個 $E$ 及 10 個 $N$ 組成的字串就對應到一種可能的走法。因此,由 10 個 $E$ 及 10 個 $N$ 可組成多少個字串就對應到小明有多少種走法,而這個數很顯然是由 20 個位置中選出 10 個來作為 $E$ 的位置的方法數,也就是 $C(10,20)$;一旦選定了10 個 $E$ 的位置,剩下的位置也就是 10 個 $N$ 的位置。

加上一條限制

假設有一條河流筆直地流經小明的家及上班的地點,這兩個處所都位於河的東側;由於河上沒有任何橋樑可供兩岸往來,因此小明上班的路徑無法跨過這條河流(也就是圖中連接 (0,0) 與 (10,10) 的對角線);每當小明向北碰到對角線就不得不轉向東行。在這樣的限制下,我們想要知道小明有多少種走法。下圖顯示了三種可能的路徑:如果我們沿用前述以 E 及 N 來描述路徑的方式,那麼上面三個圖的最左邊的圖顯示的路徑相當於 ENENEENEENNNEEENNNEN 中間的圖顯示的路徑相當於 ENENEENEENNNEEENNNEN 最右邊的圖顯示的路徑則相當於 ENENEENEENNNEEENNNEN 讀者不難看出這種字串的開頭第一個 字母一定是 E,最後一個字母一定是 N ,也就是說,小明一開始一定是向東,而抵達終點時一定是朝北。 如果沒有河流的限制,我們已經知道小明總共有 $C(10,20)$ 種走法,這些走法可以分為兩類,一類是走的過程中沒有跨過河流的(也就是符合要求的),另一類則是會跨過河流的(也就是「不可行」的)。