# How many trees can be constructed from k vertices using an LCA operator?

Consider the class of rooted trees and suppose I have at my disposal a lowest common ancestor (LCA) operator given by $$\textrm{lca}(u,v) = \text{the lowest common ancestor of u and v}$$ for all vertices $u,v$ belonging to the same tree.

Given $k$ vertices from a tree, I can apply my LCA operator to all pairs of vertices and thereby obtain new vertices to which I can apply the LCA operator once again etc. etc. In this way we construct a tree that contains the $k$ original vertices and has at most $2k-1$ vertices in total (easy to see).

Examples:

• If the $k$ vertices are all leaves in a full, binary tree, then the constructed tree is the full, binary tree tree with $2k-1$ vertices.
• If the $k$ vertices all belong to the same path, then the constructed tree is just a path of length $k$.

How many different trees can be constructed in this way from $k$ vertices using the LCA operator?

Said differently (in a labeled version which is OK): How many rooted trees are there with $k$ labeled vertices and all other vertices being generated from those $k$ vertices using an LCA operator?

An asymptotic formula or a good lower bound would be fine.

• For asymptotics, an upper bound on the number of k generated semilattices may help you. For labeled elements, the number is something like doubly exponential ($2^{2^k}$). For lower bounds look at general tree enumeration and consider trees wth k leaves and k+n vertices for n much smaller than k. Gerhard "Ask Me About System Design" Paseman, 2013.05.24 – Gerhard Paseman May 25 '13 at 6:40
• An upper bound with a double exponential looks very big to me. After all, there are at most $(2k-1)^{2k-3}$ labeled trees with $2k-1$ nodes. I have already looked at some enumeration results, but none of them give me exactly what I am looking for. I have now added another way of stating my question. – Esben May 25 '13 at 8:42