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, 4^{2}, 4^{3}, ...) 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, k^{2}, k^{3}, ...) for k ≥2. 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, t^{2} + t; (t^{2} + 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 |