engleski

Secondary structures and some related combinatorial objects

A secondary structure is a (planar, labeled) graph on the vertex set $[n]$ having two kind of edges: the segments $[i, i+1]$, for $1 \leq i \leq n-1$, and arcs in the upper half-plane connecting some vertices $i, j$, where $j-i>l$, for some fixed integer $l$. Any two arcs must be totally disjoint. We establish connections between secondary structures and some well known combinatorial families, such as lattice paths, matchings and restricted permutations. Then we give some applications and connections with polygon dissections and polyominoes, using earlier enumerative results on secondary structures to provide explicit formulas and asymptotics for enumerating sequences of those families.

secondary structure ; Motzkin path ; Dyck path ; polygon dissection ; restricted permutation

nije evidentirano