一座山的山稜線由許多片段的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)