Mathematics – Combinatorics
Scientific paper
2008-10-27
Mathematics
Combinatorics
26 pages
Scientific paper
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.
No associations
LandOfFree
Klazar trees and perfect matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Klazar trees and perfect matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Klazar trees and perfect matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-324699