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.