# Generate expressions equivalent to rooted trees

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?

-

This might not be the most efficient way, but seems to do it:

ClearAll[expr];
expr[1] = {u[x]};
expr[n_Integer?Positive] := expr[n] =
Join[
DeleteDuplicates@Flatten@Table[
Outer[Times, expr[n - k], expr[k]],
{k, 1, n - 1}
],
Map[u, expr[n - 1]]
];


For example:

expr[3]

(* {u[x]^3, u[x] u[u[x]], u[u[x]^2], u[u[u[x]]]} *)

expr[4]

(*
{u[x]^4, u[x]^2 u[u[x]], u[x] u[u[x]^2], u[x] u[u[u[x]]],
u[u[x]]^2, u[u[x]^3], u[u[x] u[u[x]]], u[u[u[x]^2]], u[u[u[u[x]]]]}
*)

-
Thanks ! That does the job and generates all rooted trees, this is excellent. –  ThQ May 14 at 13:06
@ThQ Was glad to help. Next time you ask a question, I suggest including some (however flawed or incomplete) attempts / code you tried. Questions showing no effort from the asker's side are generally frowned upon here (although I understand that for a beginner user of Mathematica, question such as this can be hard to even start with). –  Leonid Shifrin May 14 at 13:14