4
$\begingroup$

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:

    enter image description here

  • While $U[x]U\big[U[x] U[x]\big]$ is equivalent to the rooted tree

    tree1

  • And finally $U\Big[U[x]\,U\big[U[x] U[x]\big]\Big]$ is equivalent to the rooted tree

    tree2

Could you please help me generate all rooted trees on $n$ vertices, i.e. algebraic expressions as above with $U$ appearing $n$ times?

$\endgroup$
5
$\begingroup$

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]]]]}
*)
$\endgroup$
2
  • $\begingroup$ Thanks ! That does the job and generates all rooted trees, this is excellent. $\endgroup$
    – ThQ
    May 14 '14 at 13:06
  • $\begingroup$ @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). $\endgroup$ May 14 '14 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.