→ Cidolfas :先謝了，但在下認為這樣算有點沒效率，我當初這樣割 09/09 18:54
→ Cidolfas :山頂後來想想沒啥意思，因為後面n增加時，中間會出現 09/09 18:55
→ Cidolfas :許多前面沒出現的，不知道realation的「新值」，所以 09/09 18:56
→ Cidolfas :我想可能要從其他方向下手 Orz 09/09 18:57
※ 引述《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
我查了 nondecreasing peaks Dyck paths 卻查不出什麼前人結果
當然也可能是查的方向不對 關鍵字下錯.. 反正就是沒搞頭
我有個想法，先找出遞回式
舉例來說
「所有寬度為12，最高高度為3的山稜線有幾個？」
(i) 最後一山最高 那把最後一山砍掉 與一個寬度10，最高2的山對應
／＼
／＼／＼ ＼
／＼／＼／ ＼ ＼
(ii) 最後一山跟前山等高 最後一谷深度為一
把最後一山砍掉 與一個寬度10，最高3的山對應
／＼／＼
／ ＼ ＼
／＼／＼／ ＼ ＼
(iii) 最後一出山跟前山等高 最後一谷深度為二
把最後一山砍掉 與一個寬度8，最高3的山對應
／＼ ／＼
／＼／ ＼／ ＼
／ ＼ ＼
(iv) 最後一出山跟前山等高 最後一谷深度為三
把最後一山砍掉 與一個寬度6，最高3的山對應
／＼ ／＼
／ ＼ ／ ＼
／ ＼／ ＼
利用原po給的表格
k\n 2 4 6 8 10 12
------------------------------------------------------
1 1 1 1 1 1
2 1 2 4 7
3 1 3 8 19=7+8+3+1
4 1 4
5 1
接著的工作是要把generating function解出來 我就不管啦
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.25.198