k-foldability of words

DOI10.1016/J.DAM.2018.12.028MaRDI QIDQ1735671zbMATH OpenOpenAlexFDO

Authors Xianqiang Yang

Publication date 28 March 2019

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

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 691512 (Why is no real title available?)
• Enumerative combinatorics. Volume 2.
• Valency enumeration of rooted plane trees
• Valid plane trees: combinatorial models for RNA secondary structures with Watson-Crick base pairs

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)