Pairs of noncrossing free Dyck paths and noncrossing partitions

William Y.C. Chen, Sabrina X.M. Pang, Ellen X.Y. Qu and Richard P. Stanley

  Abstract:  Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n + 1] with n + 1 blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm.

  AMS Classification:  05A10, 05A15

  Keywords:  Dyck path, free Dyck path, plane partition, noncrossing partition, vacillating tableau

  Download:   pdf