I would like to know how to generate all rooted trees on $n$ vertices using Mathematica?
More precisely, I am interested in generating algebraic expressions equivalent to rooted trees and constructed as follows:
- Let $U$ be some function of one variable $x$.
- All expressions are obtained using exclusively composition by $U$ or multiplication by $U$
- Multiplication by $U$ correspond to adding a child to a vertex.
- Composition by $U$ corresponds to adding a parent.
Clarifying examples:
$U\big[U[x] U[x]\big]$ is equivalent to the rooted tree:
While $U[x]U\big[U[x] U[x]\big]$ is equivalent to the rooted tree
And finally $U\Big[U[x]\,U\big[U[x] U[x]\big]\Big]$ is equivalent to the rooted tree
Could you please help me generate all rooted trees on $n$ vertices, i.e. algebraic expressions as above with $U$ appearing $n$ times?
