The pruning-grafting lattice of binary trees
We introduce a new lattice structure B, on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in B(n) equals to the Eulerian numbers 2(n) - (n + 1) (resp. (n - 1)(2)) and that the number of coverings is (2n n-1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure. (C) 2008 Elsevier B.V. All rights reserved.
lattices binary trees feasible sequences distribution sequences catalan numbers