[問題] 遞增的山頂(關於路徑)
一座山的山稜線由許多片段的45度斜坡構成，
每一個片段不是上坡 / 就是下坡 \。
請問有多少種山稜線的形狀，使得所有山頂的位置由左而右非遞減呢？
所有的山稜線都必須完整，也就是說左右兩端都必須是高度為0的山腳，
而且不能有任何山谷的位置隱沒在地平線底下。
EX.寬度為 2 的山，只能為 /\，也就是 (010) 1組。
/\
寬度為 4 的山可以是 /\/\ (01010)與 / \ (01210) 這2組。
/\
寬度為 6 的山可以是 /\/\/\ (0101010) 與 /\/ \ (0101210)
/\
/\/\ / \
與 / \ (0121210) 及 / \ (0123210) 這4組。
所以山的寬度必須為偶數。
請問現在若任給一數 n，如何算出對應的可能數 N？
因為數量遞增的很快，我找不太到規律....
附上前5個的 (n,N) 及 當為 n 時，最高高度為 k 的數量對應
(2,1) (4,2) (6,4) (8,9) (10,21)....
n = 2 n = 4 n = 6 n = 8 n = 10
k k k k k
1:1 1:1 1:1 1:1 1:1
2:1 2:2 2:4 2:7
3:1 3:3 3:8
4:1 4:4
5:1
另外，若山頂不限制是非遞減型態，
那麼 (n,N) 的數量對應又是如何呢？
如果我沒算錯，這個的前4組是
(2,1) (4,2) (6,5) (8,14)...
p.s.可以想像成將一個正方形沿對角線切成一半，
然後將邊長割成 n/2 個，算路徑數。
所以不限制是非遞減型態可以用標數法解決。
註：非遞減型態所出現的數列是卡塔蘭數
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.85.142.90
※ 編輯: Cidolfas 來自: 219.85.142.90 (09/09 16:08)
※ 編輯: Cidolfas 來自: 219.85.142.90 (09/09 16:14)