Noncrossing Linked Partitions and Large (3, 2)-Motzkin Paths
William Y.C. Chen and Carol J. Wang
Abstract: Noncrossing linked partitions arise in the study of certain transforms in free probability theory. We explore the connection between noncrossing linked partitions and (3, 2)-Motzkin paths, where a (3, 2)-Motzkin path can be viewed as a Motzkin path for which there are three types of horizontal steps and two types of down steps. A large (3, 2)-Motzkin path is a (3, 2)-Motzkin path for which there are only two types of horizontal steps on the x-axis. We establish a one-to-one correspondence between the set of noncrossing linked partitions of {1,..., n + 1} and the set of large (3, 2)-Motzkin paths of length n, which leads to a simple explanation of the well-known relation between the large and the little Schröder numbers. AMS Classification: 05A15, 05A18. Keywords: Noncrossing linked partition, Schroder path, large (3, 2)-Motzkin path, (3, 2)-Motzkin path, Schröder number Download: PDF |