Reduction of m-Regular Noncrossing Partitions

William Y. C. Chen,   Eva Y. P. Deng and Rosena R. X. Du

  Abstract:  In this paper, we present a reduction algorithm which trans-forms m-regular partitions of [n] = {1,2,. . . , n} to (m-1)-regular partitions of [n-1]. We show that this algorithm preserves the noncrossing property.This yields a simple explanation of an identity due to Simion-Ullman andKlazar in connection with enumeration problems on noncrossing partitions and RNA secondary structures. For ordinary noncrossing partitions, the reduction algorithm leads to a representation of noncrossing partitions in terms of independent arcs and loops, as well as an identity of Simion and Ullman which expresses the Narayana numbers in terms of the Catalan numbers.

  AMS Classification:  05A18, 05A15, 92D20.

  Keywords:  Partition, noncrossing partition, m-regular partition, RNA secondary structure, Davenport-Schinzel sequence, Narayana number, Catalan number.

  Download:   pdf