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, Schröder path, large (3, 2)-Motzkin path, Schröder number

  Download:   pdf