Reduction of m-regular noncrossing partitions

DOI10.1016/J.EJC.2004.02.009MaRDI QIDQ1765607zbMATH OpenOpenAlexFDO

Authors William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du

Publication date 23 February 2005

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Catalan numberDavenport-Schinzel sequenceNarayana numberNoncrossing partitionRNA secondary structure

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Protein sequences, DNA sequences (92D20)

Abstract: In this paper, we present a reduction algorithm which transforms $m$-regular partitions of $[n]=1,2,\mathrm{...},n$ to $(m-1)$-regular partitions of $[n-1]$. We show that this algorithm preserves the noncrossing property. This yields a simple explanation of an identity due to Simion-Ullman and Klazar in connection with enumeration problems on noncrossing partitions and RNA secondary structures. For ordinary noncrossing partitions, the reduction algorithm leads to a representation of noncrossing partitions in terms of independent arcs and loops, as well as an identity of Simion and Ullman which expresses the Narayana numbers in terms of the Catalan numbers.

Recommendations

• Algorithms for non-crossing partitions
• On the structure of the lattice of noncrossing partitions
• Noncrossing partitions
• On trees and noncrossing partitions
• Enumeration of (k,2)-noncrossing partitions

Cites work

• p,q-Stirling numbers and set partition statistics
• A bijection between ordered trees and 2-Motzkin paths and its many consequences
• A Combinatorial Problem Connected with Differential Equations
• A correspondence between ordered trees and noncrossing partitions
• A map-theoretic approach to Davenport Schinzel sequences
• Bell numbers and \(k\)-trees
• Combinatorics of RNA secondary structures
• scientific article; zbMATH DE number 3928776 (Why is no real title available?)
• scientific article; zbMATH DE number 3745176 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1086865 (Why is no real title available?)
• Linear trees and RNA secondary structure
• Noncrossing partitions
• On \(abab\)-free and \(abba\)-free set partitions
• On the structure of the lattice of noncrossing partitions
• On trees and noncrossing partitions
• Ordered trees and non-crossing partitions

Cited in

(20)

• On the combinatorics of the Pfaff identity
• Identities involving Narayana polynomials and Catalan numbers
• Partitions of a set satisfying certain set of conditions
• On the Wadge reducibility of \(k\)-partitions
• Combinatorics of contacts in protein contact maps
• A simple bijection for enhanced, classical, and 2-distant \(k\)-noncrossing partitions
• Fubini numbers and polynomials of graphs
• Noncrossing normal ordering for functions of boson operators
• Regular simple queues of protein contact maps
• The research and progress of the enumeration of lattice paths
• Partitions and partial matchings avoiding neighbor patterns
• Gray codes and lexicographical combinatorial generation for nonnesting and sparse nonnesting set partitions
• Partitions of vertices and facets in trees and stacked simplicial complexes
• Explicit enumeration formulas for m-regular simple stacks
• New refinements of Narayana polynomials and Motzkin polynomials
• Heisenberg characters, unitriangular groups, and Fibonacci numbers
• Walks, partitions, and normal ordering
• Extended set partitions with successions
• Enumeration of (k,2)-noncrossing partitions
• Identities from weighted Motzkin paths

This page was built for publication: Reduction of \(m\)-regular noncrossing partitions

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