主题
Search

迪克路径

StaircaseWalkDiagonal

迪克路径是从 阶梯行走 从 (0,0) 到 (n,n) 的路径，该路径严格位于（但可以接触）对角线 y=x 之下。阶数为 n 的迪克路径的数量由卡塔兰数给出

C_n=1/(n+1)(2n; n),

即，1, 2, 5, 14, 42, 132, ... (OEIS A000108)。

等价地，由 n 个 1 和 n 个 -1 组成的具有非负部分和的序列的数量是 C_(n-1) (Bailey 1996, Brualdi 1997, Mays and Wojciechowski 2000)。以下表格总结了前几个。

n列表
1{1,-1}
2{1,1,-1,-1}
3{1,1,-1,1,-1,-1}, {1,1,1,-1,-1,-1}
4{1,1,-1,1,-1,1,-1,-1}, {1,1,-1,1,1,-1,-1,-1},
{1,1,1,-1,-1,1,-1,-1}, {1,1,1,-1,1,-1,-1,-1},
{1,1,1,1,-1,-1,-1,-1}

参见

卡塔兰数, 格路, Narayana 数, 阶梯行走

使用 探索

参考文献

Bailey, D. F. "计算 1 和 -1 的排列。" Math. Mag. 69, 128-131, 1996.Brualdi, R. A. 组合数学导论，第 4 版。 New York: Elsevier, 1997.Degenhardt, S. L. and Milne, S. C. "加权逆序统计及其对称群。" J. Combin. Theory Ser. A 90, 49-103, 2000.Mays, M. E. and Wojciechowski, J. "卡塔兰数的行列式性质。" Disc. Math. 211, 125-133, 2000.Sloane, N. J. A. 序列 A000108/M1459 在“整数序列在线百科全书”中。

在 中被引用

迪克路径

引用为

Weisstein, Eric W. “迪克路径。” 来自 MathWorld—— 资源。 https://mathworld.net.cn/DyckPath.html

主题分类