Annular non-crossing matchings

zbMATH Open1336.05014arXiv1508.01712MaRDI QIDQ2808553FDOQ2808553

Puttipong Pongtanapaisan, Paul Drube

Publication date: 24 May 2016

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

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

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

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)

Cited In (3)

• Counting curves on surfaces
• Toric manifolds over cyclohedra
• Title not available (Why is that?)

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)