论文标题
对称弧图的枚举
Enumeration of symmetric arc diagrams
论文作者
论文摘要
我们给出了与某些相关的四个类图中的对称元素列举对称元素的重复关系，这些图形与某些相关的弧度图和设定的分区相对应，其块不包含连续的整数。这些弧图是由RNA二级结构的研究激励的。例如，经典的RNA二级结构对应于3412个没有相邻换位的避开范围，而具有基本三元的结构可以表示为带有交叉的分区。我们的结果取决于组合论点。特别是，我们使用Motzkin路径来描述没有连接两个相邻节点的弧形的非交叉弧图，并且我们对长度与数字的总和相吻合的三元单词进行了明确的射击。我们还讨论了此处考虑的某些序列的渐近行为，以量化具有大量节点的对称结构的极低概率。
We give recurrence relations for the enumeration of symmetric elements within four classes of arc diagrams corresponding to certain involutions and set partitions whose blocks contain no consecutive integers. These arc diagrams are motivated by the study of RNA secondary structures. For example, classic RNA secondary structures correspond to 3412-avoiding involutions with no adjacent transpositions, and structures with base triples may be represented as partitions with crossings. Our results rely on combinatorial arguments. In particular, we use Motzkin paths to describe noncrossing arc diagrams that have no arc connecting two adjacent nodes, and we give an explicit bijection to ternary words whose length coincides with the sum of their digits. We also discuss the asymptotic behavior of some of the sequences considered here in order to quantify the extremely low probability of finding symmetric structures with a large number of nodes.
