RNA secondary structures, Schröder paths and abab-free partitions

Abstract

In this paper we introduce a bijection between RNA secondary structures on n vertices with d unpaired bases and Schröder paths of order n with d diagonal steps, and consider the enumeration problem on RNA secondary structures based on the bijection. Motivated by the theory of partition, we give a one-to-one correspondence between RNA secondary structures on n bases with k base pairs and m-regular abab-free poor partitions with k blocks. Moreover, we get an expression about the number of RNA secondary structure with constrained conditions.