# Klazar trees and perfect matchings - Mathematics > Combinatorics

Klazar trees and perfect matchings - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Martin Klazar computed the total weight of ordered trees under 12 differentnotions of weight. The last and perhaps most interesting of these weights,w {12}, led to a recurrence relation and an identity for which he requestedcombinatorial explanations. Here we provide such explanations. To do so, weintroduce the notion of a -Klazar violator- vertex in an increasing orderedtree and observe that w {12} counts what we call Klazar trees-increasingordered trees with no Klazar violators. A highlight of the paper is a bijectionfrom 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. Wefind the distribution of the latter matches and, in particular, establish theone-summation explicit formula sum {k=1}^{lfloor n-2 rfloor}2k-1!!^2StirlingPartition{n+1}{2k+1} for the number of perfect matchings of 2n withno even-to-larger-odd matches. The proofs are mostly bijective.

Author: David Callan

Source: https://arxiv.org/