Klazar trees and perfect matchings

Martin Klazar computed the total weight of ordered trees under 12 different notions of weight. The last and perhaps the 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 [ 2 n ] = { 1 , 2 , … , 2 n } 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 ∑ k = 1 ⌊ n / 2 ⌋ ( 2 k − 1 ) ! ! 2 { n + 1 2 k + 1 } for the number of perfect matchings of [ 2 n ] with no even-to-larger-odd matches. The proofs are mostly bijective.