Klazar trees and perfect matchings

DOI10.1016/J.EJC.2009.11.004zbMATH Open1231.05071arXiv0810.4901OpenAlexW1991386078WikidataQ60692172 ScholiaQ60692172MaRDI QIDQ976148FDOQ976148

David Callan

Publication date: 17 June 2010

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

Abstract: Martin Klazar computed the total weight of ordered trees under 12 different notions of weight. The last and perhaps most interesting of these weights, w_{12}, led to a recurrence relation and an identity for which he requested combinatorial explanations. Here we provide such explanations. To do so, we introduce the notion of a "Klazar violator" vertex in an increasing ordered tree and observe that w_{12} counts what we call Klazar trees--increasing ordered trees with no Klazar violators. A highlight of the paper is a bijection from n-edge increasing ordered trees to perfect matchings of [2n]={1,2,...,2n} that sends Klazar violators to even numbers matched to a larger odd number. We find the distribution of the latter matches and, in particular, establish the one-summation explicit formula sum_{k=1}^{lfloor n/2 rfloor}(2k-1)!!^2 StirlingPartition{n+1}{2k+1} for the number of perfect matchings of [2n] with no even-to-larger-odd matches. The proofs are mostly bijective.

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

Recommendations

• On the number of matchings of a tree
• scientific article
• Perfect matchings and \(k\)-decomposability of increasing trees
• scientific article; zbMATH DE number 3895093
• A pairing of the vertices of ordered trees

zbMATH Keywords

Klazar violator vertexStirling partition

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Twelve countings with rooted plane trees
• The blossoming of Schröder's fourth problem
• Ordered trees with prescribed root degrees, node degrees, and branch lengths
• Addendum to: Twelve countings with rooted plane trees

Cited In (4)

• The cycle descent statistic on permutations
• Ordered partitions and drawings of rooted plane trees
• On the number of matchings of a tree
• From Madhava–Leibniz to Lehmer’s Limit

Uses Software

• OEIS

This page was built for publication: Klazar trees and perfect matchings

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