一座山的山棱线由许多片段的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)