回上方
登入

格子路徑

從2*2方格的左上角出發,沿著向右或向下的路徑前進,最後到達右下角,總共有6種不同的走法。

【最後目標】

從20*20方格的左上角出發,沿著向右或向下的路徑前進,最後到達右下角,總共幾種不同的走法?


假設在一個5*3的方格紙中

每一橫列小段稱為a,每一縱列小段稱為b,從左上到右下的每一條相異路徑,必然通過5個a,且通過3個b,這8個字母的排列順序,對應到為一個路徑,如下圖的路徑對應為abaabbaa

又如下圖的路徑對應為baaababa

請問5個a、3個b的排列方法有多少呢?

5+3=8,總共有8個元素要排列,因此可排列出8!=8*7*6*5*4*3*2*1種不同排法。

因為5個a沒有順序性,因此重覆出現了5!=5*4*3*2*1次。

因為3個b沒有順序性,因此重覆出現了3!=3*2*1次。

所以總共有(5+3)!/(5!*3!)種不同的排列方法。

階乘寫法可以參考第20題。


本單元課程自2018.2.21日起已被瀏覽 497