k-foldability of words

DOI10.1016/J.DAM.2018.12.028zbMATH Open1411.05009arXiv1710.10616OpenAlexW2766426016MaRDI QIDQ1735671FDOQ1735671

Authors: Xianqiang Yang 

Publication date: 28 March 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We extend results regarding a combinatorial model introduced by Black, Drellich, and Tymoczko (2017+) which generalizes the folding of the RNA molecule in biology. Consider a word on alphabet $A_1,overline{A}_1,ldots,A_m,overline{A}_m$ in which $overline{A}_i$ is called the complement of $A_i$. A word $w$ is foldable if can be wrapped around a rooted plane tree $T$, starting at the root and working counterclockwise such that one letter labels each half edge and the two letters labeling the same edge are complements. The tree $T$ is called $w$-valid. We define a bijection between edge-colored plane trees and words folded onto trees. This bijection is used to characterize and enumerate words for which there is only one valid tree. We follow up with a characterization of words for which there exist exactly two valid trees. In addition, we examine the set $mathcalR(n,m)$ consisting of all integers $k$ for which there exists a word of length $2n$ with exactly $k$ valid trees. Black, Drellich, and Tymoczko showed that for the $n$th Catalan number $C_n$, $C_n,C_{n-1}subsetmathcalR(n,1)$ but $kotinmathcalR(n,1)$ for $C_{n-1}<k<C_n$. We describe a superset of $mathcalR(n,1)$ in terms of the Catalan numbers by which we establish more missing intervals. We also prove $mathcalR(n,1)$ contains all non-negative integer less than $n+1$.

Full work available at URL: https://arxiv.org/abs/1710.10616

Recommendations

• Valid plane trees: combinatorial models for RNA secondary structures with Watson-Crick base pairs
• Folding words around trees: models inspired by RNA
• RNA secondary structures and bicoloured ordered trees.
• scientific article; zbMATH DE number 3928776
• scientific article; zbMATH DE number 7152756

zbMATH Keywords

Catalan numbersplane treesnon-crossing perfect matchings

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Enumerative combinatorics. Volume 2.
• Title not available (Why is that?)
• Valid plane trees: combinatorial models for RNA secondary structures with Watson-Crick base pairs
• Valency enumeration of rooted plane trees

Cited In (2)

• Valid plane trees: combinatorial models for RNA secondary structures with Watson-Crick base pairs
• Folding words around trees: models inspired by RNA

This page was built for publication: \(k\)-foldability of words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1735671)