[其他] 遞增的山頂

[Cidolfas ()]

一座山的山稜線由許多片段的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 09:43)
→ sato186     :非遞減?? (6,4)??
→ Cidolfas    :6是指寬度，4是指寬度為6的情況下，有4組非遞減山頂
※ 編輯: Cidolfas        來自: 219.85.142.90        (09/09 11:11)
推 weeeeeeeeell:範圍是組合數學
→ Cidolfas    :我知道，但在限制條件下組合條件的表示式我求不出來
→ Vulpix      :不限制非遞減的話，是卡塔蘭數
→ Cidolfas    :多謝樓上！剩最麻煩的式子要導...