We establish three identities involving Dyck paths and alternating Motzkin paths, whose proofs are based on variants of the same bijection. We interpret these identities in terms of closed random walks on the halfline. We explain how these identities arise from combinatorial interpretations of certain properties of the -Hermite and -Laguerre ensembles of random matrix theory. We conclude by presenting two other identities obtained in the same way, for which finding combinatorial proofs is an open problem | Path counting and random matrix theory Ioana Dumitriu and Etienne Rassart Department of Mathematics Massachusetts Institute of Technology dumitriu rassart @ Submitted Aug 21 2003 Accepted Nov 7 2003 Published Nov 17 2003 MR Subject Classifications 05A19 15A52 82B41 Abstract We establish three identities involving Dyck paths and alternating Motzkin paths whose proofs are based on variants of the same bijection. We interpret these identities in terms of closed random walks on the halfline. We explain how these identities arise from combinatorial interpretations of certain properties of the -Hermite and -Laguerre ensembles of random matrix theory. We conclude by presenting two other identities obtained in the same way for which finding combinatorial proofs is an open problem. 1 Overview In this paper we present five identities involving Dyck paths and alternating Motzkin paths. These identities appear as consequences of algebraic properties of certain matrix models in random matrix theory as briefly described in Section 2. Three of them describe statistics on Dyck and alternating Motzkin paths the average norm of the rise-by-altitude and vertex-by-altitude vectors for Dyck paths and the weighted average square norms of the rise-by-altitude and level-by-altitude vectors for alternating Motzkin paths. We describe these quantities in detail in Section 2 and provide combinatorial proofs for the identities in Section 3. In terms of closed random walks on the halfline these identities give exact formulas for the total square-average time spent at a node as well as the total square-average number of advances to a higher labeled node. For the other two identities we have not been able to find simple interpretations or combinatorial proofs that would complement the algebraic ones this is a challenge that we propose to the reader in Section 4. Supported by FCAR Quebec THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R43 1 2 Definitions main results and .
