[中學] 每一點都要經過

[mj813 (薩坨十二惡皆空)]

三列，每列八個點。
共24個點以棋盤式排列。
由左下角點作一路徑抵達右上角點，
（每步只能向上下左右走）
且每一點皆要經過一次。
則有幾種不同的路徑？
拜託各位了！感恩！


--
Sent from nPTT on my iPhone 12 mini

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.168.0.247 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1754571110.A.1B0.html
→ Ricestone   : 64?
→ Ricestone   : 一開始只能選右跟上，沒有選上的話後面也都不能選下
→ Ricestone   : 而當你第一次選上之後整個棋盤會被一意地縮小成較小
→ Ricestone   : 的棋盤，只是起點跟終點變成同側的狀況
→ Ricestone   : 所以就直接同時討論同側跟異側的小棋盤再推廣
→ Ricestone   : 可知n>2時同側跟異側路徑數都是2^(n-2)
→ Ricestone   : 應該有比較好的辦法只是我可能忘了
→ mj813       : 感謝
→ Ricestone   : 倒過來分析可能比較簡明
→ Ricestone   : 先定義一下符號，{a_n}是3*n的棋盤起終點異側的方法
→ Ricestone   : 數，{s_n}是同側的方法（路徑）數
→ Ricestone   : 則a_n將會是倒數一步為終點左側以及倒數一步為終點
→ Ricestone   : 下側的路徑數的和，而其中左側路徑數實際上會等於
→ Ricestone   : a_(n-1)，因為多的那兩點有且只有唯一的走法走完；
→ Ricestone   : 下側路徑則會是s_(n-1)  （以上討論基於n>=2時）
→ Ricestone   : 另外由相似的討論可以知道s_n也一樣是s_(n-1)+
→ Ricestone   : a_(n-1)，所以可以知道s_n=a_n，進一步可以知道
→ Ricestone   : 當n>2時a_n=2*a_(n-1)，又因a_2=1，所以a_n=2^(n-2)
→ musicbox810 : 這是一筆畫問題嗎？
→ Ricestone   : 如果不是每點經過且只經過一次應該沒辦法問
→ Ricestone   : 就是漢米頓路徑