Matrix Identities on Weighted Partial Motzkin Paths

William Y.C. Chen, Nelson Y. Li, Louis W. Shapiro, and Sherry H.F. Yan

  Abstract:  We give a combinatorial interpretation of a matrix identity on Catalan numbers and the sequence (1, 4, 42, 43, ...) which has been derived by Shapiro, Woan and Getu by using Riordan arrays. By giving a bijection between weighted partial Motzkin paths with an elevation line and weighted free Motzkin paths, we find a matrix identity on the number of weighted Motzkin paths and the sequence (1, k, k2, k3, ...) for k2. By extending this argument to partial Motzkin paths with multiple elevation lines, we give a combinatorial proof of an identity recently obtained by Cameron and Nkwanta. A matrix identity on colored Dyck paths is also given, leading to a matrix identity for the sequence (1, t2 + t; (t2 + t)2, ...).

  AMS Classification:  05A15, 05A19

  Keywords:  Catalan number, Schröder number, Dyck path, Motzkin path, partial Motzkin path, free Motzkin path, weighted Motzkin path, Riordan array

  Download:   PDF