Annular non-crossing matchings

MaRDI QIDQ2808553zbMATH OpenFDO

Authors Paul Drube, Puttipong Pongtanapaisan

Publication date 24 May 2016

Published in Journal of Integer Sequences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.01712, http://www.emis.de/journals/JIS/VOL19/Drube/drube3.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Catalan numbernon-crossing matchingcombinatorial necklace

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30)

Abstract: It is well known that the number of distinct non-crossing matchings of $n$ half-circles in the half-plane with endpoints on the x-axis equals the $n^{th}$ Catalan number $C_n$. This paper generalizes that notion of linear non-crossing matchings, as well as the circular non-crossings matchings of Goldbach and Tijdeman, to non-crossings matchings of $n$ line segments embedded within an annulus. We prove that the number of such matchings $vertAnn(n,m)vert$ with $n$ exterior endpoints and $m$ interior endpoints correspond to an entirely new, one-parameter generalization of the Catalan numbers with $C_n=vertAnn(1,m)vert$. We also develop bijections between specific classes of annular non-crossing matchings and other combinatorial objects such as binary combinatorial necklaces and planar graphs. Finally, we use Burnside's Lemma to obtain an explicit formula for $vertAnn(n,m)vert$ for all $n,mgeq0$.

Recommendations

• Noncrossing matchings with fixed points
• Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings
• On the enumeration of non-crossing pairings of well-balanced binary strings
• Crossings and nestings of matchings and partitions
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle

Cited in

(4)

• Counting curves on surfaces
• Toric manifolds over cyclohedra
• On the enumeration of non-crossing pairings of well-balanced binary strings
• scientific article; zbMATH DE number 7596570 (Why is no real title available?)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Annular non-crossing matchings

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