主題
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. “迪克路徑。” 來自 —— 資源。 https://mathworld.tw/DyckPath.html

主題分類