publication . Article . 2003

Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings

Klazar, Martin;
Open Access
  • Published: 01 Feb 2003 Journal: Advances in Applied Mathematics, volume 30, pages 126-136 (issn: 0196-8858, Copyright policy)
  • Publisher: Elsevier BV
Abstract
AbstractThe number conn counts matchings X on {1,2,…,2n}, which are partitions into n two-element blocks, such that the crossing graph of X is connected. Similarly, cron counts matchings whose crossing graph has no isolated vertex. (If it has no edge, Catalan numbers arise.) We apply generating functions techniques and prove, using a more generally applicable criterion, that the sequences (conn) and (cron) are not P-recursive. On the other hand, we show that the residues of conn and cron modulo any fixed power of 2 can be determined P-recursively. We consider also the numbers scon of symmetric connected matchings. Unfortunately, their generating function satisfi...
Subjects
free text keywords: Applied Mathematics, Discrete mathematics, Combinatorics, Enumeration, Mathematics, Mathematical analysis, Laurent series, Catalan number, Generating function, Vertex (geometry), Modulo, Chord diagram, Differential equation
Related Organizations
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . 2003

Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings

Klazar, Martin;